[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] 1^2 + 2^2 + ... + n^2()Caso Geral



Bom, acho que tem algo a ver com os números de Bernoulli (que não têm
fórmula fechada, mas quem disse que cos(x) é uma "fórmula fechada"??
(Isso foi para provocar...)

O truque é que estes números relacionam-se com a expansão de n^k em
somas de binomiais da forma n^k = SOMA {em j} C(n, j) * B(k, j) (ou
algo parecido, pode ter um k-j em vez de j). Daí, como eu falei numa
mensagem anterior, é só usar a soma das colunas.

Maiores detalhes, você pode encontrar no "Concrete Mathematics",
R.L.Graham, D.E.Knuth, O.Patashnik.

Abraços,
-- 
Bernardo Freitas Paulo da Costa


On Apr 9, 2005 11:21 AM, Johann Peter Gustav Lejeune Dirichlet
<peterdirichlet2003@yahoo.com.br> wrote:
> Existe alguma especie de formula fechada para o caso
> geral? Ou seja, calcular as k-esimas potencias dos n
> primeiros naturais, em funcao de n e k.
> 
> --- "Nicolau C. Saldanha" <nicolau@mat.puc-rio.br>
> wrote:
> > On Tue, Apr 05, 2005 at 02:02:34PM -0300,
> > claudio.buffara wrote:
> > > Ontem alguém perguntou aqui na lista como se
> > demonstrava a fórmula da soma
> > > dos quadrados dos primeiros n inteiros positivos.
> >
> > Oi Claudio, achei bem legal a sua demonstração.
> >
> > Na verdade este assunto já foi discutido várias
> > vezes nesta lista
> > e pode valer a pena dar uma olhada nos arquivos.
> >
> > Seja f(n) = 1^2 + 2^2 + ... + n^2. Podemos definir f
> > também como
> > a única função de Z em Z que satisfaz f(0) = 0, f(n)
> > = f(n-1) + n^2.
> >
> > É fácil ver que f é um polinômio de grau 3. De fato,
> > considere a
> > seguinte transformação linear: T(a,b,c) = (d,e,f)
> > se, sendo
> > g(n) = an^3 + bn^2 + cn, tivermos g(n) - g(n-1) =
> > dn^2 + en + f.
> > A transformação linear T é bem definida pois os
> > termos de grau 3
> > se cancelam; T também é injetora, pois g(n) - g(n-1)
> > = 0 para todo n
> > implica que g é constante logo, como não há termos
> > constante em g,
> > temos g = 0. Assim T é inversível. Note que o mesmo
> > raciocínio
> > demonstra que se h é um polinômio de grau k e se g
> > satisfaz
> > g(n) = g(n-1) + h(n) então g é polinômio de grau
> > k+1.
> >
> > Agora escrevendo f(n) = an^3 + bn^2 + cn + d, f(0) =
> > 0, f(1) = 1,
> > f(2) = 5, f(3) = 14 temos um sisteminha 3x3:
> >   a +  b +  c =  1
> >  8a + 4b + 2c =  5
> > 27a + 9b + 3c = 14
> > e podemos facilmente achar a, b e c.
> >
> > Mas acho mais elegante neste caso ver quais são as
> > raízes de f.
> > Claramente temos f(0) = f(-1) = 0. Note que f(-2) =
> > - (-1)^2 = -f(1),
> > f(-3) = - (-1)^2 - (-2)^2 = -f(2), ...,
> > f(-1-n) = - (-1)^2 - (-2)^2 - ... - (-n)^2 = -f(n).
> > Temos assim f(-1-n) = -f(n) donde f(-1/2) = 0, a
> > terceira raiz.
> > Assim f(n) = cn(n+1)(2n+1). Uma substituição obteria
> > o valor de c,
> > mas prefiro fazer f(n) ~= int_0^n t^2 dt = 1/3 n^3
> > donde c = 1/6.
> >
> > []s, N.
> >
> =========================================================================
> > 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! Acesso Grátis - Internet rápida e grátis.
> Instale o discador agora! http://br.acesso.yahoo.com/
> =========================================================================
> 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
> =========================================================================
>

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