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