Exercício 40. Prove por indução a identidade da cola de hockey:
\sum_{k=0}^{n}\binom{k}{r}=\binom{n+1}{r+1}
Mostre o uso da regra da simplificação nos coeficientes binomiais.

Passo 1

O enunciado pede para provar por indução a identidade
\sum_{k=0}^{n}\binom{k}{r}=\binom{n+1}{r+1}
para inteiros não negativos n e r. Além disso, é solicitado que se mostre o uso da “regra da simplificação” nos coeficientes binomiais (a identidade de Pascal).
Informações relevantes que temos e que podemos usar:
  • A definição usual do coeficiente binomial para 0\le k\le n:
\binom{n}{k}=\frac{n!}{k!(n-k)!}.
  • A convenção padrão \binom{n}{k}=0 quando k<0 ou k>n.
  • A identidade de Pascal (regra da simplificação):
\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1},
que devemos usar explicitamente na prova por indução.

Passo 2

Primeira coisa: entender e provar a identidade de Pascal que vamos usar. Vou mostrar-a por manipulação de fatoriais (mas há também provas combinatórias):
Começando do lado direito,
\binom{n-1}{k}+\binom{n-1}{k-1} = \frac{(n-1)!}{k!(n-1-k)!} + \frac{(n-1)!}{(k-1)!(n-k)!}.
Coloca-se um denominador comum (k!(n-k)!):
= \frac{(n-1)!(n-k)}{k!(n-k)!} + \frac{(n-1)!k}{k!(n-k)!} = \frac{(n-1)!(n-k+k)}{k!(n-k)!} = \frac{(n-1)!n}{k!(n-k)!}.
Como n\,(n-1)! = n!, obtemos
\binom{n-1}{k}+\binom{n-1}{k-1}=\frac{n!}{k!(n-k)!}=\binom{n}{k}.
Essa é exatamente a identidade de Pascal. Esta é a “regra da simplificação” pedida: ela permite substituir uma soma de dois binomiais por um único binomial com o índice superior aumentado em 1.

Passo 3

Escolheremos indução em n mantendo r fixo (com r\ge 0). Primeiro a base da indução. Uma base conveniente é n=r.
Calcule o lado esquerdo para n=r:
\sum_{k=0}^{r}\binom{k}{r}.
Pelo convênio \binom{k}{r}=0 quando k<r, todos os termos com k=0,1,\dots,r-1 valem zero, restando apenas o termo k=r:
\sum_{k=0}^{r}\binom{k}{r}=\binom{r}{r}=1.
O lado direito para n=r é
\binom{r+1}{r+1}=1.
Portanto a igualdade vale para n=r. (Observação: se alguém preferir, também se pode tomar n=0 como base e checar os dois casos r=0 e r>0; dá no mesmo por causa da convenção de zeros.)

Passo 4

Hipótese de indução. Suponha que para algum n\ge r valha
\sum_{k=0}^{n}\binom{k}{r}=\binom{n+1}{r+1}.
Queremos provar que então
\sum_{k=0}^{n+1}\binom{k}{r}=\binom{n+2}{r+1}.

Passo 5

Fazemos o passo indutivo diretamente, somando o termo k=n+1 ao lado esquerdo:
\sum_{k=0}^{n+1}\binom{k}{r} = \left(\sum_{k=0}^{n}\binom{k}{r}\right) + \binom{n+1}{r}.
Pelo hipótese de indução substituímos a soma até n:
= \binom{n+1}{r+1} + \binom{n+1}{r}.
Agora usamos explicitamente a identidade de Pascal (a “regra da simplificação”) com n substituído por n+1 e k=r+1:
\binom{n+2}{r+1}=\binom{n+1}{r+1}+\binom{n+1}{r}.
Portanto
\sum_{k=0}^{n+1}\binom{k}{r}=\binom{n+2}{r+1},
que é exatamente o que queríamos provar no passo n\to n+1.

Passo 6

Como a igualdade vale para a base n=r e o passo indutivo foi estabelecido, concluímos por indução que, para todo inteiro n\ge r,
\sum_{k=0}^{n}\binom{k}{r}=\binom{n+1}{r+1}.
Com a convenção \binom{n}{k}=0 para k>n, a identidade estende-se sem problemas a todos os inteiros n\ge 0. Pronto — a prova por indução está completa e a identidade de Pascal foi usada explicitamente no passo indutivo.

Resposta

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

Exercícios relacionados