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