Prove a sum of sums equals n choose k

Question

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<m \choose m}=0$$

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

Answer 1

Your initial expression could be rewritten as

$$\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.

Answer 2

Hint:

$$ \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} $$