Prueba sobre combinaciones y subconjuntos

Question

Deja que $\Omega_n={1,2,....,n}$ y para $0 \leq k \leq n$ deja que $\Omega^{\{k\}}$ sea la colección de subconjuntos de k elementos de $\Omega_n$

Define el número $S^{n}_{k}$ como la cardinalidad de $\Omega^{\{k\}}_n$

Usa la inducción en n para probar para todo $n \in N$ y $k \in Z$ con $0 \leq k \leq n$ que $S^{n}_{k}={n\choose k}$ por inducción en n: Demuestra directamente para todo n, $S^{n}_0={n \choose 0}=1$. Demuestra el paso inductivo usando las identidades $S^{n}_{k} + S^{n}_{k+1}= S^{n+1}_{k+1}$ y ${n \choose k} + {n \choose k+1}={n+1 \choose k+1}$

Estoy bien con el caso base pero tengo problemas para demostrar la hipótesis inductiva

Enfoque Asume para un $n \in N$ y $k \in Z$ con $0 \leq k \leq n$ que $S^{n}_{k}= {n \choose k}$

Necesito mostrar que $S^{n+1}_k={n+1 \choose k}$

$S^{n+1}_k = S^{n}_{k}+S^{n}_{k-1}$

No sé cómo abordar el $S^{n}_{k-1}$

Answer 1

Pista: Ahora tienes $1,2,\dots,n+1$, primero considera cuántos conjuntos en $\Omega^{\{k\}}_{n+1}$ no contienen el elemento $n+1$, y luego cuenta cuántos conjuntos en $\Omega^{\{k\}}_{n+1}$ contienen el elemento $n+1