Find the coefficient of $x^{32}$ in $(x^3 +x^4 +x^5 +x^6 +x^7)^7$

Question

I don't understand the explanation in the book and why the final answer looks the way it does. I know I am supposed to factor and it will equal to $(x^3(1+x+\cdots+x^4))^7$. But after that, I am really confused about what happens. Can someone explain this problem step by step. Thank you!

Answer 1

A strategy for solving problems like this one is to try to rewrite the expression as the quotient of a polynomial in $x$ and some power of $1-x$. You can then use either Newton’s generalized binomial theorem or the identity $${1\over(1-s)^{k+1}} = \sum_{n=0}^\infty \binom{n+k}k s^n$$ to expand the denominator as a power series and write the coefficient that you seek as a linear combination of a small number of binomial coefficients.

Before plunging into the calculations, a handy bit of notation: $[x^n]f(x)$ stands for “the coefficient of $x^n$ in the power series for $f(x)$.” The brackets “absorb” powers of $x$, that is, $[x^n]x^mf(x) = [x^{n-m}]f(x)$. Basically, pulling out a factor of $x^m$ lets you reduce the exponent in the bracket—the coefficients are shifted down $m$ places in what remains. Diving right in, then,

$$\begin{align} [x^{32}](x^3+x^4+x^5+x^6+x^7)^7 &= [x^{32}]\left(x^3(1+x+x^2+x^3+x^4)\right)^7 \\ &= [x^{32}]x^{21}(1+x+x^2+x^3+x^4)^7 \\ &= [x^{11}](1+x+x^2+x^3+x^4)^7 \\ &= [x^{11}]\left({1-x^5 \over 1-x}\right)^7 \\ &= [x^{11}]{\binom70-\binom71x^5+\binom72x^{10}-\dots \over (1-x)^7} \\ &= \binom70[x^{11}]{1\over(1-x)^7} - \binom71[x^6]{1\over(1-x)^7} + \binom72[x]{1\over(1-x)^7} \\ &= \binom70\binom{17}6 - \binom71\binom{12}6 + \binom72\binom{7}6 \\ &= 6055.\end{align}$$

The absorption rule is used in lines 3 and 6. When expanding the numerator using the binomial theorem in line five, we can ignore all terms that involve powers of $x$ greater than $11$ since they won’t contribute anything to the final result.