2

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?

MJD
  • 65,394
  • 39
  • 298
  • 580
khernik
  • 1,369

4 Answers4

4

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

Adi Dani
  • 16,949
3

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

Sammy Black
  • 25,273
gt6989b
  • 54,422
  • 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
  • 1
    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
1

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

Antoine
  • 3,439
0

You can make a generating function for the coefficient of $x^5$ in $(1+x+x^2+x^3+x^4)^n$ using the method given here. It is $n(n - 1)(n + 6)(n^2 + 5n + 16)/120$. Now you can substitute $n$ with $8$ to find that the coefficient of $x^{21}$ in your original expression is 784.

Depending on what you want to know about the coefficients for given exponents for your polynomial (and depending on the difference between the smallest two exponents), creating that generating function may or may not seem like too much work. From it, you can find the coefficient of $x^{2 \cdot e + 5}$ in your exponentiated polynomial where $e$ replaces $8$. For example, if $e = 888$ then the coefficient of $x^{2 \cdot 888+5}$ is calculated from the same generating function as $4653353499600$.

smichr
  • 359