A sequência de Fibonacci (1170-1250)(Fn) é definida por:
F1 & =1 F2 & =1 & vdots Fn & =Fn-1+Fn-2, se n >= 3
Prove usando indução finita que Fn<(74)^n.

Passo 1

Então, o exercício quer que a gente prove, por indução finita (indução forte), que a sequência de Fibonacci
F1=1, F2=1, Fn=Fn-1+Fn-2;(n>=3)
satisfaz
Fn=1)
O conteúdo é Indução (forte) e a gente vai precisar:
  1. Verificar as bases (pegar e ).
  2. Formular a hipótese indutiva (supondo a desigualdade para todos os índices até ).
  3. Mostrar que daí ela vale para .

Passo 2

(Base da indução)
Para F1=1el(tfrac74r)^1=tfrac74=1,75, :
F2=1el(tfrac74r)^2=tfrac4916approx3,06,
logo . OK.
Para :
logo . Também OK.
Assim, a propriedade vale para e .

Passo 3

(Indução forte)
Suponha que, para todo Fk com Fn+1=Fn+Fn-1 , valha
Fn
Queremos mostrar Fn+1.
Usando a definição de Fibonacci:
tfrac114;<;l(tfrac74r)^2 Long<=ftrightarrow 114<4916 Long<=ftrightarrow 44<49,
Pela hipótese indutiva,
Fn+1
Então
Para concluir, basta ver que
que é verdade. Logo

Resposta

Por indução forte, mostramos que para todo boxedFn vale

Exercícios relacionados