# Binomial Coefficient Recusions

Let m and j be non-negative integers. Define $S^{0}_{m} = 1$ and:

$S^{j}_{m} = \displaystyle\sum\limits_{i=1}^{m} S_{i}^{j-1}$

Show via induction:

$S_{m}^{j} = {m+j-1 \choose j}$

I can obviously show the first step, but, I have no clue how to proceed from here. On what can I perform induction? How?

First observe that \begin{align*} S_{m}^j - S_{m-1}^j &= \left(\sum_{i=1}^{m}S_{i}^{j-1}\right) - \left(\sum_{i=1}^{m-1}S_{i}^{j-1}\right) = S_{m}^{j-1} \end{align*} since all but one of the terms cancel. Now we can prove the claim by strong induction on $n := m+j$. Fix some $n$ and suppose $S_\ell^k = \binom{\ell+k-1}{k}$ for all $\ell,k$ with $\ell + k < n$. Given $m,j$ with $m + j = n$, then \begin{align*} S_m^j &= S_{m-1}^{j} + S_{m}^{j-1} = \binom{(m-1) + j -1}{j} + \binom{m + (j - 1) - 1}{j - 1}\\ &= \binom{m + j - 2}{j} + \binom{m + j - 2}{j - 1} = \binom{m + j - 1}{j} \end{align*} where the first equality holds by our initial observation.