How prove with using mathematical induction $\prod_{i=0}^n 1+q^{2^i} = \frac{1-q^{2^{n+1}}}{1-q}$?

Question

Prove the identity \begin{align} \prod_{i=0}^n \left(1+q^{2^i}\right) = \frac{1-q^{2^{n+1}}}{1-q} \end{align} for each nonnegative integer $n$.

To begin with, I cannot verify the equality itself.

$\prod_{i=0}^n 1+q^{2^i} = \frac{1-q^{2^{n+1}}}{1-q}$

If $n=1$ then I have next expressions

$(1+q)(1+q^2) = \frac{1-q^{2^{1+1}}}{1-q} = $

$ = (1+q)(1+q^2) = \frac{1-q^{4}}{1-q}$

Well played and calculated =(.Speak me where i s mistaked.

Answer 1

Let the induction statement be such that

$$P(n):\prod_{i=0}^{n} 1 + q^{2^i}=\dfrac{1-q^{2^{n+1}}}{1-q}$$

We show the base $(n=0)$ case, which states

$$P(0):\prod_{i=0}^{0} 1 + q^{2^0}=\dfrac{1-q^{2^{0+1}}}{1-q}$$

Working from the right hand side, we have

$$\dfrac{1-q^{2^{0+1}}}{1-q}=\dfrac{1-q^{2}}{1-q}=\dfrac{(1-q)(1+q)}{1-q}=1+q=\prod_{i=0}^{0} 1 + q^{2^0}$$

With the base case verified, assume $P(n)$ is true and we must show $P(n+1)$ which states

$$P(n+1):\prod_{i=0}^{n+1} 1 + q^{2^i}=\dfrac{1-q^{2^{(n+1)+1}}}{1-q}$$

This should be straight forward starting from the left hand side.

$$\begin{align} \prod_{i=0}^{n+1} 1 + q^{2^i}&=\Bigg(\prod_{i=0}^{n} 1 + q^{2^i}\Bigg)\cdot(1+q^{2^{n+1}}) \\ &=\Bigg(\dfrac{1-q^{2^{n+1}}}{1-q}\Bigg)\cdot(1+q^{2^{n+1}}) \\ &=\dfrac{1-q^{2^{n+1}}q^{2^{n+1}}}{1-q} \\ &=\dfrac{1-q^{2^{n+1}+2^{n+1}}}{1-q} \\ &=\dfrac{1-q^{2\cdot2^{n+1}}}{1-q} \\ &=\dfrac{1-q^{2^{n+2}}}{1-q} \\ &=\dfrac{1-q^{2^{(n+1)+1}}}{1-q} \end{align}$$

Thus,

$$\prod_{i=0}^{n+1} 1 + q^{2^i}=\dfrac{1-q^{2^{(n+1)+1}}}{1-q}$$

And $P(n+1)$ is true for all $n \in \mathbb{N} \cup \{0\}$.

Answer 2

For the base case $n=1$, prove that $$(1+q)(1+q^2)=\frac{1-q^4}{1-q}\iff \underbrace{(1-q)(1+q)}_{=(1-q^2)}(1+q^2)=1-q^4$$

Which is true since $(a-b)(a+b)=a^2-b^2$.

For the inductive step $\color{blue}{\text{assume that the equation holds for some $n$}}$. Therefore

$$\begin{align*}(1+q)(1+q^2)(1+q^4)...(1+q^{2^{n+1}})&=\color{blue}{(1+q)(1+q^2)(1+q^4)...(1+q^{2^{n}})}\cdot (1+q^{2^{n+1}})\\ &=\color{blue}{\frac{1-q^{2^{n+1}}}{1-q}}\cdot (1+q^{2^{n+1}})\\ &=\frac{1-q^{2^{n+2}}}{1-q}\end{align*}$$

Alternatively

Although induction is usually a nice approach when it comes to proving an equation $\forall n\in\Bbb N$, there is even a nicer way to prove your equation. Observe simply that $$\begin{align*}&(1+q)(1+q^2)(1+q^4)...(1+q^{2^{n}})=\frac{1-q^{2^{n+1}}}{1-q}\\\iff& (1-q)(1+q)(1+q^2)...(1+q^{2^{n}})=1-q^{2^{n+1}}\end{align*}$$ which can be proven using repetidly the fact that $(a-b)(a+b)=a^2-b^2$ Therefore $$\begin{align*}(1-q)(1+q)(1+q^2)...(1+q^{2^{n}})&=(1-q^2)(1+q^2)...(1+q^{2^{n}})\\&=(1-q^4)(1+q^4)...(1+q^{2^{n}})\\&=\;...\\&=(1-q^{2^{n}})(1+q^{2^{n}})\\&=(1-q^{2^{n+1}})\end{align*}$$

Which is what we wanted to prove.

Answer 3

The quickest inductive proof is a telescoping product, $$\prod_{i=0}^n(1+q^{2^i})=\prod_{i=0}^n\frac{1-q^{2^{i+1}}}{1-q^{2^i}}=\frac{1-q^{2^{n+1}}}{1-q}.$$Whether or not you want to make the induction in this telescoping explicit, rewriting the original product as I have makes it simpler. To be explicit, note that $n=0$ base step is trivial (with the empty product on the left agreeing with $\frac{1-q}{1-q}=1$ on the right), while for the inductive step $$\prod_{i=0}^k\frac{1-q^{2^{i+1}}}{1-q^{2^i}}=\frac{1-q^{2^{n+1}}}{1-q}\implies\prod_{i=0}^{k+1}\frac{1-q^{2^{i+1}}}{1-q^{2^i}}=\frac{1-q^{2^{k+1}}}{1-q}\frac{1-q^{2^{k+2}}}{1-q^{2^{k+1}}}=\frac{1-q^{2^{k+2}}}{1-q}.$$

Answer 4

We will start off with the basis step using the base value of $n = 0$.

Basis step

$\prod_{i=0}^{0} (1 + q^{2^i}) = \dfrac{1 - q^{2^{n + 1}}}{1 - q}$

=> $1 + q^{2^0} = \dfrac{1 - q^{2^{0 + 1}}}{1 - q}$

=> $1 + q = \dfrac{1 - q^2}{1 - q}$

=> $(1 + q)(1 - q) = 1 - q^2$

=> $1 - q^2 = 1 - q^2$

The basis step is hereby proved by equality and we move forward to the inductive step.

Inductive step

If it is the case that $\prod_{i=0}^{n} (1 + q^{2^i}) = \dfrac{1 - q^{2^{n + 1}}}{1 - q}$ is true, then is $\prod_{i=0}^{k} (1 + q^{2^i}) = \dfrac{1 - q^{2^{k + 1}}}{1 - q}$ also true for any $0 \leq k$, which forms our hypothesis.

For this equality to be true, our hypothesis must also be true for $k + 1$.

$\prod_{i=0}^{k} (1 + q^{2^i})(1 + q^{2^{k + 1}}) = \dfrac{1 - q^{2^{k + 2}}}{1 - q}$

We use our hypothesis for a substitution:

$(\dfrac{1 - q^{2^{k + 1}}}{1 - q})(1 + q^{2^{k + 1}}) = \dfrac{(1 - q^{2^{k + 1}})(1 + q^{2^{k + 1}})}{1 - q} = \dfrac{1 - (q^{2^{k + 1}})^2}{1 - q} = \dfrac{1 - q^{2^{k + 1} * 2}}{1 - q} = \dfrac{1 - q^{2^{k + 2}}}{1 - q}$, which completes our proof.