# Prove a sum of sums equals n choose k

In some research I'm doing, I've come across some coefficients I'm calling $$\alpha^{n}_{j}$$, where $$\alpha^{n}_{j} = \sum_{k_1 = 1}^{n} \sum_{k_2 = 1}^{n-k_1} ... \sum_{k_j = 1}^{n - k_1 - k_2 -... - k_{j-1}}1, \quad \text{ where }\quad \sum_{m=1}^{p<1}1 = 0$$

For every coefficient I have computed, I've found $$\alpha_{j}^{n} = {n\choose j}$$. However, I am struggling to prove this. Does anybody have any advice?

By looking at some combinations, I've convinced myself of the following:

$$\alpha_{j}^{n} = 1 + \sum_{k = 1}^{n-j} \sum_{l = 1}^{k} {k-1 \choose l-1}{j \choose l}, \quad \text{ where }\quad{p

I'm not sure what the next step to proving this would be though, or if this is the right track.

• Hi, welcome. What does $\sum_{m=1}^{p < 1} 1 = 0$ mean? And do you mean $\alpha_j^n = \binom{n}{j}$? – Matthew Leingang May 24 at 14:54
• @MatthewLeingang I assume he means that the sum with lower bound $1$ and upper bound anything less than $1$ results in the empty-sum which evaluates to zero. – JMoravitz May 24 at 14:56
• Aha, so it's not a constraint, but a notational convention. – Matthew Leingang May 24 at 14:57
• for p less than m any possible value of m, the sum will be 0. So anytime $k_1 +k_2 +... + k_i \geq n$, there will be no contribution to the total sum. – Willyazaa May 24 at 14:57
• @saulspatz yep, thanks. I fixed it – Willyazaa May 24 at 14:59

$$\sum_{k_1+k_2+\cdots+k_j\leq n}1$$ where additionally you require each $$k_i\geq 1$$, i.e. it counts the number of ordered tuples $$(k_1,\ldots,k_j)$$ with sum at most $$n$$.
Now there is a transformation between such tuples and subsets of $$1,...,n$$ of size $$j$$. The numbers $$k_1,k_1+k_2,k_1+k_2+k_3,...$$ are all different and in the range $$1,...,n$$. Conversely for any set of $$j$$ numbers between $$1$$ and $$n$$ there is such a tuple: make $$k_1$$ the smallest number in the list, $$k_2$$ the difference between the smallest and second-smallest, and so on. So there is a 1-to-1 correspondence between these tuples and combinations of $$j$$ numbers from $$1,...,n$$ - but the number of those is $$\binom nj$$ by definition.
\eqalign{ & \sum\limits_{0\, \le \,k\, < \,n} 1 = n = \left( \matrix{ n \cr 1 \cr} \right) \cr & \sum\limits_{0\, \le \,k\, < \,n} {\sum\limits_{0\, \le \,j\, < \,n - k} 1 } = \sum\limits_{0\, \le \,k\, < \,n} {\left( \matrix{ n - k \cr 1 \cr} \right)} = \sum\limits_{0\, < \,k\, \le \,n} {\left( \matrix{ k \cr 1 \cr} \right)} = \sum\limits_k {\left( \matrix{ n - k \cr n - k \cr} \right)\left( \matrix{ k \cr k - 1 \cr} \right)} = \left( \matrix{ n + 1 \cr n - 1 \cr} \right) = \left( \matrix{ n + 1 \cr 2 \cr} \right) \cr & \quad \vdots \cr}
while, starting the sums from $$1$$
\eqalign{ & \sum\limits_{1\, \le \,k\, \le \,n} 1 = n = \left( \matrix{ n \cr 1 \cr} \right) \cr & \sum\limits_{1\, \le \,k\, \le \,n} {\sum\limits_{1\, \le \,j\, \le \,n - k} 1 } = \sum\limits_{1\, \le \,k\, \le \,n} {\left( \matrix{ n - k \cr 1 \cr} \right)} = \sum\limits_{0\, \le \,k\, \le \,n - 1} {\left( \matrix{ k \cr 1 \cr} \right)} = \sum\limits_k {\left( \matrix{ n - 1 - k \cr n - 1 - k \cr} \right)\left( \matrix{ k \cr k - 1 \cr} \right)} = \left( \matrix{ n \cr n - 2 \cr} \right) = \left( \matrix{ n \cr 2 \cr} \right) \cr}