# Show that $\prod_{k=1}^{n}(1+x^{2^k})$ is a polynomial of the form $\sum_{k=0}^{m}c_{k}x^{k}$

While solving exercises from Chapter 1, Calculus Vol. 1 by Apostol, I came across this question that asks to show that $$\displaystyle\prod_{k=1}^{n}(1+x^{2^k})$$ is a polynomial of the form $$\displaystyle\sum_{k=0}^{m}c_{k}x^{k}$$.

I have outlined a proof for the same by constructing sets: \begin{align} K &= \{2^k:k\in [1,n],k\in \mathbb{N}\}\\ S_0 &= \{1\}\\ S_1 &= \{x^{k_1}: k_1\in K\}\\ S_2 &= \{x^{k_1+k_2}: k_1,k_2 \in K, k_1 \neq k_2\}\\ S_3 &= \{x^{k_1+k_2+k_3}: k_1,k_2,k_3 \in K, k_1 \neq k_2\neq k_3\}\\ & \vdots\\ S_n &= \{x^{\sum_{i=1}^{n} k_i}: k_i \in K, k_i \neq k_j\forall i\neq j \}\\ S &= \bigcup_{i=0}^{n}S_i\\ \# S &= \Sigma_{i=0}^{n}{n \choose i} = 2^n \end{align} The polynomial can now be written as: $$\prod_{k=1}^{n}(1+x^{2^k}) = \sum_{i=1}^{2^n}x_i\text{ where }x_i \in S$$ However, I am not able to construct a simple algebraic formula for the last statement. I have an intuition that $$x_i\neq x_j\text{ if }i\neq j$$. I am not able to assert this statement as well.

• But every polynomial is of the form $\sum_{k=0}^m c_kx^k$? Am I missing something, or is there a condition on the $c_k$ or $m$ that's not been specified? Jun 2, 2022 at 6:01
• @SarveshRavichandranIyer yes, every polynomial is of this form. I think the textbook is asking to prove it via evaluating each coefficient $c_k$ and power $k$ to show that the formula holds. Jun 2, 2022 at 6:09
• Hint: $1 + x^{2^k} = \frac{1 - x^{2^{k+1}}}{1 - x^{2^k}}$ Jun 2, 2022 at 7:09
• Thanks, @ananta. This question isn't exactly a duplicate, but it rephrases the product as a ratio of two polynomials. If you know the geometric progression sum formula, you will be able to see what polynomial that particular ratio equals, which will do the job. I'm still looking for a duplicate, but if we're all convinced I can write an answer. Jun 2, 2022 at 7:58
• Consider that any positive natural number has a unique representation as a sum of distinct powers of $2$. Jun 2, 2022 at 9:57

The coefficients of the polynomial $$\prod_{i=1}^L (1+x^{2^k})$$ can be detected and confirmed in multiple ways.

#### Guessing the answer (before proving it)

I can roughly try to see what you're doing by constructing sets : you're basically noting that $$1 = x^0$$ contributes no powers of $$x$$ to any product of powers of $$x$$. Consequently, you seem to be grouping together those monomials which contain only certain number of powers of $$x$$ which are not equal to $$1$$.

You've got the basic structure of your argument right, although some semantics are off, that have been pointed out in the comments. What you need is further insight, that you would obtain if you computed the "simplest" cases of this product.

Watch what happens when one does $$\prod_{k=1}^1 (1+x^{2^k}) = 1+x^2 \\ \prod_{k=1}^2 (1+x^{2^k}) = (1+x^2)(1+x^4) = 1+x^2+x^4+x^6 \\ \prod_{k=1}^3 (1+x^{2^k}) = (1+x^2+x^4+x^6)(1+x^8) = 1+x^2+x^4+x^6+x^8+x^{10}+x^{12}+x^{14}$$

It would not take a lot of effort to make the necessary deduction , that the RHS is the sum of some powers of $$x$$. With more observation, it is easy to see that the RHS equals the sum $$\sum_{j=0}^{2^{L}-1} (x^{2j})$$

We then ask ourselves : how can we prove the result

For all $$L \geq 1$$, the quantity $$\prod_{k=1}^L (1+x^{2^k})$$ is a polynomial, which equals $$\sum_{j=0}^{2^L-1} (x^{2j})$$.

As it turns out, there are multiple ways. We can explore some of them.

##### Induction

This is pretty much the way I'd expect a result of this kind to be introduced and proved first. The base cases (and more) i.e. $$L=1,2,3$$ have already been checked , which was when we made our observations. Therefore, we only need to prove the induction case.

That would basically involve proving that $$\left(\sum_{j=0}^{2^{L+1}-1} x^{2j}\right) = \left(\sum_{j=0}^{2^{L}-1} x^{2j}\right)(1+x^{2^{L+1}})$$

To do this, expand the RHS using the fact that polynomial multiplication is distributive. The RHS then becomes $$\sum_{j=0}^{2^{L}-1} (x^{2j}+x^{2^{L+1}+2j}) = \sum_{j=0}^{2^{L}-1} x^{2j} + \sum_{j=0}^{2^{L}-1} x^{2^{L+1}+2j}$$ Now we look back at the LHS and break it into $$\left(\sum_{j=0}^{2^{L+1}-1} x^{2j}\right) = \sum_{j=0}^{2^{L}-1} x^{2j} + \sum_{j=2^L}^{2^{L+1}-1} x^{2j}$$ In the second term, make the change of variable $$j - 2^{L} = l$$. We then get $$\sum_{j=0}^{2^{L}-1} x^{2j} + \sum_{j=2^L}^{2^{L+1}-1} x^{2j} = \sum_{j=0}^{2^{L}-1} x^{2j} + \sum_{l=0}^{2^{L}-1} x^{2^{L+1}+ 2l}$$ This is the same sum as the RHS! Hence, the LHS equals the RHS and the general statement is proved by induction.

