Bob's nested sum

We can replace the summand $a_n$ with $\sum_{a_{n+1}=1}^{a_n} 1$ . We are now counting the number of (reversed) sorted vectors of length $n+1$ with maximum value $m$ . If we add $m - 1$ dividers between $n+1$ items, we can indicate how many of each value in $[1, m]$ we pick. There are ${n + 1 + m - 1 \choose m - 1} = {n + m \choose m - 1}$ ways to do this.

So when does ${n + 11 \choose 10}$ divide ${n + 12 \choose 11}$ ?

$\frac{(n+11)!}{10! \times (n+1)!} \vert \frac{(n+12)!}{11! \times (n+1)!}$

$11 \vert (n + 12)$

$11 \vert (n + 1)$

Since $11$ divides $1001$ , the answer is $\frac{1001}{11} = 91$ .

We have $f(m,1) \; = \; \sum_{r=1}^m r \; = \; \tfrac{1}{2}m(m+1) \; = \; {m+1 \choose 2}$ If $n \ge 1$ and $f(m,n) \; = \; {m+n \choose n+1}$ then $f(m,n+1) \; = \; \sum_{r=1}^m f(r,n) \; = \; \sum_{r=1}^m {r+n \choose n+1} \; =\; {m+n+1 \choose n+2}$ Hence, by induction on $n$ , $f(m,n) \,=\, {m+n \choose n+1}$ , and hence $\frac{f(12,n)}{f(11,n)} \; = \; \frac{n+12}{11}$ Thus we want to know the number of $n$ between $1$ and $1000$ such that $11$ divides $n+12$ , namely such that $n \equiv 10$ modulo $11$ . Possible solutions are $10,21,\ldots,1000=10+90\times11$ , and so there are $91$ values of $n$ .

f(m, n) is equivalent to the binomial coefficient of (n + m, m - 1). Therefore:

$f(11, n) = bin(11 + n, 10) = \frac{(11 + n)!}{10! * (n + 1)!}$ $f(12, n) = bin(12 + n, 11) = \frac{(12 + n)!}{11! * (n + 1)!}$

"|" denotes "is divisible by".

Dividing these two equations and applying some simple algebra:

$f(12, n) / f(11, n) = \frac{n + 12}{11}$

Clearly this only holds when $n == 10 (mod 11)$ , and there are 91 such values below 1000.

Examining the definition for $f$ , we observe that if $n>1$ , then $f(m+1,n) = f(m,n) + f(m+1,n-1)$

Also we find that $f(1,n) = 1$ $f(m,1)=(1+2+...+m)$

Now, I recognized this as the iterative rule and the boundary conditions for Pascal's Triangle: each element is the sum of the two elements above it. The general formula for an element of this triangle is $f(m,n) = {m+n \choose m-1}$

To prove this, we can inspect that it fulfils the initial conditions correctly. Also, the iterative step $\begin{aligned} f(m,n) + f(m+1,n-1) &= {m+n \choose m-1} + {m+n \choose m} \\ &= {m+n+1 \choose m} \\ &= f(m+1,n) \end{aligned}$

Moving on, we have $\begin{aligned} f(12,n) &= {12+n \choose 11} \\ &= { (12+n)! \over 11!(n+1)!} \\ &= { (11+n)! \over 10!(n+1)} {12+n \over 11} \\ &= f(11,n) {12+n \over 11} \end{aligned}$

So we simply have to find how many values of $n$ satisfy $11 \mid n+12$ .

$n$ can range from $10 = 11*1-1$ to $1000 = 11*91-1$ so there are $\boxed{91}$ values.