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
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$