<s>[INST] 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}$$
Thanks for your help.
 [/INST] 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.  
</s>