Prove por indução a identidade da cola de hockey:
\sum_{k=0}^{n}\binom{k}{r}=\binom{n+1}{r+1}

Passo 1

O enunciado pede para provar, por indução, a identidade
\sum_{k=0}^{n}\binom{k}{r}=\binom{n+1}{r+1},
onde n e r são inteiros não negativos. Dados importantes fornecidos (ou que adotamos como convenção):
  • A soma é sobre k=0,1,\dots,n.
  • Usamos a convenção \binom{k}{r}=0 quando k<r.
  • Queremos uma prova por indução em n (fixando r) que seja válida para todo n\ge r (a identidade também é verdadeira para n<r por causa da convenção).

Passo 2

Antes de começar a indução, vamos relembrar e explicar o que é o coeficiente binomial e algumas propriedades que usaremos.
  • Definição: para inteiros m\ge p\ge 0,
\binom{m}{p}=\frac{m!}{p!(m-p)!}.
Aqui m! significa o fatorial de m (produto 1\cdot2\cdot\ldots\cdot m). Por exemplo, \binom{m}{0}=1 e \binom{m}{m}=1.
  • Propriedade de Pascal (identidade de Pascal): para inteiros m\ge p\ge 0,
\binom{m}{p}+\binom{m}{p+1}=\binom{m+1}{p+1}.
Vou usar essa identidade no passo da indução. Se precisar, depois mostro como prová-la por álgebra de fatoriais.

Passo 3

Escolha da base da indução. Vou induzir em n mantendo r fixo. Uma base conveniente é n=r (ou alternativamente n=0 se r=0, mas n=r cobre o caso geral de forma direta).
  • Avaliando a soma quando n=r:
\sum_{k=0}^{r}\binom{k}{r}.
Pela convenção, \binom{k}{r}=0 para k<r, e \binom{r}{r}=1. Logo a soma vale 1.
  • O lado direito quando n=r é
\binom{r+1}{r+1}=1.
Portanto a identidade vale para n=r:
\sum_{k=0}^{r}\binom{k}{r}=1=\binom{r+1}{r+1}.
Assim a base da indução está comprovada.

Passo 4

Hipótese de indução. Suponha que a identidade seja verdadeira para algum n\ge r; isto é, suponha que
\sum_{k=0}^{n}\binom{k}{r}=\binom{n+1}{r+1}.
Essa é a hipótese que vamos usar para provar a fórmula para n+1.

Passo 5

Passo indutivo: provar que a identidade vale para n+1.
Começamos escrevendo a soma até n+1 em termos da soma até n:
\sum_{k=0}^{n+1}\binom{k}{r} = \left(\sum_{k=0}^{n}\binom{k}{r}\right)+\binom{n+1}{r}.
Pela hipótese de indução, podemos substituir a soma entre parênteses por \binom{n+1}{r+1}. Assim
\sum_{k=0}^{n+1}\binom{k}{r} = \binom{n+1}{r+1}+\binom{n+1}{r}.

Passo 6

Agora aplicamos a identidade de Pascal ao lado direito. A identidade de Pascal diz que, para inteiros adequados,
\binom{n+1}{r+1}+\binom{n+1}{r}=\binom{n+2}{r+1}.
Mostro rapidamente uma derivação algébrica desta igualdade para ficar bem claro (opcional, mas útil):
\binom{n+1}{r+1}+\binom{n+1}{r} = \frac{(n+1)!}{(r+1)!(n-r)!}+\frac{(n+1)!}{r!(n+1-r)!}.
Colocando sobre o mesmo denominador (r+1)!(n+1-r)! (multiplicando numerador e denominador do primeiro termo por n+1-r e do segundo termo por r+1) obtemos
\frac{(n+1)!(n+1-r)}{(r+1)!(n+1-r)!}+\frac{(n+1)!(r+1)}{(r+1)!(n+1-r)!} = \frac{(n+1)!\big((n+1-r)+(r+1)\big)}{(r+1)!(n+1-r)!}.
O somatório interno é (n+1-r)+(r+1)=n+2, então o numerador fica (n+1)!(n+2)=(n+2)!. Assim
\binom{n+1}{r+1}+\binom{n+1}{r}=\frac{(n+2)!}{(r+1)!(n+2-(r+1))!}=\binom{n+2}{r+1}.
Portanto, voltando ao passo anterior,
\sum_{k=0}^{n+1}\binom{k}{r}=\binom{n+2}{r+1}.
Isto mostra que, assumindo a verdade para n, a identidade vale para n+1.

Passo 7

Conclusão da indução. Como mostramos que a identidade vale para a base n=r e que a validade para um n\ge r implica a validade para n+1, por princípio da indução matemática a identidade
\sum_{k=0}^{n}\binom{k}{r}=\binom{n+1}{r+1}
é verdadeira para todo inteiro n\ge r. Pela convenção \binom{k}{r}=0 para k<r, a fórmula também vale para n<r, então vale para todo n\ge0.

Resposta

\sum_{k=0}^{n}\binom{k}{r}=\binom{n+1}{r+1}

Exercícios relacionados