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

Question

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.

Answer 1

Note that$ a_m=\sum_1^{a_m}1$

Your question is now that of finding the size of the set;

$n\geq a_m \geq a_{m-1}\geq...\geq a_1 \geq 1$

Note that this is the same as finding no.s $x_i$ such that $n\geq x_i\geq0$ and $\sum x_i=n$ ( Think differences). Now can you do it? I may have made a mistake , here or there but the idea's fine I think.

Answer 2

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