Exercício 39. Use indução para demonstrar a identidade de Cassini para Fibonacci:
Passo 1
O enunciado pede para demonstrar, por indução, a identidade de Cassini
para todo
inteiro não negativo. Informações dadas (definição da sequência de Fibonacci) que serão usadas:
- As condições iniciais:
e . - A relação de recorrência:
A tarefa é provar que a igualdade acima vale para todo
, usando o princípio da indução matemática.
Passo 2
Rápida explicação do método de indução que será usado (sem assumir que já conhece bem):
- Base da indução: mostrar que a fórmula é verdadeira para um valor inicial
(ou ); isso confirma que a propriedade começa certa em algum passo. - Passo indutivo: supor que a fórmula seja verdadeira para
(essa suposição chama-se hipótese de indução) e, a partir dela, provar que a fórmula é verdadeira para . Se isso for feito, conclui-se que a fórmula vale para todo base.
Vou aplicar exatamente esse esquema: basee depois passo .
Passo 3
Verificação da base da indução,
. Substituir
na expressão:
Calcular o lado esquerdo:
O lado direito é
Portanto, para
temos
ou seja, a identidade é verdadeira em
. A base está estabelecida.
Passo 4
Enunciar a hipótese de indução. Suponha que a identidade seja verdadeira para algum inteiro
; isto é, suponha que
A partir desta hipótese queremos provar que a identidade vale para
, ou seja, queremos mostrar que
Passo 5
Preparação para manipular a expressão do passo
. Usar a recorrência de Fibonacci para reescrever
:
Substituir essa expressão na quantidade que queremos avaliar:
Passo 6
Desenvolver a expressão e agrupar termos passo a passo, explicando cada passo:
Esta decomposição parece complicada à primeira vista; vamos simplificá-la usando uma identidade simples e a recorrência. Observe que
Pelo fato de
(que vem da recorrência escrita como
), segue que
Passo 7
Retornar à expressão original e usar a simplificação obtida. Começando de
reagrupar como
Usando
(do Passo 6) e simplificando os termos restantes obtemos:
A última linha resulta porque
e sobrou apenas o termo com sinal negativo.]
Passo 8
Aplicar a hipótese de indução
na igualdade obtida no passo anterior:
Isso demonstra exatamente que, se a identidade vale para
, então ela vale para
.
Passo 9
Conclusão da indução. Como a identidade foi verificada na base
(Passo 3) e mostramos que a validade para
implica validade para
(Passos 4–8), pelo princípio da indução matemática a identidade de Cassini
vale para todo inteiro
.