# Showing that $1 + 2 x + 3 x^2 + 4 x^3 + \cdots + x^{10} = (1 + x + x^2 + x^3 + x^4 + x^5)^2$

I was studying a polynomial and Wolfram|Alpha had the following alternate form:

$$P(x) = 1 + 2 x + 3 x^2 + 4 x^3 + 5 x^4 + 6 x^5 + 5 x^6 + 4 x^7 + 3 x^8 + 2 x^9 + x^{10} = (1 + x + x^2 + x^3 + x^4 + x^5)^2$$

Of course, we can verify this through expansion, but if I were a mathematician without access to CAS, how might I notice that this is the case?

I suppose what I'm asking is how one should "see" that $P$ can be simplified to $(1 + x + x^2 + x^3 + x^4 + x^5)^2$? Is it a multinomial thing (which seems a bit too complicated for someone to "notice"), or is there something simpler about the polynomial that one could use to factor it?

• Btw What is CAS? – Manish Kundu Feb 9 '18 at 18:29
• @ManishKundu Computer Algebra System – Tiwa Aina Feb 9 '18 at 18:29
• Couldn't vanishing method simply help you to factor it? Or I wrongly understood your question? – Manish Kundu Feb 9 '18 at 18:30
• @ManishKundu Doesn't the vanishing method give you the roots? I'm asking about how to see that $P(x)$ can be converted into a power of an other polynomial. – Tiwa Aina Feb 9 '18 at 18:32
• I did it in one way by splitting the terms into two series and adding their sums, to give a perfect whole square. – Manish Kundu Feb 9 '18 at 18:54

By direct factorization:

\begin{align} P(x) &= 1 + 2 x + 3 x^2 + 4 x^3 + 5 x^4 + 6 x^5 + 5 x^6 + 4 x^7 + 3 x^8 + 2 x^9 + x^{10} \\[5px] &= 1 + x + x^2 + x^3 + x^4 + x^5 \\ &\quad\quad + x + x^2 + x^3 + x^4 + x^5 + x^6 \\ &\quad\quad\quad\quad + x^2 + x^3 + x^4 + x^5 + x^6 + x^7\\ &\quad\quad\quad\quad\quad\quad \ldots \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10} \\[5px] &= \color{blue}{1} + x + x^2 + x^3 + x^4 + x^5 \\ &\quad\quad + \color{blue}{x}\cdot(1 + x + x^2 + x^3 + x^4 + x^5) \\ &\quad\quad\quad\quad + \color{blue}{x^2} \cdot(1 + x + x^2 + x^3 + x^4 + x^5) \\ &\quad\quad\quad\quad\quad\quad \ldots \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad + \color{blue}{x^5} \cdot(1 + x + x^2 + x^3 + x^4 + x^5) \\[5px] &= (\color{blue}{1 + x + x^2 + x^3 + x^4 + x^5}) \cdot (1 + x + x^2 + x^3 + x^4 + x^5) \end{align}

• +1 for the most intuitively evident approach given yet. I was busy formatting my answer when your answer showed up, and didn't see your answer until I posted mine, but what you've done is not too far off from what I gave. – Dave L. Renfro Feb 9 '18 at 19:28
• @DaveL.Renfro Thanks, and right, it can go both ways. I was toying with the idea of using the $\,6^{th}\,$ roots of unity, instead, but in the end it looked easier this way. – dxiv Feb 9 '18 at 19:37
• Actually, it was the fact that you tried to go from the expanded form to the factored form, and my wondering why you approached this in such a difficult way, that caused me to reread the question, after which I realized the explanation I spent so much time formatting wasn't quite what was asked! – Dave L. Renfro Feb 9 '18 at 19:53

When you multiply two polynomials, the result is the sum of each pair of terms, one from the "left" and one from the "right", multiplied together.

With $(1+x+x^2+x^3+x^4+x^5)^2$, you'll get $1*1$ once (there's only one way to pick "1" from each side). But you'll get $x$ twice, once from taking the left's $1$ and the right's $x$, and once the other way around. Hence you get a $2x$ in the product. Then there's 3 ways to get $x^2$ -- $1*x^2$, $x*x$, and $x^2*1$. It's the same from the other end, with a maximum in the middle.

Recognizing the factoring is, like many complex polynomial factorings, just a matter of being familiar with the pattern.

It is easier to expand $$(1 + x + x^2 + x^3 + x^4 + x^5)^2$$

to get $$1 + 2 x + 3 x^2 + 4 x^3 + 5 x^4 + 6 x^5 + 5 x^6 + 4 x^7 + 3 x^8 + 2 x^9 + x^{10}$$ All we have to do is check the squares and twice the products to see if the coefficients are correct.

How do we see that P(x) is a perfect square? When evaluated at different integer values of x, we get perfect squares so, that may be helpful to make an intelligent guess.

Use the distributive property.

$$(1 + x + x^2 + x^3 + x^4 + x^5)(1 + x + x^2 + x^3 + x^4 + x^5)$$

is equal to

$$\begin{matrix} (1)(1 + x + x^2 + x^3 + x^4 + x^5) \\ (x)(1 + x + x^2 + x^3 + x^4 + x^5) \\ (x^2)(1 + x + x^2 + x^3 + x^4 + x^5) \\ (x^3)(1 + x + x^2 + x^3 + x^4 + x^5) \\ (x^4)(1 + x + x^2 + x^3 + x^4 + x^5) \\ (x^5)(1 + x + x^2 + x^3 + x^4 + x^5) \\ \end{matrix}$$

When the above is expanded, we get $36$ products. Arrange the results of these $36$ products into columns whose entries have the same degree.

$$\begin{matrix} 1 & x & x^2 & x^3 & x^4 & x^5 \\ & x & x^2 & x^3 & x^4 & x^5 & x^6 \\ & & x^2 & x^3 & x^4 & x^5 & x^6 & x^7 \\ & & & x^3 & x^4 & x^5 & x^6 & x^7 & x^8 \\ & & & & x^4 & x^5 & x^6 & x^7 & x^8 & x^9 \\ & & & & & x^5 & x^6 & x^7 & x^8 & x^9 & x^{10} \\ \end{matrix}$$

Adding like powers of $x$ shows how the pattern of coefficients arises, giving

$$= \;\;\; 1 + 2x + 3x^2 + 4x^3 + 5x^4 + 6x^5 + 5x^6 + 4x^7 + 3x^8 + 2x^9 + x^{10}$$

In the case of $\;(1 + x + x^2 + \ldots + x^{n-1} + x^n)^2,\;$ the same pattern of coefficients --- increasing by increments of $1$ from $1$ to some maximum value, and then decreasing by increments of $1$ from the maximum value to $1$ --- can be seen by thinking about the following.

$$\begin{matrix} 1 & x & x^2 & x^3 & x^4 & \ldots & x^{n-1} & x^n \\ & x & x^2 & x^3 & x^4 & \ldots & x^{n-1} & x^n & x^{n+1} \\ & & x^2 & x^3 & x^4 & \ldots & x^{n-1} & x^n & x^{n+1} & x^{n+2} \\ & & & x^3 & x^4 & \ldots & x^{n-1} & x^n & x^{n+1} & x^{n+2} & x^{n+3} \\ & & & & x^4 & \ldots & x^{n-1} & x^n & x^{n+1} & x^{n+2} & x^{n+3} & x^{n+4} \\ \end{matrix}$$ $$\cdot$$ $$\cdot$$ $$\cdot$$

• I just noticed that what you actually asked for was how to proceed from the expanded form to the factored form, and not the reason why going the other way produces the coefficient pattern. Oh well . . . – Dave L. Renfro Feb 9 '18 at 19:35

While others have pointed towards factorizing the expression, I would like to say that it isn't always easy for one to notice that the expression can be factorized. Also, the series has some property - the coefficients are gradually increasing or decreasing.

Let's try to find the sum of the series because that would surely help in simplification.

$$Let, \; S = 1 + 2x + 3x^2 + 4x^3+5x^4+6x^5+5x^6+4x^7+3x^8+2x^9+x^{10} \,$$

$$x . S = x + 2x^2 + 3x^3 + 4x^4 + 5x^5+6x^6+5x^7+4x^8+3x^9+2x^{10}+x^{11}$$

From here, we can get,

$$S (x-1) = -(1+x+x^2+x^3+x^4+x^5) + (x^6+x^7+x^8+x^9+x^{10}) + x^{11}$$

Now use the formula of a geometric progression in the first two series to get: $$S (x-1) = -\frac{(x^6-1)}{x-1} + \frac{x^6(x^5 - 1)}{x-1} + x^{11}$$

$$S = \frac{(1-x^6) + x^6(x^5 - 1) + x^{11}(x-1)}{(x-1)^2}$$

$$S = \frac{x^{12} - 2x^6 + 1}{(x-1)^2}$$

$$S = \frac{(x^6 - 1)^2}{(x-1)^2}$$

Now it is indeed a perfect whole square. You can simply divide $x^6-1$ by $x-1$ to get your desired result.

The coefficient of $x^n$ ($0\leq n\leq 10$) in the expansion is the number of solutions to $$x_{1}+x_{2}=n;\quad 0\leq x_i\leq5.$$ We can compute this via inclusion exclusion. Let $U$ be the set of all solutions to the previous question in non-negative integers and $A_{i}$ be the set of solutions in $U$ which $x_i>5$. Then \begin{align} |A_{1}^c\cap A_{2}^c|&=|U|-|A_{1}|-|A_{2}|+|A_{1}\cap A_{2}|\\ &=(n+1)-2(n-5)[n\geq6]+0 \end{align} where $[\cdot]$ is the iverson bracket since $A_{1}\cap A_{2}=\varnothing$.

This is equivalent to multiplying $111111 \times 111111$. There is a principle in logic called "universal generalization". Since no property of the $10$ in $10^k$ the base of $11111$ is being used, because there are no carries, it can be generalized to $x^k$.

The coefficient of $x^n$ is the number of integer compositions of $n$ into two parts where every part has length between $0$ and $5$. You can find the coefficients with a stars and bars approach. For every $n$, draw $n$ stars in a line, and see how many places it is possible to insert one bar such that there are between $0$ and $5$ stars on either side.

The reason this works is that in the expanded form, every instance of $x^n$ results from multiplying one of $\{x^0, x^1, x^2, x^3, x^4, x^5\}$ and another one of $\{x^0, x^1, x^2, x^3, x^4, x^5\}$. Thus to find the coefficient of $x^n$, it suffices to count the number of ways to get $n$ from a sum of two members of $\{0,1,2,3,4,5\}$, where the order of the sum matters.

I do realize that my and other answers address expanding the polynomial and not factoring it. I don't think there's such an easy trick to factoring it, and I think that seeing it can be factored just comes with experience and exposure to this kind of thing. (I mean, factoring an 11-digit square number isn't really easy, so why should factoring a degree-10 square polynomial be?)

• What is the reason why that relationship exists? That is, what exactly is it about the polynomial that allows us to interpret exponents as counts of integer compositions? – Tiwa Aina Feb 9 '18 at 19:05
• Good question. I've added a paragraph to explain. – NoName Feb 9 '18 at 19:37