Re: [obm-l] somatório

["Fabio Dias Moreira" <fabio@xxxxxxxxxxxxxxxxxxx>]

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