##### Using combinatorics (continuing your idea)

Using combinatorial ideas, one may prove the identity as well, as you tried to do so. In fact, why don't we use your notation?

You already have your $$K$$ and $$S_n$$ in place. Just to redefine them for completeness, $$K = \{2^k , 1 \leq k \leq L\}$$ and $$S_m = \{x^{\sum_{i=1}^m k_i}, k_i \text{ distinct}\}$$ for $$0 \leq m \leq L$$. Then we set $$S = \cup S_m$$ and know that the polynomial we need is the sum over all elements of $$S$$.

The missing bit of insight is the binary expansion of a number here.

You see, every natural number has a binary expansion : which is, at the heart of it, a way to write that number as a distinct sum of powers of $$2$$ (which would be members of $$K$$). Think about it : for $$13$$, we have $$13 = 1101$$ in binary, which translates to $$8+4+1$$. The convenience of the binary expansion is in this very fact.

If we used it (and it is proved by induction, so you could say we're "repeating the argument" of the previous section, but such an observation is helpful even when one is handling harder questions) then what we see is :

For every $$j=0$$ to $$2^L-1$$, the term $$x^{2j}$$ must appear in at least one of the $$S_i$$.

Why? Indeed, take any such $$j$$ and perform its binary expansion. If there are $$l$$ $$1$$s in the expansion, then $$x^{2j} \in S_l$$. It must happen that $$0 \leq l \leq L$$, since if $$j$$ had more than $$L+1$$ $$1$$s then $$j$$ must have at least $$L+1$$ binary digits so that $$j \geq 2^L$$, a contradiction.

For every $$j=0$$ to $$2^L-1$$, the term $$x^{2j}$$ must appear in exactly one of the $$S_i$$.

Why? Of course, if $$x^{2j}$$ belonged in both $$S_i$$ and $$S_{i'}$$, say, then $$j$$ would admit two different binary expansions, because the number of $$1$$s in those binary expansions would be different. Consequently, $$x^{2j}$$ appears in exactly one $$S_i$$. Now we get :

For every $$j=0$$ to $$2^L-1$$, the term $$x^{2j}$$ appears exactly once in $$S$$.

However, that's $$2^{L}$$ elements, and $$\#S = 2^L$$, as you already know. So we've listed all the elements of $$S$$, and adding them up leads to $$\sum_{j=0}^{2^L-1} x^{2j}$$, as desired.

##### A different guess using a polynomial cascade

A polynomial cascade is an often seen olympiad-type technique, where a product of various polynomial collapses following the introduction of a "simplifier" term that leads to multiplications which rapidly simplify the number of terms in the polynomial. In this case, the tool is the difference of squares formula.

For example, look at just $$(1+x^2)(1+x^4)$$, say. When we multiply by $$1-x^2$$ , we use difference-of-squares twice to get $$(1-x^2)[(1+x^2)(1+x^4)] = [(1-x^2)(1+x^2)](1+x^4) =(1-x^4)(1+x^4) = 1-x^8$$ Therefore, we obtain as a corollary that $$1-x^8$$ is a polynomial multiple of $$1-x$$, and $$(1+x)(1+x^2) = \frac{1-x^8}{1-x}$$

Now, I can immediately sense a problem : the RHS isn't defined at $$x=1$$, but the LHS is? So what exactly is going on here? Well, there are two ways of looking at this. The first is more natural at a basic level, but will miss the point here. The second goes slightly further forward than the first, but succeeds in making a point.

• If one says "Ah, well, let's just say they're equal on the domain $$\mathbb R \setminus \{1\}$$ and treat this as an equality of functions" then one is right, but not doing enough.

• If one instead says "Oh, but, the equality isn't on $$\mathbb R \setminus \{1\}$$ , it's actually on $$\mathbb R$$, and the function $$\frac{1-x^4}{1-x}$$ has been extended to $$1$$ so that $$\frac{1-x^4}{1-x}$$ equals $$(1+x)(1+x^2)$$ at $$1$$", then one gets the point : the fraction isn't actually a function with a restricted domain, it's in fact a function with a domain that is extended by the polynomial on the LHS.

That resolves the conflict about the equality : it is very much of functions on $$\mathbb R$$ , with no trouble caused. Here's a caveat : the equality doesn't show that the product on the LHS is a polynomial. That the product is a polynomial follows from the fact that the product of two polynomials is one as well, and nothing more complicated. In that light and with that notion of equality, one may very well make the conjecture that $$\prod_{k=1}^L (1+x^{2^k}) = \frac{x^{2^{L+1}}-1}{x^2-1}$$

Which is basically proved by the cascade argument I detailed for the case $$L=2$$ earlier, but is basically proved by induction. The base case is already proved, but the induction step is easy and involves no binary expansion : if $$\prod_{k=1}^L (1+x^{2^k}) = \frac{x^{2^{L+1}}-1}{x^2-1}$$ then $$\prod_{k=1}^{L+1} (1+x^{2^k}) = \frac{x^{2^{L+1}}-1}{x^2-1} \times (1+x^{2^{L+1}}) = \frac{(x^{2^{L+1}}-1)(x^{2^{L+1}}+1)}{x^2-1} \\ =\frac{x^{2^{L+2}}-1}{x^2-1}$$ using the difference of squares formula, proving the induction step and thus providing for a formula which is easier to work with.