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

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