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

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.

• You want to start with $n=0$. – JacobCheverie Apr 29 at 18:46

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

• Thanks for operation with exponents ! Where pre the end. – Saint Hentai Apr 29 at 20:10

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

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.

• It is brilliant what you have done with polynomials. And it's also sad that ${1-q} ^ 3 \not= {1 + q} ^ 3$ – Saint Hentai Apr 29 at 19:43
• Alternatively method not bad, he is really good if i am not using method mathematecal induction, thanks mr. – Saint Hentai Apr 29 at 20:24
• No problem @SaintHentai ;) – Dr. Mathva Apr 29 at 20:26

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.