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

Question

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.

Answer 1

What happens when you multiply the expression by $a-1$ and simplify it?

Answer 2

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}$$