# How do you prove $\prod_{i=0}^n(1+2^{2^i})=2^{2^{n+1}}-1$ using induction?

For a homework assignment, I am being asked to find and prove (by induction) a simple formula for $$\prod_{i=0}^n(1+2^{2^i})$$. Plugging in a few small values of $$n$$ shows that the formula is $$2^{2^{n+1}}-1$$. However, when I tried to prove it using induction, I ran into some issues. Here is what I have so far:

We will prove using induction that $$P(n)$$ is true for all positive integers $$n$$, where $$P(n)$$ is true exactly when $$\prod_{i=0}^n(1+2^{2^i})=2^{2^{n+1}}-1$$ and false otherwise.

Base case:

When $$n=0$$, the left side of $$P(n)$$ is

$$\prod_{i=0}^0(1+2^{2^i})=1+2^{2^0}=1+2^1=3$$

and the right side is

$$2^{2^{0+1}}-1=2^2-1=3$$

Both sides are equal, so $$P(n)$$ holds for $$n=0$$.

Induction step:

Let $$k\in \mathbb{Z}^+$$ and suppose that $$P(n)$$ is true for $$n=k$$.
We want to show that $$P(n)$$ is also true for $$n=k+1$$; that is, we want to show that $$\prod_{i=0}^{k+1}(1+2^{2^i})=2^{2^{k+2}}-1$$.

$$\prod_{i=0}^{k+1}(1+2^{2^i})$$
$$=(1+2^{2^{k+1}})\prod_{i=0}^{k}(1+2^{2^i})\space\space\space\space\space\space\space$$factoring out the $$k+1$$ term
$$=(1+2^{2^{k+1}})(2^{2^{k+1}}-1)\space\space\space\space\space\space\space\space\space\space\space\space\space$$ by the inductive hypothesis
$$=(2^{2^{k+1}})^2-1\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space$$ expanding the above
$$=2^{2^{2(k+1)}}-1\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space$$ by properties of exponents
$$=2^{2^{2k+2}}-1$$

However, we wanted to show that $$\prod_{i=0}^{k+1}(1+2^{2^i})=2^{2^{k+2}}-1$$, not $$2^{2^{2k+2}}-1$$. Clearly these two quantities are not equal. Can anyone spot the bug in this proof? Or perhaps the formula is wrong in the first place?

Thanks

• $\prod_{i=0}^{k-1} (1+x^{2^i}) = \sum_{m=0}^{2^k-1} x^m$ (any integer $< 2^k$ is a sum of distinct powers of $2$ in a unique way) Jul 4 '19 at 19:03
• @Sil Sorry, that was a typo. I want $2^{2^{k+2}}-1$, but I have $2^{2^{2k+2}}-1$.
– user686717
Jul 4 '19 at 19:10
• I see, well $(2^{2^{k+1}})^2 \neq 2^{2^{2(k+1)}}$, as the answers show. Instead $(2^{2^{k+1}})^2=2^{2\cdot 2^{k+1}}=2^{2^{k+2}}$
– Sil
Jul 4 '19 at 19:12
• Now I understand. Thank you!
– user686717
Jul 4 '19 at 19:17

You made a mistake just before the last step("by property of exponent"). Note that $$2*(2^j) = 2^{(j+1)}$$. And $$(a^b)^c = a^{bc}$$ not $$a^b^c$$
$$(2^{2^{k+1}})^2 = 2^{2^{k+1}} \cdot 2^{2^{k+1}} = 2^{2^{k+1}+2^{k+1}} = 2^{2 \cdot 2^{k+1}} = 2^{2^{k+2}} \text{.}$$
$$\left(2^{2^{n+1}}-1\right)\left(1+2^{2^{n+1}}\right)=2^{2^{n+1}}+\left(2^{2^{n+1}}\right)^2-1-2^{2^{n+1}}=2^{2^{n+1}\cdot2}-1=2^{2^{n+2}}-1$$
Applied rule:$$\left(a^b\right)^c=a^{bc}$$