Proof of a sequence of products

tim

New member
Joined
Jul 4, 2011
Messages
8
Hi all,

Awesome site you've got here.

I'm stuck on a problem in an intro to proof/numbers/set theory/functions book I'm working through in my spare time.

Apologies if this is in the wrong forum. This isn't a calculus problem (AFAIK), but I didn't see anywhere more appropriate, so here it is.

Anyway, the question is this:

Given a sequence of numbers a(1),a(2),...,\displaystyle a(1), a(2),..., the number i=1na(i)\displaystyle \prod_{i=1}^{n} a(i) is defined inductively by,
(i) i=11a(i)=a(1)\displaystyle \prod_{i=1}^{1}a(i)=a(1)
(ii) i=1k+1a(i)=(i=1ka(i))a(k+1)\displaystyle \prod_{i=1}^{k+1}a(i)=(\prod_{i=1}^{k} a(i))\cdot a(k+1) for k1\displaystyle k\geq1

Prove that i=1n(1+x2i1)=(1x2n)/(1x)\displaystyle \prod_{i=1}^{n}(1+x^{2^{i-1}})=(1-x^{2^{n}})/(1-x) for x1\displaystyle x\not=1

So far, that all looks quite straightforward.

The way the book teaches you to structure inductive proofs is as follows:

Proof: We use induction on n\displaystyle n.
Base case: [Prove statement P(1)\displaystyle P(1)]
Inductive step: Suppose as inductive hypothesis that [P(k)\displaystyle P(k) is true] for some positive integer k. Then [deduce that P(k+1)\displaystyle P(k+1) is true]. This proves the inductive step.
Conclusion: Hence, by induction, [P(n)\displaystyle P(n) is true] for all positive integers n\displaystyle n.

Again, all pretty straight forward.

But with this problem, the base case appear to be false!

For n=1\displaystyle n=1, (1+x20)=1+x\displaystyle (1+x^{2^{0}})=1+x and (1x20)/(1x)=1\displaystyle (1-x^{2^{0}})/(1-x)=1.

Consequently, my proof has fallen at the first hurdle.

Can anyone help? Is there an error in the text? Or maybe I'm missing something obvious...?

Cheers
 
Aaarrgh, just seen my mistake:

tim said:
For n=1\displaystyle n=1, (1+x20)=1+x\displaystyle (1+x^{2^{0}})=1+x and (1x20)/(1x)=1\displaystyle (1-x^{2^{0}})/(1-x)=1.

Should be,

(1+x20)=1+x\displaystyle (1+x^{2^{0}})=1+x and (1x21)/(1x)=(1x2)/(1x)=(1x+xx2)/(1x)=(1+x)(1x)/(1x)=1+x\displaystyle (1-x^{2^{1}})/(1-x)=(1-x^{2})/(1-x)=(1-x+x-x^{2})/(1-x)=(1+x)(1-x)/(1-x)=1+x as required to prove the base case.

Doh!
 
Now I'm having a bit of trouble with the inductive step. Can someone tell me if this is okay? It relates to my proof of the P(k+1)\displaystyle P(k+1) case.

x2kx2k=(xx)2k=(x2)2k=x2k+1\displaystyle x^{2^{k}}\cdot x^{2^{k}}=(x\cdot x)^{2^{k}}=(x^2)^{2^{k}}=x^{2^{k+1}}
 


tim said:
Can someone tell me if this is okay?

x2kx2k=(xx)2k=(x2)2k=x2k+1\displaystyle x^{2^{k}}\cdot x^{2^{k}}=(x\cdot x)^{2^{k}}=(x^2)^{2^{k}}=x^{2^{k+1}}

Those expressions all look equal, to me. 8-)

 
Ace.

Proof: We use induction on n.
For n=1\displaystyle n=1, (1+x20)=1+x\displaystyle (1+x^{2^{0}})=1+x and (1x21)/(1x)=1+x\displaystyle (1-x^{2^{1}})/(1-x)=1+x.
Suppose now as inductive hypothesis that i=1k(1+x2i1)=1x2k1x\displaystyle \prod_{i=1}^{k}(1+x^{2^{i-1}})=\frac{1-x^{2^{k}}}{1-x} for x1\displaystyle x\not=1 and some integer k>1\displaystyle k>1. Then i=1k+1(1+x2i1)=(i=1k(1+x2i1))(1+x2(k+1)1)\displaystyle \prod_{i=1}^{k+1}(1+x^{2^{i-1}})=(\prod_{i=1}^{k}(1+x^{2^{i-1}}))\cdot (1+x^{2^{(k+1)-1}}) (by definition) =(1x2k1x)(1+x2k)\displaystyle =(\frac{1-x^{2^{k}}}{1-x})\cdot (1+x^{2^{k}}) (by inductive hypothesis) =(1x2k1x)+x2k(1x2k1x)=1x2k+11x\displaystyle = (\frac{1-x^{2^{k}}}{1-x})+x^{2^{k}}\cdot(\frac{1-x^{2^{k}}}{1-x})= \frac{1-x^{2^{k+1}}}{1-x} and so i=1k+1(1+x2i1)=(1x2k+11x)\displaystyle \prod_{i=1}^{k+1}(1+x^{2^{i-1}})=(\frac{1-x^{2^{k+1}}}{1-x}) as required to complete the inductive step.
Hence, by induction, i=1n(1+x2i1)=(1x2n1x)\displaystyle \prod_{i=1}^{n}(1+x^{2^{i-1}})=(\frac{1-x^{2^{n}}}{1-x}) for x1\displaystyle x\not=1 and xZ+\displaystyle \forall x \in \mathbb{Z}^{+}.
 
Top