Se m, n \in \mathbb{N} e n \geq m definimos \binom{n}{m}=\frac{n!}{(n-m)!m!} onde n!=n(n-1) \ldots 3 \cdot 2 \cdot 1 se n \geq 1 e 0!=1. Prove (por indução sobre n ) a seguinte fórmula onde n \geq m \geq 1 são inteiros:
\binom{n}{m-1}+\binom{n}{m}=\binom{n+1}{n}

Passo 1

O enunciado define o coeficiente binomial para n,m\in\mathbb{N} com n\ge m como
\binom{n}{m}=\frac{n!}{(n-m)!\,m!},
e pede para provar, por indução em n, que para inteiros n\ge m\ge1 vale
\binom{n}{m-1}+\binom{n}{m}=\binom{n+1}{m}.
O conteúdo a usar é a definição fatorial de \binom{n}{m} e o princípio de indução.

Passo 2

Base da indução: n=m. Então o lado esquerdo é
\binom{m}{m-1}+\binom{m}{m} =\frac{m!}{1!\,(m-1)!}+\frac{m!}{0!\,m!} =m+1,
pois \binom{m}{m-1}=m e \binom{m}{m}=1. O lado direito é
\binom{m+1}{m} =\frac{(m+1)!}{1!\,m!} =m+1.
Logo a propriedade vale para n=m.

Passo 3

Passo indutivo: suponha que, para algum n\ge m, já tenhamos
\binom{n}{m-1}+\binom{n}{m}=\binom{n+1}{m}.
Queremos mostrar que
\binom{n+1}{m-1}+\binom{n+1}{m} =\binom{n+2}{m}.

Passo 4

Usamos diretamente a definição fatorial para o lado esquerdo em n+1:
\binom{n+1}{m-1} =\frac{(n+1)!}{\bigl((n+1)-(m-1)\bigr)!\,(m-1)!} =\frac{(n+1)!}{(n+2-m)!\,(m-1)!},
\binom{n+1}{m} =\frac{(n+1)!}{\bigl((n+1)-m\bigr)!\,m!} =\frac{(n+1)!}{(n+1-m)!\,m!}.
Somando:
\binom{n+1}{m-1}+\binom{n+1}{m} =\frac{(n+1)!}{(n+2-m)!\,(m-1)!} +\frac{(n+1)!}{(n+1-m)!\,m!}.
Colocando sob um mesmo denominador (n+2-m)!\,m!:
=\frac{(n+1)!\,m}{(n+2-m)!\,m!} +\frac{(n+1)!\,(n+2-m)}{(n+2-m)!\,m!} =\frac{(n+1)!\bigl(m+n+2-m\bigr)}{(n+2-m)!\,m!} =\frac{(n+1)!\,(n+2)}{(n+2-m)!\,m!}.
Reconhecemos que
\frac{(n+1)!\,(n+2)}{(n+2-m)!\,m!} =\frac{(n+2)!}{(n+2-m)!\,m!} =\binom{n+2}{m},
como queríamos.

Resposta

Portanto, por indução em n, mostramos que para todo n\ge m\ge1 vale
\binom{n}{m-1}+\binom{n}{m}=\binom{n+1}{m}.

Exercícios relacionados