# Finding a generating function for number of existing integers

Let $$k$$ be a positive integer. $$\left \{ a_r \right \} _{r=0}^{\infty}$$ is the number of integers which exist between $$0$$ and $$10^k$$ (i.e integers with no more than $$k$$ digits), such that the sum of their digits is no more than $$r$$.

Find the generating function for $$\left \{ a_r \right \} _{r=0}^{\infty}$$.

A very similar question has been asked here.

It is clear to me that we can define $$f(x) = (1+x+x^2+\dots+x^9)^{k}$$ and this would be a generating function for the problem "how many integers exist with exactly the sum $$r$$". Meaning that would be the coefficient of $$x^r$$.

So using this I believe we can express $$a_r$$, but the question is to find a generating function for $$a_r$$.

So is this still a good direction, or should I think about the problem differently?

• Markus Scheuer’s answer to the question to which you linked contains the generating function that you want: just remove the initial $[x^r]$ (and the final $+1$, if you don’t want to include $10^k$) from the first blue expression. The reasoning is in the material above the formula. May 30, 2020 at 16:15

If we denote the number of integers with sum no more than $$r$$ by $$a_r$$ and the number of integers with sum exactly $$r$$ by $$b_r$$, we have

$$a_r=\sum_{k=0}^rb_k\;.$$

You know the generating function for $$b_k$$. Summing a sequence corresponds to multiplying its generating function by $$\sum_{k=0}^\infty x^k=\frac1{1-x}$$. Thus the generating function you want is

$$\frac{\left(1+\cdots+x^9\right)^k}{1-x}=\frac{\left(1-x^{10}\right)^k}{(1-x)^{k+1}}\;.$$

Note that this is also an intermediate result that Markus Scheuer arrived at in line $$(6)$$ in his answer to the question you linked to. He included $$10^k$$ instead of $$0$$, but the result is the same.

• I lost you at "Summing a sequence corresponds to dividing its generating function by...". Can you explain what you mean by that? this material is pretty new to me May 30, 2020 at 16:48
• @paxtibimarce: I added an intermediate step. Does that make it clearer? May 30, 2020 at 16:50
• I'm still not sure why summing a sequence is the same as multiplying its generating function by this sum. Is this something trivial or could you tell me where I could read about it maybe? May 30, 2020 at 16:56
• I got it, very cool trick :) Thank you May 30, 2020 at 17:06
• @paxtibimarce: \begin{eqnarray} \left[x^r\right]\frac{\left(1-x^{10}\right)^k}{(1-x)^{k+1}} &=& \left[x^r\right]\left(\sum_{j=0}^k\binom kj(-1)^jx^{10j}\right)\left(\sum_{m=0}^\infty\binom{k+m}kx^m\right) \\ &=& \sum_{j=0}^{\left\lfloor\frac r{10}\right\rfloor}\binom kj(-1)^j\binom{k+r-10j}k\;. \end{eqnarray} For $r=18$, this is $\binom{k+18}k-k\binom{k+8}k$. May 30, 2020 at 18:03