Q:

Show $\sum_{a_1=1}^n\sum_{a_2=1}^{a_1}\sum_{a_3=1}^{a_2}...\sum_{a_m=1}^{a_{m-1}}a_m=\frac 1 {(m+1)!}\prod_{k=0}^m(n+k)$.

When playing around Wolfram Alpha, I find something interesting:
$\displaystyle \sum_{a_1=1}^n a_1=\frac 1 2 n(n+1)$
$\displaystyle \sum_{a_1=1}^n\sum_{a_2=1}^{a_1} a_2=\frac 1 6 n(n+1)(n+2)$
$\displaystyle \sum_{a_1=1}^n\sum_{a_2=1}^{a_1}\sum_{a_3=1}^{a_2} a_3=\frac 1 {24} n(n+1)(n+2)(n+3)$
I then deduce that $\displaystyle \sum_{a_1=1}^n\sum_{a_2=1}^{a_1}\sum_{a_3=1}^{a_2}...\sum_{a_m=1}^{a_{m-1}}a_m=\frac 1 {(m+1)!}\prod_{k=0}^m(n+k)$. But I don't know how to prove or disprove this. Please help. Thank you.

A:

Try to prove by induction.
Take
$S_m(n) = \sum_{a_1=1}^n\sum_{a_2=1}^{a_1}\sum_{a_3=1}^{a_2}...\sum_{a_m=1}^{a_{m-1}}a_m$,
$S_{m+1}(n)= \sum_{a_0=1}^n\sum_{a_1=1}^{a_0}\sum_{a_2=1}^{a_1}\sum_{a_3=1}^{a_2}...\sum_{a_m=1}^{a_{m-1}}a_m=\sum_{a_0=1}^n S_m(a_0)$.

