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 xk, es decir, (m+1k), se forma a partir de los coeficientes de xk y xk+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)[…(mk−1)xk−1+(mk)xk+…]
Claramente, el coeficiente de xk es la suma (mk−1)+(mk). Lo cual es el resultado de multiplicar por 1 el término (mk)xk y por x el término (mk−1)xk−1.
Pero la suma (mk−1)+(mk) se puede interpretar como la suma de las cardinalidades de dos clases de subconjuntos del conjunto {1,2,…,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 (m+1k). (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 (m+1k)=(mk−1)+(mk) el lado izquierdo cuenta los subconjuntos de tamaño k tomados de {1,2,…,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,…,m,m+1}. Y los que no lo contienen son tantos como (mk) --dado que son subconjuntos de tamaño k tomados de{2,…,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í.)
