Calculating Nested Sums

Question

I know that $$ \sum^{n}_{k_p=0} \sum_{k_{p-1}=0}^{k_p} ...\sum_{k_1=0}^{k_2}1 = {n+p\choose n} $$

Now I would like to calculate the closed-form solution for the following $$ \sum^{n}_{k_p=1} \sum_{k_{p-1}=1}^{k_p} ...\sum_{k_1=1}^{k_2}x_{k_1} = ? $$

Where $x_i \in Z$.

Any idea how I can solve this?

Perhaps you can come up with a comparison or a visualization about how the first result is obtained. Is there another mathematical problem that it provides an answer to? Perhaps a combinatorics problem? — Matti P., Oct 01 '20 at 09:13
I got the first result from this article https://cs.uwaterloo.ca/journals/JIS/VOL13/Butler/butler7.pdf — Esildor, Oct 01 '20 at 09:24

score 0 · Answer 1 · answered Oct 01 '20 at 09:44

0

HINT:

$$\sum_{k=m}^{n} {k \choose m}={n+1 \choose m+1}$$ So $$\sum_{x=k_1}^{k_2} {x \choose k_1}={k_2+1 \choose k_1+1}$$

Contunue like this.

answered Oct 01 '20 at 09:44

Z Ahmed

43,235

Could you please elaborate more on your second statement? – Esildor Oct 01 '20 at 12:31
I think ${x_k}_1$ is actually ${x \choose k_1}$, then my solution works. – Z Ahmed Oct 01 '20 at 15:49

score 0 · Accepted Answer · answered Oct 03 '20 at 07:38

We have $\displaystyle\sum^{n}_{k_p=1}\sum_{k_{p-1}=1}^{k_p}\ldots\sum_{k_1=1}^{k_2}x_{k_1}=\sum_{k=1}^{n}c_k x_k$, where, using the idea of stars and bars, $$c_k=\#\{(k_2,\ldots,k_p):k\leqslant k_2\leqslant\ldots\leqslant k_p\leqslant n\}=\binom{n-k+p-1}{p-1}.$$

Calculating Nested Sums

2 Answers2