I'm asking for an alternative (more common?) proof of the following equality, more specifically an alternative proof for the inductive step: $$(1+x)(1+x^2)(1+x^4)...(1+x^{2^n})=\dfrac{1-x^{2^{n+1}}}{1-x} (x\neq 1)$$ This is how I proved it:

Basecase: substitute $1$ for $n$, everything works out.
Inductive step: assume that $$\prod _{i=1}^{n}(1+x^i)=\dfrac{1-x^{2^{n+1}}}{1-x}$$ then $$\prod _{i=1}^{n+1}(1+x^i)=\dfrac{1-x^{2^{n+1}}}{1-x} (1+x^{n+1})$$ Let $a$, $b$ and $c$ be positive real numbers, then $\dfrac {c}{a}=b\Leftrightarrow ab=c$, thus
$$\dfrac {\left( \dfrac{1-x^{2^{n+2}}}{1-x}\right)}{\left( \dfrac{1-x^{2^{n+1}}}{1-x}\right)}=1-x^{2^{n+1}} \Leftrightarrow \dfrac{1-x^{2^{n+1}}}{1-x} (1+x^{n+1}) = \dfrac{1-x^{2^{n+2}}}{1-x}$$ $$\dfrac {\left( \dfrac{1-x^{2^{n+2}}}{1-x}\right)}{\left( \dfrac{1-x^{2^{n+1}}}{1-x}\right)}=\dfrac {1-x^{2^{n+2}}}{1-x^{2^{n+1}}}$$ Applying polynomial division, we see that indeed $\dfrac {1-x^{2^{n+2}}}{1-x^{2^{n+1}}} = 1+x^{2^{n+1}}$.
Thus $\dfrac{1-x^{2^{n+1}}}{1-x} (1+x^{n+1}) = \dfrac{1-x^{2^{n+2}}}{1-x}$.

However, the exercise was in a chapter on binomial coefficients and pascal's triangle, furthermore we didn't mention polynomial division in class. Which makes me think that there was another solution that I was "supposed" to see. How was I supposed to prove it?


4 Answers 4


In the inductive step, you assume that

$$(1+x)(1+x^2)(1+x^4)...(1+x^{2^n}) = \dfrac{1-x^{2^{n+1}}}{1-x}$$

Which means that

$$(1-x)(1+x)(1+x^2)(1+x^4)...(1+x^{2^n}) = 1-x^{2^{n+1}}$$

Multiply by $(1+x^{2^{n+1}})$ and you get

$$(1-x)(1+x)(1+x^2)(1+x^4)...(1+x^{2^n})(1+x^{2^{n+1}}) = (1-x^{2^{n+1}})(1+x^{2^{n+1}})$$

Using $(a-b)(a+b)=a^2 - b^2$, the left side simplifies to

$$(1-x^{2^{n+1}})(1+x^{2^{n+1}}) = 1 - \left(x^{2^{n+1}}\right)^2 = 1-x^{2^{n+2}}.$$

This means that the previous equation becomes

$$(1-x)(1+x)(1+x^2)(1+x^4)...(1+x^{2^n})(1+x^{2^{n+1}}) = (1-x^{2^{n+2}})$$

and, after dividing by $(1-x)$, you are done. No polynomial division required.


Expanding $(1+x)(1+x^2)(1+x^4)\cdots(1+x^{2^n})$ gives $1+x+x^2+\cdots +x^{2^{n+1}-1}$ because every integer $k$ with $0 \le k \le 2^{n+1}-1$ has a unique binary representation (as a sum of powers of $2$).


On the left-hand side, the ratio of $\Pi_n$ over $\Pi_{n-1}$ is


and on the right-hand side,







A Proof with a Bit of Field Theory

Over a field of characteristic $2$, $1+x^{2^r}=(1+x)^{2^r}$ and $1-x=1+x$, so the LHS is $$ \begin{align} \prod_{i=0}^n\,\left(1+x^{2^i}\right) &=\prod_{i=0}^n\,(1+x)^{2^i}=(1+x)^{\sum\limits_{i=0}^n\,2^i}=(1+x)^{2^{n+1}-1} \\ &=\frac{(1+x)^{2^{n+1}}}{1+x}=\frac{1+x^{2^{n+1}}}{1+x}=\frac{1-x^{2^{n+1}}}{1-x}\,. \end{align}$$

Over a field of characteristic not equal to $2$, we may assume to be algebraically closed, hence every nonconstant polynomial has roots in the field. The polynomial $1-x^{2^{n+1}}$ has the derivative $-2^{n+1}\,x^{2^{n+1}-1}$, which is nonzero at any root of $1-x^{2^{n+1}}$. Thus, $1-x^{2^{n+1}}$ has only simple roots, one of which is $1$. Therefore, $\frac{1-x^{2^{n+1}}}{1-x}$ is the product of $x-\omega$, where $\omega\neq 1$ are other roots of $1-x^{2^{n+1}}$. However, if $r$ is the smallest positive integer such that $\omega^{2^r}=1$, then $\omega^{2^{r-1}}=-1$, or $\omega$ is a root of $1+x^{2^{r-1}}$. Furthermore, all the roots of $1+x^{2^{r-1}}$, for $r=1,2,\ldots,n+1$, are clearly roots of $1-x^{2^{n+1}}$ and they are not equal to $1$. Finally, if $r$ and $s$ are distinct positive integers, then we can easily show that $\gcd\left(1+x^{2^{r-1}},1+x^{2^{s-1}}\right)=1$ (well, the roots of $1+x^{2^{r-1}}$ are all elements $\omega$ in the field such that $\omega^k=1$ if and only if $2^{r}$ divides $k$). Hence, $\prod\limits_{r=1}^{n+1}\,\left(1+x^{2^{r-1}}\right)=\prod\limits_{i=0}^n\,\left(1+x^{2^i}\right)$ is a factor of $\frac{1-x^{2^{n+1}}}{1-x}$. As both of these polynomials have the same degree and are monic, we conclude that $$\prod\limits_{i=0}^n\,\left(1+x^{2^i}\right)=\frac{1-x^{2^{n+1}}}{1-x}\,.$$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .