# 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? Commented Feb 14, 2016 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. Commented Feb 14, 2016 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 Commented Feb 14, 2016 at 9:16
• @MithleshUpadhayay, My pleasure. Commented Feb 14, 2016 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? Commented Dec 10, 2018 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. Commented Dec 10, 2018 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. Commented Feb 14, 2016 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 "...". Commented Feb 14, 2016 at 20:25
• @EricTowers. I prefer . to \cdot when it's not causing problems. Commented Feb 15, 2016 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? Commented Feb 15, 2016 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. Commented Feb 15, 2016 at 1:23