Os números de Fibonacci são definidos recursivamente pela sequência
onde
e para
.
Aqui, examinamos as propriedades dos números de Fibonacci.
Encontre uma fórmula fechada para a sequência de Fibonacci usando as seguintes etapas.
Considere a sequência definida recursivamente
onde
e
. Mostre que essa sequência pode ser descrita pela fórmula fechada
para todo
.
Aqui, examinamos as propriedades dos números de Fibonacci.
Encontre uma fórmula fechada para a sequência de Fibonacci usando as seguintes etapas.
Considere a sequência definida recursivamente
Passo 1
O enunciado define a sequência por
e
e pede uma fórmula fechada. O conteúdo aqui é recorrência de primeira ordem e a ferramenta que vamos usar é o princípio de indução matemática.
Passo 2
Base da indução: para
temos
. Por outro lado,
, logo a fórmula
vale para
.
Passo 3
Hipótese de indução: suponha que, para algum
, valha
.
Passo 4
Passo indutivo: usando a recorrência,
Assim mostramos que, se vale para
, vale também para
.
Passo 5
Pelo princípio de indução, a fórmula fechada
é válida para todo
.