Seja a sequência de Fibonacci dada recursivamente por e para todo . Usando indução matemática comprove que
Passo 1
Vamos resolver um exercício sobre a sequência de Fibonacci. A questão pede para provar, usando indução matemática, que a fórmula fechada da sequência de Fibonacci é:
Para isso, vamos usar o princípio da indução matemática, que nos ajuda a provar que uma afirmação é verdadeira para todos os números naturais.
Passo 2
Primeiro, vamos verificar se a fórmula funciona para os primeiros termos da sequência de Fibonacci. Sabemos que e .
Vamos calcular usando a fórmula:
Simplificando:
O mesmo vale para . Portanto, a fórmula está correta para os casos base.
Passo 3
Agora, vamos assumir que a fórmula funciona para um termo qualquer , ou seja:
Esse é o nosso hipótese de indução. Precisamos mostrar que, se isso é verdadeiro para n = k , então também é verdadeiro para n = k + 1 .
Passo 4
Vamos calcular ak+1 usando a definição recursiva da sequência de Fibonacci:
Vemos que a expressão que obtivemos para ak+1 é exatamente a fórmula que queríamos provar, mas para n = k + 1 . Isso completa a etapa de indução, mostrando que se a fórmula vale para n = k , também vale para n = k + 1 .
Resposta
Portanto, por indução matemática, a fórmula fechada para a sequência de Fibonacci é: