Transform $\prod_{k=0}^{n} (1+x^{2^{k}})$ to $\sum_{k=0}^{n} c_{k}x^{k}$

Question

I want to transform the following $$\prod_{k=0}^{n} (1+x^{2^{k}})$$ to the canonical form $\sum_{k=0}^{n} c_{k}x^{k}$

This is what I got so far \begin{align*} \prod_{k=0}^{n} (1+x^{2^{k}})= \dfrac{x^{2^{n}}-1}{x-1} (x^{2^{n}}+1) \\ \end{align*} but I don't know how to continue, can someone help me with this?

Note that the expansion is of the form $\sum_{k\ge 0}x^{\sum_{j=0}^n r_j 2^{j}}$, where $r_j\in {0,1},\ j=0,\cdots,n$. The exponents can be seen to be the binary expansion of the numbers from $0$ to $2^{n}-1$. — Samrat Mukhopadhyay, Sep 27 '19 at 07:46

score 4 · Accepted Answer · answered Mar 29 '19 at 10:13

Note that $ \sum_{k=0}^{n-1} 2^k=2^n-1$. Therefore, the highest power of $x$ in $\prod_{k=0}^{n-1}(1+x^{2^k})$ is $2^n-1$. In other words, none of the terms will repeat as we keep multiplying by $1+x^{2^n}$. Thus, the relation can be obtained using induction.

It is easy to see that for $n=1$ \begin{equation} \prod_{k=0}^1(1+x^{2^k}) = (1+x)(1+x^2)= 1+x+x^2+x^3. \end{equation} Now, let us assume that $\prod_{k=0}^{n-1}(1+x^{2^k}) = \sum_{k=0}^{2^n-1} x^k$. Then, we have \begin{equation} \prod_{k=0}^{n}(1+x^{2^k}) = \left(\sum_{k=0}^{2^{n-1}} x^k\right)(1+x^{2^{n}}) = \sum_{k=0}^{2^{n}-1} x^k+ \sum_{k=0}^{2^{n}-1} x^{k+2^n} = \sum_{k=0}^{2^{n+1}-1} x^k. \end{equation}

score 3 · Answer 2 · answered Mar 29 '19 at 09:48

3

Looks good as

\begin{align} \prod_{k=0}^{n-1}\left(1+x^{2^{k}}\right)&=\prod_{k=0}^{n-1}\frac{1-x^{2^{k+1}}}{1-x^{2^{k}}}\\ &=\frac{1}{1-x}\prod_{k=0}^{n-1}\left(1-x^{2^{k+1}}\right)\prod_{k=0}^{n-2}\left(1-x^{2^{k+1}}\right)^{-1}\\ &={\frac{1-x^{2^{n}}}{1-x}}. \end{align}

answered Mar 29 '19 at 09:48

But how would I transform it to the canonical form? In a solution I encountered the final solution was $\dfrac{1-x^{2^{n}} }{1-x} (1+x^{2^{n}} )= (1+x+ \dots +x^{2^{n}-1} ) (1+x^{2^{n}} )$, but I did not understand how does $\dfrac{1-x^{2^{n}} }{1-x} =(1+x+ \dots +x^{2^{n}-1} ) $ – Friedrich Mar 29 '19 at 09:56
@D.Qa, sum of a geometric progression. – Martín-Blas Pérez Pinilla Mar 29 '19 at 10:46
@Martín-BlasPérezPinilla Does the same also apply for $(1+x^{2^{n}})=x^{2^{n}}+x^{2^{n}+1}+ \dots + x^{2^{n+1}-1}$ ? – Friedrich Mar 29 '19 at 13:42
@D.Qa, I think that you have forgotten the denominator and a sign... But your RHS is the sum of a geometric progression. – Martín-Blas Pérez Pinilla Mar 29 '19 at 14:52

score 3 · Answer 3 · answered Mar 29 '19 at 10:22

You may also approach this from a combinatorical point fo view:

Expanding would give a sum of $2^{n+1}$ summands.
Each summand is a product of powers of $x$ where the exponent corresponds to a uniquely determined sequence $(b_0,b_1,\ldots , b_n)$ of binary digits $b_i \in {0,1}$ for $i=0,\ldots ,n$ where $0$ means choose $1 = x^0$ and $1$ means choose $x^{2^i}$ from the factor $(1+x^{2^i})$

Hence,

$$\prod_{k=0}^{n} (1+x^{2^{k}}) = \sum_{(b_0,b_1,\ldots , b_n) \in \{0,1\}^{n+1}}x^{\sum_{i=0}^nb_i\cdot 2^i}= \sum_{k=0}^{2^{n+1}-1}x^k$$

Transform $\prod_{k=0}^{n} (1+x^{2^{k}})$ to $\sum_{k=0}^{n} c_{k}x^{k}$

3 Answers3