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

I missed this. This question has already been answered. https://math.stackexchange.com/questions/1084850/how-to-simplify-sum-a-1-1n-sum-a-2-1a-1-sum-a-3-1a-2-dots-sum-a?rq=1 — , Apr 18 '17 at 12:07

score 0 · Answer 1 · answered Apr 18 '17 at 12:03

0

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

answered Apr 18 '17 at 12:03

Dirk

6,359

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

1 Answers1