# Digit sum formula $< n$ motivation

Quoting:

We define $f(d, n)$ to be the number of integers of up to $d$ decimal digits with digit sum less than or equal to $n$. It can be seen that this function is given by the formula $$f(d,n)=\sum_{i=0}^d(-1)^i\binom{d}i\binom{n+d-10i}d\;.$$

How is this derived? And surely the function requires binomials with negative arguments?

-
Edited to reflect this – sam keays Apr 25 '12 at 14:57

The number of solutions of $x_1+x_2+\ldots+x_d=m$ in non-negative integers is $\binom{m+d-1}m$. (If this is not familiar, see this article.) If we could use arbitrarily large digits, not just $0,\dots,9$, this would be the number of non-negative integers of at most $d$ digits with digit sum $m$. Since we want to allow all digits sums from $0$ through $n$, we want $$\sum_{m=0}^n\binom{m+d-1}m=\sum_{m=0}^n\binom{m+d-1}{d-1}=\binom{n+d}d\tag{1}$$ by a standard binomial coefficient identity; and since $\binom{d}0=1$, $(1)$ is the $i=0$ term of the sum

$$f(d,n)=\sum_{i=0}^d(-1)^i\binom{d}i\binom{n+d-10i}d\;.\tag{2}$$

The other terms of $(2)$ correct for the inclusion in $(1)$ of numerals using digits greater than $9$, i.e., for the inclusion of solutions to $x_1+\ldots+x_d=m$ with some $x_k>9$. This is a standard inclusion-exclusion argument, but I’ve included some of the details below.

To start, fix $k$ with $1\le k\le d$. There is a natural bijection between solutions in non-negative integers to $x_1+\ldots+x_d=m$ with $x_k\ge 10$ and solutions in non-negative integers to $x_1+\ldots+x_d=m-10$. Arguing as before, and ignoring the possibility that some $x_i$ may exceed $9$, we get $\binom{(m-10)+d-1}{m-10}$ such solutions, and summing over $m\le n$ yields a total of $\binom{n+d-10}d$ solutions counted in $(1)$ but having $x_k\ge 10$. Moreover, there are $\binom{d}1=d$ possible values of $k$, each of which provides $\binom{n+d-10}d$ ‘bad’ solutions, so we must subtract $\binom{d}1\binom{n+d-10}d$ from the first approximation in $(1)$. Our second approximation to the desired number is therefore $$\binom{d}0\binom{n+d}d-\binom{d}1\binom{n+d-10}d\;.\tag{3}$$

Unfortunately, $(3)$ overcorrects: some of the ‘bad’ solutions counted in $(1)$ exceed $9$ in two terms and have been removed twice in $(2)$, so they have to be added back in. The reasoning is as before. For any pair of indices $i,k$ with $i\ne k$ and any sum $m$, there is a natural bijection between solutions in non-negative integers to $x_1+\ldots+x_d=m$ with $x_i,x_k\ge 10$ and solutions in non-negative integers to $x_1+\ldots+x_d=m-2\cdot10$. The total correction for this pair of indices is therefore $\binom{n+d-2\cdot10}d$, and there are $\binom{d}2$ such pairs of indices, so the overall correction is $\binom{d}2\binom{n+d-2\cdot 10}d$, giving a third approximation of $$\binom{d}0\binom{n+d}d-\binom{d}1\binom{n+d-10}d+\binom{d}2\binom{n+d-2\cdot 10}d\;.\tag{4}$$

This again overcorrects, because some of the original solutions are ‘bad’ in three places and got added back into $(4)$ for two pairs of indices, so we have to subtract another correction. When all of the corrections have been made, we’re left with $(2)$, as desired.

The binomial coefficients with negative upper number are evidently defined to be $0$ for purposes of this calculation, so they cause no trouble.

Added: This is not the usual definition, so the notation is a bit sloppy: the usual definition, good for arbitrary complex $z$ and non-negative integer $k$, is $$\binom{z}k=\frac{z^{\underline k}}{k!}\;,$$ where $z^{\underline k}$ is the falling $k$ power of $z$, $z(z-1)(z-2)\dots(z-k+1)$.

-
But the usual definition of $x\choose n$ is the quotient of $x(x-1)(x-2)\cdots(x-n+1)$ and $n!$, whether $x$ is positive, negative, integer, decimal, real, complex, whatever. – Gerry Myerson Apr 25 '12 at 22:37
Thanks, that's actually not so difficult to understand. For some reason I just find it often hard to visualise the binomial coefficient and what it does, there often feels something algebraically counter-intuitive about it. – sam keays Apr 26 '12 at 12:19
@Gerry: Yes, and I really should make more of a point of that. Done now. – Brian M. Scott Apr 26 '12 at 13:07