The Horror of the Nested Sum

First, note that $f(m,n)$ can be defined recursively as follows. $\begin{cases} f(m, n)= m-1 & \text{if } n=1 \\ f(m, n) = \sum \limits_{k=1}^{m-1} f(m-k, n-1) & \text{if } n>0 \end{cases}$ We try to find another function which satisfies the same recursion.

Let $g(m, n)$ denote the number of positive integer solutions to the equation $a_1 + a_2 + \cdots + a_{n+1}= m$ . Note that when $n=1$ , $g(m,n)$ is simply the number of positive integer solutions to $a_1+a_2= m$ . Each choice of $a_1$ determines a unique $a_2$ , and $a_1$ must lie in the range $[1, m-1]$ for both $a_1$ and $m-a_1$ to be positive, which shows that $g(m, 1)= m-1$ .

We shall now show that $g(m,n)= \sum \limits_{k=1}^{n-1} g(m-k, n-1)$ . Consider the equation $a_1 + a_2 + \cdots + a_{n+1}= m$ . Let's say we fix the variable $a_{n+1}$ . If $a_{n+1}=1$ , the equation becomes $a_1+a_2+\cdots + a_n= m-1$ , which has $g(m-1, n-1)$ solutions by our definition. Similarly, if $a_{n+1}= 2$ , the equation becomes $a_1+a_2+\cdots + a_n= m-2$ , which has $g(m-2, n-1)$ solutions. In general, if $a_{n+1}=k$ , the equation $a_1 + a_2 + \cdots + a_n = m-k$ has $g(m-k, n-1)$ solutions. Since $a_{n+1} \in \{1, 2, \cdots , m-1\}$ , we conclude that $g(m, n) = \sum \limits_{k=1}^{m-1} g(k-1, n-1)$ .

Notice that $g(m, n)$ has the same initial values of $f(m, n)$ and they both follow the same recursion. A simple inductive argument shows that $f(m, n)$ and $g(m, n)$ are identically equal. But from stars and bars formula, we know that $g(m, n)= \dbinom{m+n}{n+1}$ . Hence, $f(m, n)= \dbinom{m+n}{n+1} \ \forall \ (m, n) \in \mathbb{N}^2$ .

Then, note that $\dfrac{f(12,n )}{f(11, n)}= \dfrac{\dbinom{12+n}{n+1}}{\dbinom{11+n}{n+1}} = \dfrac{\dfrac{(12+n)!}{11!}}{\dfrac{(11+n)!}{10!}}= \dfrac{12+n}{11}.$

It is easy to verify that there are $\boxed{91}$ values of $n$ in the range $[1, 1000]$ which make the $\dfrac{12+n}{11}$ an integer.