Ol� Gustavo,
Existem algumas solu��es poss�veis para encontrar uma f�rmula para o
somat�rio apresentado.
UM POUCO DE TEORIA:
Alguns autores consideram que se os termos consecutivos de uma
progress�o aritm�tica s�o multiplicados por pot�ncias de mesma base e
expoentes consecutivos, ent�o teremos uma progress�o aritm�tico-geom�trica
(P.A.G.). Ou seja, uma seq��ncia do tipo:
a1, (a1 + R).q, (a1 + 2R).q^2, (a1 + 3R).q^3, ..., [a1 + (n - 1)R].q^(n - 1)
� uma progress�o aritm�tico-geom�trica de primeiro termo a1, com a1, a1 + R,
a1 + 2R, ..., a1 + (n - 1).R formando uma P.A. de raz�o R e q, q^2, q^3,
..., q^(n - 1) formando uma P.G. de raz�o q.
A seguir, eu apresento uma terceira solu��o poss�vel usando
somat�rios e suas propriedades. Esta t�cnica de resolu��o pode ser utilizada
para deduzir a f�rmula geral da soma dos termos de uma P.A.G. e somente
utiliza a f�rmula da soma dos termos de uma P.G. uma �nica vez.
NOTA��O ADOTADA:
S{i=1,i=n}(a_i) significa somat�rio com i variando de 1 at� n de a �ndice i.
OUTRA RESOLU��O POSS�VEL:
Seja S a soma a ser encontrada, ent�o:
S = S{i=0,i=n-1}[(n-i).2^i]
2.S = S{i=0,i=n-1}[(n-i).2^(i+1)]
2.S = S{i+1=1,i+1=n}{[n+1-(i+1)].2^(i+1)}
2.S = S{i=1,i=n}[(n+1-i).2^i]
2.S = S{i=1,i=n}[(n-i).2^i+2^i]
2.S = S{i=1,i=n}[(n-i).2^i] + S{i=1,i=n}(2^i)
2.S = S - (n-0).2^0 + (n-n).2^n + 2.(2^n-1)/(2-1)
2.S - S = -n + 0 + 2^(n+1) - 2
S = 2^(n+1)-(n+2)
Atenciosamente,
Rog�rio Moraes de Carvalho
________________________________________
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On
Behalf Of Gustavo Baggio
Sent: segunda-feira, 17 de maio de 2004 01:13
To: [EMAIL PROTECTED]
Subject: Re:_[obm-l]_somat�rio
Valeu f�bio dias, mas a solu��o do eduardo henrique me pareceu mas atraente
pois manipula direto no somat�rio. A sua me pareceu interessante tamb�m pelo
que olhei (maios ou menos).
Na verdade esse somat�rio saiu de uma rela��o de recorr�ncia de um algoritmo
recursivo aparentemente inofensivo. Rodei o programa para alguns valores de
n e a f�rmula � realmente v�lida.�
�
gustavo
Fabio Dias Moreira <[EMAIL PROTECTED]> wrote:
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)
&g! t; [...]
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, n�vel 3.
[]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
=========================================================================
________________________________________
Yahoo! Messenger - Fale com seus amigos online. Instale agora!
=========================================================================
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
=========================================================================
