Entendi.. entendi.. obrigado. []'s
> -----Mensagem original----- > De: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] Em nome de Domingos Jr. > Enviada em: terça-feira, 20 de julho de 2004 23:44 > Para: [EMAIL PROTECTED] > 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 =========================================================================