Author Topic: TT's Maths Thread (Read 139948 times) Tweet Share

TrueTears · « **Reply #405 on:** December 13, 2009, 08:23:54 pm »

Thank you Ahmad, your explanations are always so easy to understand

kamil9876 · « **Reply #406 on:** December 13, 2009, 08:25:39 pm »

use exercise 3 and the fundamental theorem of arithmetic to show that there are infinitely many primes

TrueTears · « **Reply #407 on:** December 13, 2009, 10:51:11 pm »

Quote

1. Let $f(n)$ denote the number of non-negative solutions to $a_1 + a_2 + \cdots + a_k = n$ . Find the generating function for the counting sequence $f(n)$ .

$a_1$ can take any value between $[0,\infty)$ , so can $a_2, a_3, \cdots, a_k$

so define $a_1(x) = a_2(x) = a_3(x) = \cdots = a_k(x) = 1+x^1+x^2+x^3+x^4+\cdots$

Thus $f(n) = a_1(x)a_2(x)a_3(x) \cdots a_k(x) = (1+x^1+x^2+x^3+x^4+\cdots)^k = \left(\frac{1}{1-x}\right)^k = \frac{1}{(1-x)^k}$

Quote

2. What is $(1+x)(1+x^2)(1+x^4)(1+x^8)\cdots$ when expanded out? (Hint: think binary).

Expanding out the first few factors we get: $x^7+x^6+x^5+x^4+x^3+x^2+x^1+1$

My conjecture is that every non-negative integer can be expressed as unique powers with base 2 and that there is only one way to achieve this.

Now how to prove it?

zzdfa · « **Reply #408 on:** December 13, 2009, 11:10:04 pm »

if it were not true, computers would be nonexistent.
computers exist, hence it is true. qed.

(strong induction works fine too)

TrueTears · « **Reply #409 on:** December 13, 2009, 11:53:24 pm »

lol thanks Ahmad for hint

$\frac{(1-x)(1+x)(1+x^2)(1+x^4)(1+x^8)\cdots(1+x^{2^n})}{1-x} = \frac{(1-x^2)(1+x^2)(1+x^4)(1+x^8)\cdots(1+x^{2^n})}{1-x} = \frac{(1-x^{2^n})(1+x^{2^n})}{1-x} = \frac{1-x^{2^{n+1}}}{1-x}$

$= x^{2^{n+1}-1} + \frac{1}{1-x} = x^{2^{n+1}-1} + \left(1+x^1+x^2+x^3+ \cdots\right)$

kamil9876 · « **Reply #410 on:** December 14, 2009, 12:34:13 am »

an extension:

prove that for all $b>1$ :

$(1+x+x^2...x^{b-1})(1+x^b+x^{2b}...+x^{(b-1)b})(1+x^{b^2}+x^{2b^2}....+x^{(b-1)b^2})(1+x^{b^3}+x^{2b^3}....+x^{(b-1)b^3})....=1+x+x^2+x^3...$

TrueTears · « **Reply #411 on:** December 14, 2009, 04:11:31 am »

Quote from: zzdfa on December 13, 2009, 11:10:04 pm

if it were not true, computers would be nonexistent.
computers exist, hence it is true. qed.

(strong induction works fine too)

Yeap so using strong induction.

Let $\mbox{n}$ be the integer which will be represented as the sums of unique powers of $2$ .

$n = M + x$ where $M$ and $x$ (' $x$ ' can be a sum of distinct powers of $2$ ) are both distinct powers of $2$ . And clearly $M \le n$

For example, $37 = 2^5+2^2+2^0$

Here $n = 37, M = 2^5$ and $x = 2^2+2^0$

Our inductive hypothesis is that for all integers less than $\mbox{n}$ , can also be expressed like $M+x$ .

However if $x$ contains a $M$ , then we can not satisfy the condition of having unique powers.

I conjecture that $x < M$

Consider if $x > M$ .

Thus let $x = M+y$ (where $y$ is some integer).

$\therefore n = M + M + y \implies n = 2M+y$

$\therefore n > 2M$ Contradiction! (Since $2M$ is just a larger power of $2$ so the equation becomes $n = 2M + x$ and clearly $2M \le n$ )

Thus $x<M$

Now by strong induction, all integers less than $\mbox{n}$ can be expressed in the form $n = M+x$ which completes the proof.

kenhung123 · « **Reply #412 on:** December 14, 2009, 10:05:59 am »

How'd you do TT?

kamil9876 · « **Reply #413 on:** December 14, 2009, 12:53:00 pm »

Now you have to prove uniqueness. and congratz on the score

TrueTears · « **Reply #414 on:** December 14, 2009, 11:48:00 pm »

