# If $a\neq 1$, find $(a+1)(a^2+1)(a^4+1)\ldots(a^{2^n}+1)$.

If $a\neq 1$, find $$(a+1)(a^2+1)(a^4+1)\ldots(a^{2^n}+1)$$

Or i.e.

If $a\neq 1$, find $\prod_{i=0}^n(a^{2^i}+1)$.

It really does seem like $$(a+1)(a^2+1)(a^4+1)\ldots(a^{2^n}+1)=a^{2^n+2^{n-1}+\ldots+2+1}+a^{2^n+2^{n-1}+\ldots+2+1-1}+a^{2^n+2^{n-1}+\ldots+2+1-2}+\ldots+a^2+a+1$$

Or i.e. $$\prod_{i=0}^n(a^{2^i}+1)=\sum_{i=0}^{2^n+2^{n-1}+\ldots+2+1}a^i$$

Is there an interesting proof of this? I'd appreciate any help.

-
multiply numerator and denominator with $a-1$, you will get $\frac{(a^{2^{n+1}}-1)}{a-1}$ –  r9m Mar 7 '14 at 14:56
You can see it as r9m comments, or you can just see it as a generating function statement that every number from $0$ to $2^{n}-1$ can be represented in exactly one way as an $n$-digit binary number. –  Thomas Andrews Mar 7 '14 at 15:42

What happens when you multiply the expression by $a-1$ and simplify it?
The "generating function" interpretation of this is that every number from $0$ to $2^n-1$ can be written in exactly one way in base $2$ number of $n$ digits or less.
So the base 3 way of writing this is that $$(1+x+x^2)(1+x^3+x^6)(1+x^9+x^{18})\dots(1+x^{3^n}+x^{2\cdot 3^n}) = \frac{x^{3^{n+1}}-1}{x-1}$$