Re: [obm-l] sequencia, numero de digitos

[Leonardo Paulo Maia <lpmaia@xxxxxxxxxxx>]

Niski, consulte algum texto de matem�tica discreta, que fale sobre rela��es de
recorr�ncia. H� uma teoria an�loga � de eqs. diferenciais, c/ superposi��o de
solu��es, solu��o do caso n�o homog�neo � soma de solu��o particular com
solu��o do caso homog�neo, etc. Essa recorr�ncia que voc� trouxe � f�cil porque
se trata de uma equa��o com coeficientes constantes e o termo n�o homog�neo �
simples (polin�mio de grau 1). As solu��es b�sicas da homog�nea v�m da eq.
p^2=p-2 (tentativa de solu��o p^n, onde p � uma cte a ser determinada), de
ra�zes 2 e -1. A solu��o particular vem da tentativa An+B, que revela que
A=-1/2 e B=-5/4.

Sol. geral: x[n] = (cte1).(2^n)+(cte2).((-1)^n)-(n/2)-5/4

Como x[1]=x[2]=1, cte1=1 e cte2=-3/4.

Finalmente, x[n] = 2^n-(3/4).((-1)^n)-(n/2)-5/4
e x[100] = (2^100) - 52.

Como o n�mero de d�gitos decimais de um inteiro positivo � dado por 1 mais a
parte inteira do seu logaritmo na base 10, voc� precisa calcular log[(2^100) -
52] = log[2^100] + log[1 - 52/(2^100)] = 30,1 aproximadamente. O segundo log �
desprez�vel, se voc� quiser ser rigoroso pode controlar o erro no truncamento
da expans�o de Taylor. Logo, a resposta final � 30+1=31.

Leo

Quoting Fabio Niski <fniski@terra.com.br>:

> Pessoal, nao tive uma boa ideia pra resolver este problema, entao eu o 
> proponho pra lista. Quem achar a solucao, pe�o para que poste aqui.
> 
> "How many decimal digits are needed to write the hundredth term of the 
> sequence 1,1,6,12,29,59,...(x[n] = x[n-1] + 2x[n-2] + n, x[1]=x[2]=1)
> ?"
> 
> Niski
> =========================================================================
> 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
=========================================================================