Bajo la hipótesis de inducción que se cumple para m, vamos a bosquejar cómo sería el paso inductivo. (El caso base es trivial y se deja al lector.)
En $(1+x)^{m+1}=(1+x)(1+x)^m$, el coeficiente de $x^k$, es decir, $\binom{m+1}{k}$, se forma a partir de los coeficientes de $x^k$ y $x^{k+1}$ en la expansión de $(1+x)^m.$
Para verlo basta reconstruir los dos términos $k$ y $k+1$ en la expansión de $(1+x)^m$, y
multiplicarlos por $(1+x)$ de acuerdo a la regla distributiva: $$(1+x)[\ldots \binom{m}{k-1}x^{k-1}+\binom{m}{k}x^k+\ldots]$$
Claramente, el coeficiente de $x^k$ es la suma $\binom{m}{k-1}+\binom{m}{k}$. Lo cual es el resultado de multiplicar por 1 el término $\binom{m}{k}x^k$ y por $ x$ el término $\binom{m}{k-1}x^{k-1}.$
Pero la suma $\binom{m}{k-1}+\binom{m}{k}$ se puede interpretar como la suma de las cardinalidades de dos clases de subconjuntos del conjunto $\{1,2,\ldots,m\}$: la de los subconjuntos de tamaño $k-1$ y la de los subconjuntos de tamaño $k$. Y por la regla de formación de los coeficientes en el triángulo de Pascal, esta suma es $\binom{m+1}{k}$. (Esta identidad permite realizar con éxito el paso inductivo en la demostración por inducción.)
Es posible, sin embargo, dar una demostración combinatoria de esa identidad muy básica. En $\binom{m+1}{k}=\binom{m}{k-1}+\binom{m}{k}$ el lado izquierdo cuenta los subconjuntos de tamaño $ k$ tomados de $\{1,2,\ldots,m,m+1\}$.
Pero esos subconjuntos se pueden contar de otra manera (el método se llama doble conteo): se pueden clasificar en aquéllos que contienen el 1 y aquéllos que no lo contienen. (Esta forma de clasificación se llama método del elemento señalado.)
Los que contienen el 1 son tantos como \binom{m}{k-1} --dado que podemos ignorar el 1 y verlos como subconjuntos de tamaño $k-1$, tomados de $\{2,\ldots,m,m+1\}$. Y los que no lo contienen son tantos como $\binom{m}{k}$ --dado que son subconjuntos de tamaño $k$ tomados de$\{2,\ldots,m,m+1\}$. Como las dos clases son disjuntas y entre las dos cubren todos los casos, se puede aplicar el principio aditivo.
(La prueba completa por inducción se deja al lector --así como otros detalles que pudieran haber sido omitidos aquí.)
