Hola
Hola, necesito ayuda para resolver esta identidad por doble conteo.
Editado \( \LaTeX \) por moderador
Demostrar que, para todo \( n,m \in \mathbb{N} \) se cumple que
\( \displaystyle \sum_{k=0}^n {n \choose k} m^k = (m+1)^n \)
1) Como te dice ani_pascual puedes usar simplemente la fórmula del Binomio de Newton:
\( (a+b)^n=\displaystyle\sum_{k=0}^n{}{n \choose k}a^{n-k}b^k \)
para \( a=1 \), \( b=m. \)
2) Puedes también hacer la demostración de ese resultado más general para tu caso particular, por inducción.
Spoiler
El paso inductivo sería:
\( (m+1)^{n+1}=(m+1)(m+1)^n=(m+1)\displaystyle \sum_{k=0}^n {n \choose k} m^k =\\
\qquad =\displaystyle \sum_{k=0}^n {n \choose k} m^{k+1}+\displaystyle \sum_{k=0}^n {n \choose k}=\\
\qquad =\displaystyle \sum_{k=1}^{n+1} {n \choose k-1} m^{k}+\displaystyle \sum_{k=0}^n {n \choose k}m^{k}=m^{n+1}+\displaystyle \sum_{k=1}^n \left({n \choose k-1} +{n \choose k} \right)m^{k}+1=\\
\qquad =\displaystyle{n+1\choose n+1}m^{n+1}+\displaystyle \sum_{k=1}^n{n+1\choose k} m^{k}+{n+1\choose 0}m^0=\\
\qquad=\displaystyle \sum_{k=0}^{n+1} {n+1 \choose k} m^k \)
3) Otra opción es una prueba que interpreta desde el punto de vista combinatorio las fórmulas.
\( m^k \) es el número de funciones entre un conjunto de \( k \)sobre en un conjunto de \( m \) elementos.
Entonces:
\( (m+1)^n \) el el número de funciones entre un conjunto \( A \) de \( n \) elementos sobre un conjunto \( B \) de \( m+1 \) elementos. Este número de funciones pueden contarse así. Si los elementos del conjunto final son \( B=\{b_1,\ldots,b_m,b_{m+1}\} \).
\( \displaystyle\sum_{s=0}^n{}\text{Funciones que llevan exactamente $s$ elementos de $A$ en $b_{m+1}$} \)
Ahora las funciones que llevan exactamente $$s$$ elementos de $$A$$ en $$b_{m+1}$$ se cuentan: primero enumerando las formas de elegir que $$s$$ elementos de $$A$$ irán sobre $$b_{m+1}$$: \( \displaystyle {n\choose s} \) multiplicado por las funciones entre los \( n-s \) elementos restantes sobre los \( m+1 \) primeros elementos de \( B \) que son \( m^{n-s} \).
Queda:
\( \displaystyle\sum_{s=0}^n{}{n\choose s}m^{n-s}=\displaystyle\sum_{k=0}^n{}{n\choose n-k}m^{k}=\displaystyle\sum_{k=0}^n{}{n\choose k}m^{k} \).
Saludos.
