Re: [obm-l] Problema - Recorrência / Fibonacci

["Domingos Jr." <dopikas@xxxxxxxxxx>]

David M. Cardoso wrote:

>Olá novamente,
>
>Seja F_n a recorrência definida por F_(n+1) = F_n + F_(n-1).
>Com F_1 = 1, F_2 = 1, ... (sequencia de fibonacci)
>
>"Qual é o maior: 2^100 ou F_100 ?"
>
>deu pra perceber, testando, que 2^100 é maior.
>Ateh porque 2^(n+1) / 2^n = 2
>Enquanto que F_(n+1) / F_(n) ~ 1,618 quando n é grande.
>
>Mas não sei formalizar/mostrar que 2^100 é de fato o maior.
>
Você pode provar o resultado por indução para todo n, veja:
para n = 1, 2, F_n = 1 < 2^n

F_{n+1} = F_n + F{n-1} < 2^n + 2^{n-1} = 3*2^{n-1} < 4*2^{n-1} = 2^{n+1}

e o resultado segue por indução.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================