Quote from: kamil9876 on December 14, 2009, 12:53:00 pm

Now you have to prove uniqueness. and congratz on the score

Finally time to do some maths!

What do you mean prove uniqueness?

humph · « **Reply #415 on:** December 14, 2009, 11:52:17 pm »

You've proved existence (that every integer can be written in that form). You also need to prove uniqueness (that there is only one such form for each integer).

P.S. How did you go in each of your subjects?

kamil9876 · « **Reply #416 on:** December 15, 2009, 12:00:45 am »

meaning that a number cannot have two different representations. ie let's write it down in descending powers:

$2^{a_1}+2^{a_2}....2^{a_m}=2^{b_1}+2^{b_2}... 2^{b_k}$

now we want to show that if $a_i=b_i$ for all $i$ DOES not hold, then we arrive at a contradiction:

Now suppose the expressions are not the same: we can cancel out any terms common to both sides, thus all terms involved are different and only one side contains the maximum term, call this $2^M$ . Say WLOG that LHS contains this term. Thus we have

$LHS\geq 2^M$ (1)

Now let the RHS have a maximum term, call it $2^K$ thus the largest possible value for the RHS is $1+2^1+2^2...+2^K=2^{K+1}-1$

Therefore $RHS\leq 2^{K+1}-1$

$\implies RHS<2^{K+1}$ , but $2^{K+1}\leq 2^M$ since $K$ is strictly less than $M$ . Therefore:
$<br />RHS<2^M$ (2)

But (1) and (2) contradict $RHS=LHS$ . Thus we cannot have different expressions for the same number.

TrueTears · « **Reply #417 on:** December 15, 2009, 02:00:53 am »

Thanks!!!!

I'm really enjoying generating functions, it makes such good use of algebra to tell a story.

TrueTears · « **Reply #418 on:** December 15, 2009, 03:31:26 pm »

Hmm the Catalan Recurrence, how does one prove it using generating functions to get a closed form of the recurrence formula: $t_n = \sum_{u+v=n+1} t_ut_v$

Ahmad · « **Reply #419 on:** December 15, 2009, 04:15:31 pm »

We have $t_0 = 1$ and $t_n = \sum_{i=1}^n t_{i-1} t_{n-i}$ for $n > 0$ . Define $T(x) = \sum_{n=0}^\infty t_n x^n$ . As per usual to find the generating function we multiply the recurrence equation by $x^n$ and sum over all values of n for which the recurrence is valid. The rest is just about having the fortitude to carry out the computation, which with enough experience doesn't require much thinking at all. However, I'm aware it can be difficult to do (and understand) in the beginning, so feel free to ask about any of the steps below if you're confused and I'll go through how it works.

$\sum_{n\ge 1} t_n x^n = \sum_{n\ge 1} \sum_{i=1}^n t_{i-1} t_{n-i} x^n$

The left hand side is just $T(x) - t_0 x^0 = T(x) - 1$ . At this point I want to interchange the order of summation (to break the inner sum's dependence on the outer sum's dummy variable).

$= \sum_{i=1}^\infty \sum_{n=i}^\infty t_{i-1} t_{n-i} x^n$

$= \sum_{i=1}^\infty t_{i-1} \sum_{n=i}^\infty t_{n-i} x^n$

Now I'm going to perform an index shift in the inner sum, by starting the sum at n=0, and replacing n by n+i in the summand.

$= \sum_{i=1}^\infty t_{i-1} \sum_{n=0}^\infty t_{n} x^{n+i}$

$=\left( \sum_{i=1}^\infty t_{i-1} x^i \right) \left(\sum_{n=0}^\infty t_{n} x^{n} \right)$

And we've broken the sum into independent parts, which is what I tried to hint at as my reason for interchanging summation order. The second bracket is just $T(x)$ , so we'll work on the first bracket. To do this we perform an index shift starting the sum at i=0 and changing i to i+1 in the summand.

$=\left( \sum_{i=0}^\infty t_{i} x^{i+1} \right) \left(\sum_{n=0}^\infty t_{n} x^{n} \right)$

$=x \cdot \left( \sum_{i=0}^\infty t_{i} x^{i} \right) \left(\sum_{n=0}^\infty t_{n} x^{n} \right)$

$= x (T(x))^2$

And we've done the hard part. We have $T(x) - 1 = x (T(x))^2$ . Now you can solve this functional equation for $T(x)$ . You'll get a quadratic and hence two solutions, think about which one you should select.

Search the forums now!

We have moved!

Author Topic: TT's Maths Thread (Read 139948 times) Tweet Share

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

zzdfa

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kenhung123

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

humph

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

Ahmad

Re: TT's Maths Thread

Recent Posts

User:
Password: