Prove the full expansion of $(1+x)(1+x^2)\cdot\cdot\cdot(1+x^{2^n})$

Question

Prove, by using concept of base 2, that $(1+x)(1+x^2)(1+x^4)\cdot\cdot\cdot (1+x^{2^n})\equiv1+x+x^2+\cdot\cdot\cdot+x^{{2^{n+1}}-1}$. I proved it by induction with ease, but I forgot a base 2 approach which I was taught before. Thank you.

Remark: I did not expect to receive answers from different perspectives, which was indeed pleasing. The question has been solved. Nevertheless, any new approach or comment, regardless of the restriction in bold, is always welcome.

Answer 1

Let $0 \leq i \leq 2^{n+1}-1.$ then $i$ has a unique binary(=base 2) expansion in $n+1$ digits:

$$i = \sum_{k=0}^{n} \; i_k \, 2^k\qquad\text{where each }i_k \in \{0,1\}.$$

Consider the number of ways of producing an $x^i$ by multiplying one term from each bracket in $(1)$.

$$\underbrace{(1+x)}_{k=0}\underbrace{(1+x^2)}_{k=1}\underbrace{(1+x^4)}_{k=2} \cdots \underbrace{(1+x^{2^n})}_{k = n} \tag{1}$$

Choosing the $x^\text{something}$ term in the brackets corresponding to $\{k\,:\,i_k =1\}$ and the $1$ term otherwise gives you the factor

$$x^{2^{\,i_i + i_2 + \ldots i_n}} = x^{i}.$$

Conversely, very term $x^i$ obtained by multiplying out in this way must correspond to a choice of brackets. If you define

$$j_k =\begin{cases} 1&\text{if the }x^\text{something}\text{ term is chosen from the $k$th bracket,}\\ 0&\text{if the }1\text{ is chosen from the $k$th bracket.} \end{cases}$$

Then from this you can derive

$$i = \sum_{k=0}^{n} \; j_k \, 2^k$$

I.e., the $j_k$ are a binomial expansion of $i$. Hence $i_k = j_k$ for all $k$; i.e., there is only one way to obtain $x^i$ in this way, and the coefficient must be $1$.

Answer 2

An alternative method without using base 2 :

Hint:Multiply numerator and denominator by $(1-x)$

Answer 3

First let $x=2=10_2$ and work in base $2$, then $$1+x=11_2,1+x^2=101_2,1+x^4=10001_2,...,1+x^{2^n}=1000...\text{($2^n-1$ zeros repeated)}1_2$$

Now you can easily see $$(11_2)(101_2)=1111_2,(1111_2)(10001_2)=11111111_2,$$

and so on until $(111...(\text{$2^n$ ones repeated})1_2)(1000...\text{($2^n-1$ zeros repeated)}1_2)=111...\text{($2^{n+1}$ ones repeated)}1_2=1+x+x^2+...+x^{2^{n+1}-1}$

Now comes the crucial part for the proof. Notice the above number representation will be exactly the same when you let $x=3$ and work in base $3$, let $x=10$ and work in base $10$. Therefore it works for any $x$ and the two sides are congruent.

Answer 4

Hint: all integers from $1$ to $2^{n+1}-1$ can be written as unique sum of power of $2$ less than or equal to $2^{n}$

Alternative hint: all integers from $1$ to $2^{n+1}-1$ can be written as unique $n$ digits binary number

Answer 5

In any base $b$,

$$\begin{align}11\times101\times10001\times100000001\times\cdots&=1111\times10001\times100000001\times\cdots \\&=11111111\times100000001\times\cdots \\&=1111111111111111\times\cdots\end{align}$$

(There are no carries.)

Answer 6

In every binomial, the powers are $x^0$ and $x^{2^k}$. So after expansion, a term is a power of $x$ made of a sum of some terms $2^k$, with a coefficient $1$.

But the numbers made of a sum of powers of $2$ not exceeding $2^n$ are precisely the integers in $[0,2^{n+1}-1]$.