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

-

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

-
induction, I believe? –  Vincent Tjeng Mar 3 '13 at 14:28
@VincentTjeng oops...thanks. –  Yimin Mar 3 '13 at 14:29

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8735467195510864, "perplexity": 850.8264731515051}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-27/segments/1435375095711.51/warc/CC-MAIN-20150627031815-00270-ip-10-179-60-89.ec2.internal.warc.gz"}