Proof of a sequence of products

[tim]

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 \(\displaystyle a(1), a(2),...,\) the number \(\displaystyle \prod_{i=1}^{n} a(i)\) is defined inductively by,
(i) \(\displaystyle \prod_{i=1}^{1}a(i)=a(1)\)
(ii) \(\displaystyle \prod_{i=1}^{k+1}a(i)=(\prod_{i=1}^{k} a(i))\cdot a(k+1)\) for \(\displaystyle k\geq1\)

Prove that \(\displaystyle \prod_{i=1}^{n}(1+x^{2^{i-1}})=(1-x^{2^{n}})/(1-x)\) for \(\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 \(\displaystyle n\).
Base case: [Prove statement \(\displaystyle P(1)\)]
Inductive step: Suppose as inductive hypothesis that [\(\displaystyle P(k)\) is true] for some positive integer k. Then [deduce that \(\displaystyle P(k+1)\) is true]. This proves the inductive step.
Conclusion: Hence, by induction, [\(\displaystyle P(n)\) is true] for all positive integers \(\displaystyle n\).

Again, all pretty straight forward.

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

For \(\displaystyle n=1\), \(\displaystyle (1+x^{2^{0}})=1+x\) and \(\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

 

[tim]

Aaarrgh, just seen my mistake:

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

Should be,

\(\displaystyle (1+x^{2^{0}})=1+x\) and \(\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!

 

[tim]

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 \(\displaystyle P(k+1)\) case.

\(\displaystyle x^{2^{k}}\cdot x^{2^{k}}=(x\cdot x)^{2^{k}}=(x^2)^{2^{k}}=x^{2^{k+1}}\)

 

[mmm4444bot]

Can someone tell me if this is okay?

\(\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.

 

[tim]

Ace.

Proof: We use induction on n.
For \(\displaystyle n=1\), \(\displaystyle (1+x^{2^{0}})=1+x\) and \(\displaystyle (1-x^{2^{1}})/(1-x)=1+x\).
Suppose now as inductive hypothesis that \(\displaystyle \prod_{i=1}^{k}(1+x^{2^{i-1}})=\frac{1-x^{2^{k}}}{1-x}\) for \(\displaystyle x\not=1\) and some integer \(\displaystyle k>1\). Then \(\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) \(\displaystyle =(\frac{1-x^{2^{k}}}{1-x})\cdot (1+x^{2^{k}})\) (by inductive hypothesis) \(\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 \(\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, \(\displaystyle \prod_{i=1}^{n}(1+x^{2^{i-1}})=(\frac{1-x^{2^{n}}}{1-x})\) for \(\displaystyle x\not=1\) and \(\displaystyle \forall x \in \mathbb{Z}^{+}\).