2
$\begingroup$

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.

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

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

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

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

$\endgroup$
2
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.