Exercício 40. Prove por indução a identidade da cola de hockey:
Mostre o uso da regra da simplificação nos coeficientes binomiais.
Passo 1
O enunciado pede para provar por indução a identidade
para inteiros não negativos
e
. 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
:
- A convenção padrão
quando ou . - A identidade de Pascal (regra da simplificação):
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,
Começando do lado direito,
Coloca-se um denominador comum
:
Como
, obtemos
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
mantendo
fixo (com
). Primeiro a base da indução. Uma base conveniente é
.
Calcule o lado esquerdo para
:
Pelo convênio
quando
, todos os termos com
valem zero, restando apenas o termo
:
O lado direito para
é
Portanto a igualdade vale para
. (Observação: se alguém preferir, também se pode tomar
como base e checar os dois casos
e
; dá no mesmo por causa da convenção de zeros.)
Passo 4
Hipótese de indução. Suponha que para algum
valha
Queremos provar que então
Passo 5
Fazemos o passo indutivo diretamente, somando o termo
ao lado esquerdo:
Pelo hipótese de indução substituímos a soma até
:
Agora usamos explicitamente a identidade de Pascal (a “regra da simplificação”) com
substituído por
e
:
Portanto
que é exatamente o que queríamos provar no passo
.
Passo 6
Como a igualdade vale para a base
e o passo indutivo foi estabelecido, concluímos por indução que, para todo inteiro
,
Com a convenção
para
, a identidade estende-se sem problemas a todos os inteiros
. Pronto — a prova por indução está completa e a identidade de Pascal foi usada explicitamente no passo indutivo.