[obm-l] RE: _[obm-l]_somatório

[Rogério Moraes de Carvalho <rogeriom@xxxxxxx>]

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: owner-obm-l@mat.puc-rio.br [mailto:owner-obm-l@mat.puc-rio.br] On
Behalf Of Gustavo Baggio
Sent: segunda-feira, 17 de maio de 2004 01:13
To: obm-l@mat.puc-rio.br
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 <fabio@dias.moreira.nom.br> 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
=========================================================================