Re:_[obm-l]_somatório

[Gustavo Baggio <lagwagonhc@xxxxxxxxxxxx>]

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)
> >
>  [...]
>
> 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!