Prove por indução a identidade da cola de hockey:
Passo 1
O enunciado pede para provar, por indução, a identidade
onde
e
são inteiros não negativos. Dados importantes fornecidos (ou que adotamos como convenção):
- A soma é sobre
. - Usamos a convenção
quando . - Queremos uma prova por indução em
(fixando ) que seja válida para todo (a identidade também é verdadeira para 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
,
Aqui
significa o fatorial de
(produto
). Por exemplo,
e
.
- Propriedade de Pascal (identidade de Pascal): para inteiros
,
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
mantendo
fixo. Uma base conveniente é
(ou alternativamente
se
, mas
cobre o caso geral de forma direta).
- Avaliando a soma quando
:
Pela convenção,
para
, e
. Logo a soma vale
.
- O lado direito quando
é
Portanto a identidade vale para
:
Assim a base da indução está comprovada.
Passo 4
Hipótese de indução. Suponha que a identidade seja verdadeira para algum
; isto é, suponha que
Essa é a hipótese que vamos usar para provar a fórmula para
.
Passo 5
Passo indutivo: provar que a identidade vale para
.
Começamos escrevendo a soma até em termos da soma até
:
Começamos escrevendo a soma até
Pela hipótese de indução, podemos substituir a soma entre parênteses por
. Assim
Passo 6
Agora aplicamos a identidade de Pascal ao lado direito. A identidade de Pascal diz que, para inteiros adequados,
Mostro rapidamente uma derivação algébrica desta igualdade para ficar bem claro (opcional, mas útil):
Colocando sobre o mesmo denominador
(multiplicando numerador e denominador do primeiro termo por
e do segundo termo por
) obtemos
O somatório interno é
, então o numerador fica
. Assim
Portanto, voltando ao passo anterior,
Isto mostra que, assumindo a verdade para
, a identidade vale para
.
Passo 7
Conclusão da indução. Como mostramos que a identidade vale para a base
e que a validade para um
implica a validade para
, por princípio da indução matemática a identidade
é verdadeira para todo inteiro
. Pela convenção
para
, a fórmula também vale para
, então vale para todo
.