6
$\begingroup$

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!

  • 2
    The sum gives an answer to the [stars ans bars problem](http://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29) with the closed form expression $S_r^q = \binom{q+r-1}{r}$.2012-08-01

1 Answers 1

11

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


Inductive Reasoning

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

  • 0
    Thanks! Could you please show the steps for the inductive reasoning? Thanks again.2012-08-02