Product of Sums: Show that the following is a Polynomial by converting it into standard form.

Question

$$\prod_{k=0}^n (1+x^{2^k})$$ The given expression simplifies to $(1+x)(1 + x^2)...(1 + x^{2^n})$

I am not able to proceed further. How do I express this in Summation form?

Answer 1

We have

$$\prod_{k = 0}^n (1 + x^{2^k}) = \prod_{k = 0}^n \frac{1 - (x^{2^k})^2}{1 - x^{2^k}} = \prod_{k = 0}^n \frac{1 - x^{2^{k+1}}}{1 - x^{2^k}} = \frac{1 - x^{2^{n+1}}}{1 - x},$$

and

$$\frac{1 - x^{2^{n+1}}}{1 - x} = 1 + x + x^2 + \cdots + x^{2^{n+1} - 1}.$$

Thus

$$\prod_{k = 0}^n (1 + x^{2^k}) = 1 + x + x^2 + \cdots + x^{2^{n+1} - 1}.$$

Answer 2

Hint: Every integer between $0$ and $2^{n+1}-1$ has a unique binary representation, hence it is uniquely the sum of some of the numbers $1,2,4,8, \dotsc, 2^n$.

If you still have no idea, you should just expand the product manually for some small $n$. You will definitely get an idea, how the general case might look like. At least then you will get the idea of the hint.