Re:_[obm-l]_somatório

[Johann Peter Gustav Lejeune Dirichlet <peterdirichlet2002@xxxxxxxxxxxx>]

Para quem ja leu o artigo do Hector Soza Pollman,
"Equaçoes de Recorrencia", na Eureka! 9, e o
artigo "Series Formais" do Eduardo Tengan na
Eureka! 20 este metodo abaixo e um pouco mais
geral.

n *2^0 + (n - 1) * 2^1 + (n - 2)*2^2 + ...
+1*2^(n-1)
Bem, se tentarmos nos livrar do n primeiro...

n*( 2^0 +2^1  +2^2  +2^3  +...+2^(n-1) )
 -(0*2^0+1*2^1+2*2^2+3*2^3+...+(n-1)*2^(n-1))

Agora o primeiro somatorio e uma PG (fica para o
leitor as contas). O segundo e algo como
S(n)=soma (1<=i<=n) (i*2^i)
Minha ideia sera escrever S como uma recursao
linear homogenea de si mesma:
S(n+1)-S(n+0)=(n+1)*2^(n+1)
Uma substituiçao de variaveis:
S(n)-S(n-1)=g(n)=n*2^n
g(n+1)=(n+1)*2^(n+1)=n*2^(n+1)+2^(n+1)
=2*n*2^n+2^(n+1)
=2*g(n)+2^(n+1)
E com isto ,
g(n+1)-2*g(n)=2^(n+1)
g(n+2)-2*g(n+1)=2*2^(n+1)=2*g(n+1)-4*g(n)
g(n+2)-4*g(n+1)+4*g(n)=0
Troca g por S:
S(n+2)-S(n+1)-4*S(n+1)+4*S(n)+4*S(n)-4*S(n-1)=0
S(n+2)-5S(n+1)+8*S(n)-4*S(n-1)=0
S(n+3)-5S(n+2)+8*S(n+1)-4*S(n)=0
Agora e so fatorar o polinomio caracteristico
x^3-5*x^2+8*x-4
e escrever as equaçoes necessarias para a serie
formal de S (leia o artigo!). Com isto basta ter
os valores iniciais e catapimba!, acaba o
problema.

Esta parte e a mais facil (ou nao...) e ela fica
para quwem quiser continuar...Agora tenho que ir.

Ass.:Johann




 --- Fabio Dias Moreira
<fabio@dias.moreira.nom.br> escreveu: > 
> Eduardo Henrique Leitner said:
> > On Sun, May 16, 2004 at 08:32:39PM -0300,
> Gustavo Baggio wrote:
> >> Alguém manja de alguma fórmula pra calcular
> direto o somatório de n *
> >> 2^0 + (n - 1) * 2^1 + (n - 2)*2^2 + ... +
> 1*2^(n-1)  ?
> >> Isso nada mais é do que somatório de i
> variando de 0 até (n-1) de  (n
> >> - i)*(2^i).
> >> Por exemplo para n = 4 temos 4*1 + 3*2 + 2*4
> + 1*8.
> >>
> >> Qualquer dica, enfim, tá valendo...
> >> [...]
> >
> > eis uma maneira:
> >
> >
> > n * 2^0 + (n - 1) * 2^1 + (n - 2)*2^2 + ... +
> 1*2^(n-1) =
> > = n[ 2^0 + 2^1 + 2^2 + ... + 2^(n-1) ] - {
> 1*2^1 + 2*2^2 + 3*2^3 + ... +
> > (n-1)*2^(n-1) }  =
> >
> > partindo do suposto que vc conhece a fórmula
> da soma dos n primeiros
> > termos de uma PG:
> > [...]
> > resposta:  2^(n+1) - (n+2)
> > [...]
> 
> Se pudermos usar cálculo tem uma maneira mais
> direta:
> 
> x^0 + x^1 + x^2 + ... + x^n = [x^(n+1) -
> 1]/(x-1)
> 
> Derive os dois lados em relação a x:
> 
> 1*x^0 + 2*x^1 + ... + n*x^(n-1) = d([x^(n+1) -
> 1]/[x-1])/dx
> 
> Finalmente, multiplique por x:
> 
> 1*x^1 + 2*x^2 + ... + n*x^n = x * d([x^(n+1) -
> 1]/[x-1])/dx
> 
> O lado direito é facilmente derivado, pois é a
> derivada de um quociente.
> De fato, não é muito difícil ver que ela vale
> [n*x^(n+1)-(n+1)*x^n+1]/[x-1]^2. Substituindo x
> = 2,
> 
> 1*2^1 + 2*2^2 + ... + n*2^n = 2 *
> [n*2^(n+1)-(n+1)*2^n+1]/[2-1]^2
> 1*2^1 + 2*2^2 + ... + n*2^n = n*2^(n+2) -
> (n+1)*2^(n+1) + 2.
> 
> Finalmente, voltando ao problema original,
> 
> n*2^0 + (n-1)*2^1 + ... + 1*2^(n-1) =
> = n*[2^0+2^1+2^2+...+2^(n-1)] - (1*2^1 + 2*2^2
> + ... +
> (n-1)*2^(n-1)) =
> = n*(2^n-1) - (n-1)*2^(n+1) + n*2^n - 2 =
> = n*2^n - n - 2*n*2^n + 2^(n+1) + n*2^n - 2 =
> = 2^(n+1) - (n+2).
> 
> Note que nós calculamos 1*2^1 + ... + n*2^n,
> mas queremos 1*2^1 + 2*2^2 +
> ... + (n-1)*2^(n-1), logo temos que trocar o n
> por n-1.
> 
> Outro problema legal nessa mesma linha é o
> problema 4 da OBM 2002.
> 
> []s,
> 
> -- 
> Fábio "ctg \pi" Dias Moreira
> 
> 
>
=========================================================================
> 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
>
========================================================================= 

=====
TRANSIRE SVVM PECTVS MVNDOQVE POTIRI 

CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE 

Fields Medal(John Charles Fields)
 
N.F.C. (Ne Fronti Crede)



______________________________________________________________________

Yahoo! Messenger - Fale com seus amigos online. Instale agora! 
http://br.download.yahoo.com/messenger/
=========================================================================
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
=========================================================================