Home » Blog » Use an induction and properties of the product to prove an identity

Use an induction and properties of the product to prove an identity

by RoRi

Prove the identity:

    \[ \prod_{k=1}^n \left( 1 + x^{2^{k-1}} \right) = \frac{1-x^{2^n}}{1-x} \]

for x \neq 1.

Proof. For the case n=1 on the left we have,

    \[ \prod_{k=1}^n \left(1+x^{2^{k-1}}\right) = \prod_{k=1}^1 \left(1 + x^{2^{k-1}}\right) = 1+x^{2^0} = 1+x. \]

While, on the right we have,

    \[ \frac{1-x^{2^n}}{1-x} = \frac{1-x^2}{1-x} = \frac{(1-x)(1+x)}{1-x} = 1+x. \]

So, the identity holds in the case n=1. Assume then that it holds for some n = m \in \mathbb{Z}_{>0}. Then we have,

    \begin{align*} \prod_{k=1}^{m+1} \left( 1+ x^{2^{k-1}} \right) &= \left( 1 + x^{2^m} \right) \cdot \prod_{k=1}^m \left(1 + x^{2^{k-1}} \right) \\ &= \left( 1 + x^{2^m} \right) \cdot \left( \frac{1-x^{2^m}}{1-x} \right) \\ &= \frac{\left(1+x^{2^m}\right)\left(1-x^{2^m}\right)}{1-x} \\ &= \frac{1-x^{2^{m+1}}}{1-x}. \end{align*}

Hence, the statement is true for m+1, and so, for all n \in \mathbb{Z}_{>0}. \qquad \blacksquare

2 comments

Point out an error, ask a question, offer an alternative solution (to use Latex type [latexpage] at the top of your comment):