[obm-l] Re: [obm-l] Somatória

["claudio.buffara" <claudio.buffara@xxxxxxxxxxxx>]

 

De:	owner-obm-l@mat.puc-rio.br

Para:

obm-l@mat.puc-rio.br

Cópia:

Data:

Tue, 10 May 2005 13:45:36 -0300

Assunto:

Re: [obm-l] Somatória

> Citando Bruno Bonagura :

>

> > Acho que faz um ano que vi essa questão e jamais consegui responder. Sempre

> > que tenho alguma idéia acabo voltando para a pergunta original :/.

> >

> > S = 1² + 2² + 3² + 4² + ... + n²

>

>

> Se você souber a fórmula:

>

> 1² + 2² + 3² + 4² + ... + n²= (1+2+3+...+n)²

>

Espero sinceramente que ninguém saiba esta fórmula. Por exemplo, teste o caso n = 2.

 

A fórmula correta é:

1^3 + 2^3 + ... + n^3 = (1 + 2 + ... + n)^2.

 

Além da demonstração padrão por indução, tem esta aqui:

 

Seja I_n= {0,1,2,....,n}.

Seja A = conjunto das quadruplas ordenadas (x,y,z,w) de elementos de I_n tais que x > y, x > z e x > w.

Seja B = conjunto das quádruplas ordenadas (x,y,z,w) de elementos de I_n tais que x > y  e  z > w.

 

1) |A| = 1^3 + 2^3 + ... + n^3.

Se x = 0, então não há nenhuma quadrupla satisfazendo a condição.

Se x = k > 0, então, temos k alternativas para y, k para z e k para w, num total de k^3 (ou seja, y, z, w pertencem a I_k = {0,1,...,k-1}).

Somando de k = 1 até n, obtemos que:

|A| = 1^3 + 2^3 + ... + n^3.

 

2) |B| = (1 + 2 + ... + n)^2.

Um par (x,y) com x > y pode ser escolhido de Binom(n+1,2) maneiras.

Um par (z,w) com z > w também.

Logo, |B| = Binom(n+1,2)^2 = ((n+1)n/2)^2 = (1 + 2 + ... + n)^2.

 

3) A inter B = {(x,y,z,w) em I_n^4 | x > y, x > z > w}.

Assim, se (x,y,z,w) pertence a A - B, então de duas uma:

Ou  x > w = z  ou  x > w > z.

 

Se (x,y,z,w) pertence a B - A, então de duas uma:

Ou  x = z > w  ou  x > z > w.

 

Mas o número de quadruplas (x,y,z,w) com x > y e x > w = z é igual ao número de quádruplas (x,y,z,w) com x > y e x = z > w.

Fixando x = k e y < x, teremos k quádruplas de cada tipo.

 

Além disso, o número de quádruplas (x,y,z,w) com x > y e x > w > z é igual ao número de quádruplas (x,y,z,w) com x > y e x > z > w.

Fixando x = k e y < x, teremos Binom(k,2) quádruplas de cada tipo.

 

Em suma, existe uma bijeção entre A - B e B - A.

 

Adicionando (via união) o conjunto A inter B a cada um deles, concluímos que existe uma bijeção entre A e B.

 

Logo, |A| = |B| e acabou.

 

 

[]s,

Claudio.