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

["David M. Cardoso" <david-obm@xxxxxxxxxxxx>]

Entendi.. entendi.. obrigado.

[]'s

> -----Mensagem original-----
> De: owner-obm-l@mat.puc-rio.br 
> [mailto:owner-obm-l@mat.puc-rio.br] Em nome de Domingos Jr.
> Enviada em: terça-feira, 20 de julho de 2004 23:44
> Para: obm-l@mat.puc-rio.br
> Assunto: Re: [obm-l] Problema - Recorrência / Fibonacci
> 
> 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
> ==============================================================
> ===========
> 


=========================================================================
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
=========================================================================