Ways to prove $\sum_{A_k}^n \sum_{A_{k-1}}^{A_k} \sum_{A_{k-2}}^{A_{k-1}} \cdots \sum_{A_1}^{A_2} A_1 = {n+k \choose k+1}$

Question

Ways to prove $$\sum_{A_k\ =1}^n\ \sum_{A_{k-1} \ \ =1}^{A_k} \ \sum_{A_{k-2}\ \ =1}^{A_{k-1}} \ \cdots \ \sum_{A_1=1}^{A_2} A_1 = {n+k \choose k+1} $$ Something I found messing around a while ago. Proved it once, forgot, and can't get back up again. Sum from right to left.

t. neet

Answer 1

Induction on $k$ leaves us to prove that $$\sum_{i=1}^n {k+i \choose k+1} = {n+k \choose k+1}$$ holds for all $k,n$. This should not be that difficult with another induction...