# Sums of sums of sums of…of numbers

If we introduce the following notation

$$S_r^q=\overbrace{\sum_{a_{r-1}=1}^q\sum_{a_{r-2}=1}^{a_{r-1}}\cdots\sum_{a_1=1}^{a_2}\sum^{a_1}}^{\mbox{a total of r sums}}1$$

for example, $S^q_1=q$, $S^q_2=q(q+1)/2$ and so on, then one can show that

$$S^p_{q-1}=S^q_{p-1},$$

where $p$ and $q$ are positive integers. What is the simplest proof of this? I know of one but suspect that there exists simpler ones. Is there any generalisation of this statement. Can somebody also direct me to some references on related material. Thanks a lot in advance!

-
The sum gives an answer to the stars ans bars problem with the closed form expression $S_r^q = \binom{q+r-1}{r}$. – Sasha Aug 1 '12 at 21:58

Using the formula $$\sum_{k=0}^n\binom{k}{j}=\binom{n+1}{j+1}\tag{1}$$ we get inductively that $$S_q^p=\binom{p+q-1}{q}\tag{2}$$ Thus, we have $$S_{q-1}^p=\binom{p+q-2}{q-1}$$ and $$S_{p-1}^q=\binom{p+q-2}{p-1}$$ and your identity is just the common symmetry identity $\displaystyle\binom{n}{k}=\binom{n}{n-k}$.
1. $(2)$ holds for $q=\color{#C00000}{1}$ because $\displaystyle S_{\color{#C00000}{1}}^p=p=\binom{p+\color{#C00000}{1}-1}{\color{#C00000}{1}}$
2. Assume $(2)$ holds for some $q$. By definition, assumption, and $(1)$, \begin{align} S_{q+1}^p &=\sum_{k=1}^pS_q^k\\ &=\sum_{k=1}^p\binom{k+q-1}{q}\\ &=\binom{p+q}{q+1}\\ &=\binom{p+(q+1)-1}{q+1} \end{align} Therefore, $(2)$ holds for $q+1$.