[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.