Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need to find a coefficient of $x^{21}$ inside the following expression:

$$(x^{2} + x^{3} + x^{4} + x^{5} + x^{6})^{8}$$

I think the only way (using generating functions) is to express the parentheses content with a generating function.

The generating function for the $(1, x, x^{2}, x^{3}, ...)$ sequence is equal to $\frac{1}{1-x}$.

However, well...the expression at the top is not infinite, so I can't really express it as a generating function.

How can I do this?

share|cite|improve this question

Hint Use a finite geometric series:

$$x^2 + \ldots + x^6 = x^2 \cdot \frac{1-x^5}{1-x}$$

and now you are looking for $$\left[x^{13}\right] \left(1-x^5\right)^8 \cdot \frac{1}{(1-x)^8}$$

share|cite|improve this answer
Yes, that's true, and the last part ( $\frac{1}{(1-x)^{8}}$ ) is a generating function now, but..and more hint? :) – khernik Apr 24 '13 at 21:46
There is a contribution from the $(1-x^5)^8$ from the $1$, also from the $-8x^5$, also from the $28x^{10}$. Now need the coefficient of $x^{13}$, $x^8$, and $x^3$ from $(1-x)^{-8}$. – André Nicolas Apr 24 '13 at 22:21

$$(x^{2} + x^{3} + x^{4} + x^{5} + x^{6})^{8}=(x^2(1+x+x^2+x^3+x^4))^8=$$ $$=x^{16}\left(\frac{1-x^5}{1-x}\right)^8=x^{16}(1-x^5)^8(1-x)^{-8}=$$ $$=x^{16}\sum_{k=0}^{8}\binom{8}{k}(-x)^{5k}\sum_{l=0}^{\infty}\binom{8+l-1}{l}x^l=$$ $$=\sum_{l=0}^{\infty}\sum_{k=0}^{8}(-1)^{5k}\binom{8+l-1}{l}\binom{8}{k}x^{16+5k+l}$$ $$16+5k+l=21\Rightarrow k=1,l=0 \text{and}k=0,l=5$$ coefficient next $x^{21}$ is $$(-1)^0\binom{8+5-1}{5}\binom{8}{0}+(-1)^5\binom{8+0-1}{0}\binom{8}{1}=\binom{12}{5}-8$$

share|cite|improve this answer
How can you get $-8<0$?:) – Antoine Apr 24 '13 at 22:06
you missed a case: $k=1,l=0$ but also $k=0,l=5$. – gt6989b Apr 25 '13 at 17:02

$(x^{2} + x^{3} + x^{4} + x^{5} + x^{6})^{8} = x^{16}(1+x+x^2+x^3+x^4)^8$, so you should find the coefficient of $x^5$ in $(1+x+x^2+x^3+x^4)^8$. If you write $5$ as sum of $8$ terms $4\geq k_i\geq 0$ in all possible ways, you'll to see in how many ways you can get $x^5$. It is also known what is the number of sums of $k$ nonegative terms which sum up in $n$: $n+k-1 \choose k-1$. In your case, there are $8$ sums $5=0+0+...+5=0+...+0+5+0=...=5+0+..+0$,which you cannot get in the products, because $k_i\leq 4$. So the answer is ${5+8-1} \choose{8-1}$$-8$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.