Closed form of infinte product proof: $\prod_{i=1}^{n}(1 + x^{2^{i-1}}) = \frac{1-x^{2^n}}{1-x}$

Question

I was working through problems in "An Introduction to Mathematical Reasoning" and am stumped on an induction proof in Problems I: Question 18, which is:

$$\prod_{i=1}^{n}(1 + x^{2^{i-1}}) = \frac{1-x^{2^n}}{1-x}$$

I checked the base case using n=1, and got:

$$1-x^2=1-x^2$$

So I assumed this was true:

$$\prod_{i=1}^{k}(1 + x^{2^{i-1}}) = \frac{1-x^{2^k}}{1-x}$$

and tried this:

$$\prod_{i=1}^{k+1}(1 + x^{2^{i-1}}) = \frac{1-x^{2^{k+1}}}{1-x}$$

$$\prod_{i=1}^{k}(1 + x^{2^{i-1}})\times(1+x^{2^{k+1-1}}) = \frac{1-x^{2^{k+1}}}{1-x}$$

$$\frac{1-x^{2^k}}{1-x}\times(1+x^{2^{k}}) = \frac{1-x^{2^{k+1}}}{1-x}$$

$$1-x^{2^k}\times(1+x^{2^{k}}) = 1-x^{2^{k+1}}$$

$$1-x^{2^{k+k}} \not= 1-x^{2^{k+1}}$$

I've been over this so many times and I still don't see where I'm going wrong, what I've missed, or an alternative approach. Any guidance would be appreciated!

Answer 1

You made a calculation error in the very last line.

$$\begin{align} \left(1-x^{2^k}\right)\left(1+x^{2^k}\right)&=1-\left(x^{2^k}\right)^2\\ &=1-x^{2\cdot2^k}\\ &=1-x^{2^{k+1}} \end{align}$$

In the last line, on the left-hand side, you have an exponent of $2^{k+k}$, but the correct exponent is $2^k+2^k$.

Answer 2

We will proceed by induction.

Note that the base case $n=1$ is true because $\displaystyle 1 + x = \frac{1-x^{2}}{1-x}$. Now, let us assume that the case $n=k$ is true. Then, we have:

$$\prod_{i=1}^{k}(1+x^{2^{i-1}}) =\frac{1-x^{2^{k}}}{1-x}$$

$$(1+x^{2^{k}})\prod_{i=1}^{k}(1+x^{2^{i-1}})=(1+x^{2^{k}})\frac{1-x^{2^{k}}}{1-x}$$

$$\prod_{i=1}^{k+1}(1+x^{2^{i-1}})=\frac{1-(x^{2^{k}})^{2}}{1-x}=\frac{1-x^{2\cdot 2^{k}}}{1-x}=\frac{1-x^{2^{k+1}}}{1-x}$$

Thus, if case $n=k$ is true, then case $n=k+1$ is true as well. Then, because case $n=1$ is true, the statement is true for all $n\in\mathbb{N}$. $\blacksquare$

Your error was in assuming $(1-x^{2^{k}})(1+x^{2^{k}}) = 1 - x^{2^{2k}}$.