3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ $\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) $\endgroup$
    – reuns
    Jul 4 '19 at 19:03
  • $\begingroup$ @Sil Sorry, that was a typo. I want $2^{2^{k+2}}-1$, but I have $2^{2^{2k+2}}-1$. $\endgroup$
    – user686717
    Jul 4 '19 at 19:10
  • $\begingroup$ 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}}$ $\endgroup$
    – Sil
    Jul 4 '19 at 19:12
  • $\begingroup$ Now I understand. Thank you! $\endgroup$
    – user686717
    Jul 4 '19 at 19:17
1
$\begingroup$

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$

$\endgroup$
0
1
$\begingroup$

$$ (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{.} $$

$\endgroup$
1
$\begingroup$

Induction step:

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy