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$

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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?)

Answer 7

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

Answer 8

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.