Recusiones del coeficiente binomial

Question

Sean m y j números enteros no negativos. Definamos $S^{0}_{m} = 1$ y:

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

Mostrar a través de la inducción:

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

Obviamente puedo mostrar el primer paso, pero, no tengo idea de cómo proceder a partir de aquí. ¿En qué puedo realizar la inducción? ¿Cómo?

Answer 1

Primero observe que \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*} ya que todos los términos, excepto uno, se cancelan. Ahora podemos demostrar la afirmación por inducción fuerte sobre $n := m+j$ . Arreglar algunos $n$ y supongamos $S_\ell^k = \binom{\ell+k-1}{k}$ para todos $\ell,k$ con $\ell + k < n$ . Dado $m,j$ con $m + j = n$ entonces \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*} donde la primera igualdad se mantiene por nuestra observación inicial.