# Finding a coefficient using generating functions

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?

-

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

-
Yes, that's true, and the last part ( $\frac{1}{(1-x)^{8}}$ ) is a generating function now, but..and then..uhm..well...one 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$$

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

-