Foro de Práctico

Hola,

Estoy teniendo problemas para probar esta igualdad: $\mathrm{Sob}(m,n) = \sum_{i=1}^{m-(n-1)} \binom{m}{i} \mathrm{ Sob}(m-i, n-1)$

Se pide hacerlo por regla de la suma y regla del producto. Lo que estoy haciendo es considerar un caso $i$ genérico, que consta de las siguientes etapas:

1. Elijo $i$ elementos de $\{1, \dots, m\}$, para lo cual hay $\binom{m}{i}$ formas distintas de hacerlo.
2. Elijo un elemento $y \in \{1, \dots, n\}$, por lo que hay $n$ formas de hacer esto.
3. Defino una función sobreyectiva $f: \{1, \dots, m\}- \{ x_i | x_i \text{ fue elegido en la etapa 1} \} \rightarrow \{1, \dots, n\}-\{ y \}$, lo cual tiene $\mathrm{Sob}(m-i,n-1)$ formas posibles.
4. De los $x_i$ elegidos en la etapa 1, elijo uno ($i$ formas de hacerlo) y le asigno como imagen el valor de $y$; de esta forma, todos los elementos del codominio $\{1, \dots, n\}$ ya tienen preimagen.
5. A los restantes valores del dominio (los $i-1$ $x_i$ que aún no tienen imagen), les asigno cualquier valor del codominio (con repetición posible), por lo que hay $n^{i-1}$ formas de hacer esto.

Luego, por la regla del producto, esta etapa genérica tiene $\binom{m}{i}\mathrm{Sob}(m-i,n-1)in^{i}$. Ahora bien, ¿cuántas etapas hay? Entiendo que el primer argumento de la función $\mathrm{Sob}$ debe ser mayor o igual a uno (si no, su significado no tiene sentido), y además, para que esta función no valga cero, su primer argumento debe ser mayor o igual al segundo. Luego, imponiendo esto, se tiene que $i \leq m - n + 1$. Por lo tanto, por la regla de la suma:

$\mathrm{Sob}(m,n) = \sum_{i=1}^{m-(n-1)} \binom{m}{i} \mathrm{ Sob}(m-i, n-1)in^{i}$

¿Dónde está mi error? Seguramente no se cumpla alguna condición necesaria de la regla de la suma o de la regla del producto, pero no logro verlo. Tampoco logro ver cómo sería el razonamiento para llegar al resultado correcto. Desde ya, muchas gracias.

Saludos