Generating function to find the sum of digits How many integers between $30,000$ and $100,000$ have a sum of $15$ or less? 
I was approaching this problem with a generating function: 
$$g(x) = (x^3+x^4+x^5+x^6+x^7+x^8+x^9)(1+x+...+x^9)^4$$
First I'm going to pull out $x^3$ then I would need the coefficients of $x$ to the $15$th, $14$th, $13$th etc correct? If so, can someone help me through finding the coefficients?
Also finding the coefficient of x to the 15th would be the same as finding the coefficient of x to the 12 is I pull out x$^3$
 A: Assuming you are including $30\,000$ and excluding $100\,000$.
Write:
$$\sum_{k=3}^{9}x^k=\frac{x^3-x^{10}}{1-x}\, ,$$
$$\sum_{k=0}^{9}x^k=\frac{1-x^{10}}{1-x}\, .$$
Then
$$g(x)=\left(\sum_{k=3}^{9}x^k\right)\left(\sum_{k=0}^{9}x^k\right)^4=\frac{x^3-x^{10}}{1-x}\left(\frac{1-x^{10}}{1-x}\right)^4$$
Use the operator $(1-x)^{-1}=1+x+x^2+x^3+\cdots$. Then the coefficient of $x^{15}$ in
$$\frac{1}{1-x}g(x)$$
is the required answer.
Now
$$(x^3-x^{10})(1-x^{10})^4=\sum_{r=0}^{4}(-1)^{r}\binom{4}{r}x^{10r+3}-\sum_{r=0}^{4}(-1)^{r}\binom{4}{r}x^{10r+10}\, ,$$
and therefore, since $(1-x)^{-6}=\sum_{k\ge 0}\binom{5+k}{5}x^k$, we have
$$\begin{align}(1-x)^{-1}g(x)=&\left(\sum_{r=0}^{4}(-1)^r\binom{4}{r}x^{10r+3}\right)\left(\sum_{k\ge 0}\binom{5+k}{5}x^k\right)\\[1ex] &- \left(\sum_{r=0}^{4}(-1)^r\binom{4}{r}x^{10r+10}\right)\left(\sum_{k\ge 0}\binom{5+k}{5}x^k\right)\, ,\\[1ex]
=& \sum_{k\ge 0}\left(\sum_{r\ge 0}(-1)^r\binom{4}{r}\binom{k+2-10r}{5}\right)x^{k}\\[1ex] &-\sum_{k\ge 0}\left(\sum_{r\ge 0}(-1)^r\binom{4}{r}\binom{k-10r-5}{5}\right)x^{k}\, .\end{align}$$
Taking the $x^{15}$ coefficient gives
$$\begin{align}[x^{15}](1-x)^{-1}g(x)&=\sum_{r\ge 0}(-1)^r\binom{4}{r}\binom{17-10r}{5}-\sum_{r\ge 0}(-1)^r\binom{4}{r}\binom{10-10r}{5}\, ,\\[1ex]
&=\binom{4}{0}\binom{17}{5}-\binom{4}{1}\binom{7}{5}-\binom{4}{0}\binom{10}{5}\, ,\\[1ex]
&=\binom{17}{5}-4\binom{7}{5}-\binom{10}{5}\, ,\\[1ex]
&=5852\, .\tag{Answer}\end{align}$$
A: We want the number of solutions in integers to
$$x_1+x_2+x_3+x_4+x_5 \le 15$$
where $3 \le x_1 \le 9$ and $0 \le x_i \le 9$ for $2 \le i \le 5$. This is the same as the number of solutions to
$$x_1+x_2+x_3+x_4+x_5+x_6 = 15$$
with the additional constraint $0 \le x_6$.  More generally, we seek the generating function of the number of solutions $a_r$ to 
$$x_1+x_2+x_3+x_4+x_5+x_6 = r$$
with the above constraints.
The generating function is
$$\begin{align}
f(x) &= (x^3 + x^4 + x^5 + \dots +x^9) (1+x+x^2+\dots +x^9)^4(1+x+x^2+\dots) \\
&=x^3 \cdot \frac{1-x^7}{1-x} \cdot \left( \frac{1-x^{10}}{1-x} \right)^4 \cdot \frac{1}{1-x} \\
&=x^3 (1-x^7)(1-x^{10})^4 (1-x)^{-6} \\
&= x^3 (1-x^7) \cdot \sum_{i=0}^4 (-1)^i \binom{4}{i} x^{10i} \cdot \sum_{j=0}^{\infty} \binom{6+j-1}{j} x^j
\end{align}$$
From the final equation above we can extract the coefficient of $x^{15}$:
$$a_{15}=\binom{6+12-1}{12}-\binom{4}{1} \binom{6+2-1}{2}-\binom{6+5-1}{5} = \boxed{5852}$$
