# Polynomials identity, factoring $x^{2^n}-1$

There is a proof that I can't solve.

Show that for any integer $k$, the following identity holds:

$$(1+x)(1+x^2)(1+x^4)\cdots(1+x^{2^{k-1}})=1+x+x^2+x^3+\cdots+x^{2^k-1}$$

-
What are you asking? What is the $\theta$ for? Do you want to prove this for any integer or any natural number? –  chris Jun 26 '12 at 14:47
A direct inductive argument is actually easy: what happens if you multiply the right hand side by $1 + x^{2^k}$ and expand? –  Hurkyl Jun 26 '12 at 14:55

This equation is a fancy way of stating existence and uniqueness of binary representation.

-
...and that's what the OP wants to know about, maybe. –  Pedro Tamaroff Jun 26 '12 at 15:58
This insight makes the result intuitive. –  ncmathsadist Jun 26 '12 at 16:31

Hint: Multiple by $(1-x)$ left side and right side. and start with $(1-x)(1+x)=1-x^2$ in left side.

-
This is a nice trick. –  Martin Brandenburg Jul 2 '12 at 8:42

From each term on the left-hand side, you can either choose $x^{2^{l}}$ or $x^0$ when forming the monomial terms. Therefore, the expansion of this will only involve sums of powers of $x$.

Then think about binary representation on the exponents (using the powers on the left-hand side) to see that each power on the right-hand side will be obtained exactly once from choosing the terms (corresponding to the binary representation of the power) from each piece on the left-hand side, giving the equality.

-

We work with the left-hand side. $$(1+x)(1+x^2)=(1+x)(1)+(1+x)(x^2)=1+x+x^2+x^3.$$ Thus \begin{align} (1+x)(1+x^2)(1+x^4)&=(1+x+x^2+x^3)(1+x^4)\\ &= (1+x+x^2+x^3)(1)+(1+x+x^2+x^3)(x^4)\\ &=1+x+x^2+x^3+x^4+x^5+x^6+x^7\end{align}.

Continue. We will be multiplying $1+x+\cdots+x^7$ by $1+x^8$. Multiplying $1+x+\cdots+x^7$ by $x^8$ gets us $x^8+x^9+\cdots+x^{15}$, so the full product is $1+x+\cdots+x^{15}$

The pattern is obvious. If we wish, we can use a formal induction argument.

-