# Finding coefficient of polynomial?

The coefficient of $x^{12}$ in $(x^3 + x^4 + x^5 + x^6 + …)^3$ is_______?

### My Try:

Somewhere it explain as:

The expression can be re-written as: $(x^3 (1+ x + x^2 + x^3 + …))^3=x^9(1+(x+x^2+x^3))^3$ Expanding $(1+(x+x^2+x^3))^3$ using binomial expansion:

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

$= 1+3(x+x^2+x^3)+3*2/2((x+x^2+x^3)^2+3*2*1/6(x+x^2+x^3)^3…..$

The coefficient of $x^3$ will be $10$, it is multiplied by $x^9$ outside, so coefficient of $x^{12}$ is $10$.

It's basically the number of ways you can write $12$ as a sum of three integers all greater than or equal to $3$, where order matters. So $12=3+3+6$, $12=3+4+5$, $12=4+4+4$. The first can be rearranged three ways, the second can be rearranged six ways and the last can only be arranged one way. So yes, I believe the answer is $10$.

• Is this concept applicable for any question like my? – Mithlesh Upadhyay Feb 14 '16 at 7:36
• Yes, it follows from how the terms combine. Another classic example is how if you expand $\Pi_{n=1}^{\infty}(1+x^n+x^{2n}+x^{3n}+\cdots)=\sum a_nx^n$ you find $a_n$ is exactly the number of ways of writing $n$ as a sum, where order does not matter. For example $a_3=3$ since $3=1+1+1$, $3=1+2$, and $3=3$. So three ways. – Gregory Grant Feb 14 '16 at 7:41

$$(x^3+x^4+x^5+x^6+\cdots)^3=x^9(1+x+x^2+\cdots)^3=x^9\left(\dfrac1{1-x}\right)^3=x^9(1-x)^{-3}$$

Now, we need the coefficient of $x^3$ in $(1-x)^{-3}$

Now the $r+1,(r\ge0)$th term of $(1-x)^{-3}$ is $$\dfrac{-3(-4)(-5)\cdots(-r)(-r-1)(-r-2)}{1\cdot2\cdot3\cdot r}(-x)^r=\binom{r+2}2x^r$$

• Thanks for nice explanation – Mithlesh Upadhyay Feb 14 '16 at 9:16
• @MithleshUpadhayay, My pleasure. – lab bhattacharjee Feb 14 '16 at 12:30

From the OP, the coefficient of $x^{12}$ in $(x^3 + x^4 + x^5 + x^6 + \cdots)^3$ is equal to that of $x^3$ in $(1+x+x^2+x^3)^3$. This is equivalent to asking the number of ways to pick one $x^i$ below in each row so that the product of the $x^i$ picked in each row is of the form $kx^3$ for some number $k$.

$$\require{enclose} \bbox[border:2px solid red] { \begin{array}{c|c|c|c} x^0 & x^1 & x^2 & x^3 \\ \hline x^0 & x^1 & x^2 & x^3 \\ \hline x^0 & x^1 & x^2 & x^3 \end{array} }$$

If we focus on indices, we will find out that this is equivalent to asking the number of ways of choosing one number from each row so that the sum of three chosen numbers adds up to three.

$$\bbox[border:2px solid red] { \begin{array}{c|c|c|c} 0 & 1 & 2 & 3 \\ \hline 0 & 1 & 2 & 3 \\ \hline 0 & 1 & 2 & 3 \end{array} }$$

Therefore, the problem is asking for $$\#\{x,y,z\in\Bbb Z_0^+ \mid x \color{blue}{\fbox+} y \color{red}{\fbox+} z = 3\}.$$

Hence, the answer is very simple: ${5 \choose 2} = 10$. First, imagine that we have a $5\times 1$ grid.

\begin{array}{|l|l|l|l|l|} \hline \\ &&&& \\ \hline \end{array}

Then you choose two grids to put $\color{blue}{\fbox+}$ and $\color{red}{\fbox+}$. These two plus signs symbolises $x\color{blue}{\fbox+}y\color{red}{\fbox+}z=3$. Therefore, $\color{blue}{\fbox+}$ should be at the left of $\color{red}{\fbox+}$. The picture below serves as an example.

\begin{array}{|l|l|l|l|l|} \hline \\ &\color{blue}{\fbox+}&\color{red}{\fbox+}&& \\ \hline \tag{*} \label{*} \end{array}

Fill the remaining grids with three $\enclose{circle}{1}$ to see what happens.

\begin{array}{|l|l|l|l|l|} \hline \\ \enclose{circle}{1}&\color{blue}{\fbox+}&\color{red}{\fbox+}&\enclose{circle}{1}&\enclose{circle}{1} \\ \hline \end{array}

Therefore, this example shows one possibility $x=1,y=0,z=2$. You may make up others by choosing other combinations in \eqref{*}.

• This is a great explanation. Can you share the source of it? Or have $you$ created it? – Sherlock Watson Dec 10 '18 at 11:43
• @SherlockWatson Thanks for your appreciation. The combinatorical source is some basic counting skills in IMO training. I hope that's available in AoPS. – GNUSupporter 8964民主女神 地下教會 Dec 10 '18 at 13:05

Another way: For $|x|<1$, we have:

$$(x^3+x^4+x^5+...)^3=x^9(1+x+x^2+...)^3=x^9(1-x)^{-1}.$$

Now $(1-x)^{-3}$ is half of the second derivative of $(1-x)^{-1}.$ The second derivative of $(1-x)^{-1}=(1+x+x^2+...)$ is $(1.2+2.3 x+3.4 x^2+4.5 x^3+...).$ Half the co-efficient of $x^3$ in this, which is $(1/2).4.5=10,$ is therefore the co-efficient of $x^{12}$ in $x^9(1+x+x^2+...).$

• @Mithlesh Upadhayay. Why do you ask about a typo? I do make a lot but usually get them out. – DanielWainfleet Feb 14 '16 at 11:16
• I believe you mean "\cdot" in many of the places you have ".". Also, "\dots" or "\cdots" tend to produce better spacing in expressions than does "...". – Eric Towers Feb 14 '16 at 20:25
• @EricTowers. I prefer . to \cdot when it's not causing problems. – DanielWainfleet Feb 15 '16 at 0:25
• Alrighty. Then from where do "1.2", "2.3", "3.4", "4.5" and other non-integers in your sentence starting "The second derivative..." come from? Also, what is the bizarrely malformed syntax "(1/2).4.5" supposed to convey? – Eric Towers Feb 15 '16 at 0:32
• @EricTowers. The co-efficients come from twice differentiating the power series for $1/(1-x)$ giving the power series for $2/(1-x)^3$. Non-integers? 1.2=2,2.3=6, etc. "Half the co-efficient..." is half of 4x5. – DanielWainfleet Feb 15 '16 at 1:23