3

$$\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?

Regret
  • 3,817
Deepabali Roy
  • 477
  • 2
    Any expression formed from copies of $x$ and constants using only addition, subtraction and multiplication (and non-negative integer exponents) gives a polynomial in $x$. In other words you do not need to convert to standard form to conclude that it is a polynomial. – Marc van Leeuwen Feb 26 '15 at 09:21

2 Answers2

6

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

kobe
  • 41,901
  • 1
    Note that letting $n\to\infty$ this gives an identity of formal power series $\prod_{k = 0}^\infty (1 + x^{2^k})=\lim_{n\to\infty}\frac{1-x^{2^n}}{1-x}=\frac1{1-x}$, which can occasionally be useful. (It maybe surprising to have an infinite factorisation of $\frac1{1-x}$, but note that all those factors and their product are invertible as power series.) – Marc van Leeuwen Feb 26 '15 at 10:38
3

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.

MooS
  • 31,390