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

Re:RES: [obm-l] Somatorios de potencias dos naturais

Eu ainda prefiro uma demonstra��o combinat�ria.
 
Problema: Quantos ternos ordenados (x,y,z) existem cujos elementos pertencem a {1, 2, 3, ..., n, n+1} e s�o tais que x > y e x > z?
 
Solu��o 1:
Para x = k+1  (k em {1, 2, ..., n}), temos k escolhas para y e k escolhas para z. Logo, existem k^2 ternos da forma (k+1,y,z) nas condi��es do enunciado.
Fazendo k variar de 1 a n, obtemos que o n�mero total de ternos �:
1^2 + 2^2 + 3^2 + ... + n^2.
 
Solu��o 2:
Os ternos (x,y,z) com x > y e x > z s�o de tr�s tipos:
1. Ternos em que x > y > z
2. Ternos em que x > z > y
3. Ternos em que x > y = z.
Existem Binom(n+1,3) ternos dos tipos 1 e 2 e Binom(n+1,2) ternos do tipo 3.
Logo, o n�mero total de ternos � 2*Binom(n+1,3) + Binom(n+1,2) =
2*(n+1)*n*(n-1)/6 + (n+1)*n/2 =
n*(n+1)*((n-1)/3 + 1/2) =
n*(n+1)*(2n-2+3)/6 =
n*(n+1)*(2n+1)/6
 
Como ambas as solu��es t�m que dar o mesmo resultado...
 
***
 
Pra soma dos cubos, ter�amos que considerar as qu�druplas ordenadas (x,y,z,w) de elementos de {1,2,...,n,n+1} tais que x > y, x > z e x > w.
 
Na solu��o 2, os tipos b�sicos de qu�drupla seriam:
1. x > y > z > w  (total de 6 permuta��es de y, z  e w)
Contribui��o = 6*Binom(n+1,4)
2. x > y = z > w (total de 3)
Contribui��o = 3*Binom(n+1,3)
3. x > y > z = w (total de 3)
Contribui��o = 3*Binom(n+1,3)
4. x > y = z = w (total de 1)
Contribui��o = Binom(n+1,2)
 
Total = 6*(Binom(n+1,4) + Binom(n+1,3)) + Binom(n+1,2) =
6*Binom(n+2,4) + Binom(n+1,2) =
6*(n+2)*(n+1)*n*(n-1)/24 + (n+1)*n/2 =
(n+1)*n/2 * ((n+2)*(n-1)/2 + 1) =
n*(n+1)/2 * (n^2 + n - 2 + 2)/2 =
n*(n+1)/2 * n*(n+1)/2 =
n^2*(n+1)^2/4
 
No entanto, ser� que o fato de ser:
1^3 + 2^3 + ... + n^3 = (1 + 2 + ... + n)^2
n�o d� margem a alguma demonstra��o geom�trica?
 
[]s,
Claudio.
 
De: owner-obm-l@mat.puc-rio.br
Para: obm-l@mat.puc-rio.br
C�pia:
Data: Mon, 8 May 2006 16:01:17 -0300
Assunto: RES: [obm-l] Somatorios de potencias dos naturais
> Vou olhar o seu blog assim que tiver tempo para uma avalia��o cuidadosa.
>
> Uma forma de se chegar aa formula para as pot�ncias p+1, p inteiro, dos n
> primeiros inteiros positivos eh usar recorrecia. Sendo Bin(p,k) =
> p!/(k!*(n-k)*), k=0, 1,... p, temos pelo Binomio de Newton, temos:
>
> (n + 1)^p = n^p + p*n^(p-1) ....+Bin(p,k)n^k ...+ 1
> (n-1 +1)^p = (n-1)^p + p*(n-1)^(p-1) + Bin(p,k)(n-1)^k ...+ 1
> .
> .
> (1+ 1)^p n = 1 + p....+ Bin(p,k)......+1
>
> Somando-se estas n igualdades e fazendo algumas transformacoes algebricas um
> tanto bracais, obtemos a soma das potencias p conhecendo-se a formula das
> potencias de ordem p-1,...1. Isto vai nos mostrar que a soma das potencias p
> eh dada por um polinomio em n do grau p+1.
> Com um pouco de paciencia e muita atencao para nao errar, podemos
> generalizar este processo para obter a formula da soma das potencias de
> ordem p dos n primeiros termos de uma progressao aritmetica.
>
> Uma vez provado que a soma desejada eh um polinomio de grau p+1 em n ( que
> pode ser feito por inducao em p), vc tambem pode chegar aos coeficientes do
> polinomio atribuindo p+1 valores a n e resolvendo um sistema de equacoes
> lineares. Tambem exige uma certa dose de paciencia.
>
> De forma simples, eh possivel demonstrar por inducao que S(n,3) = (S(n,1))^2
> = (n*(n+1)/2)^2
>
> Artur
>
>
>
>
> -----Mensagem original-----
> De: owner-obm-l@mat.puc-rio.br [mailto:owner-obm-l@mat.puc-rio.br]Em
> nome de Bruno Bonagura
> Enviada em: segunda-feira, 8 de maio de 2006 14:33
> Para: obm-l@mat.puc-rio.br
> Assunto: [obm-l] Somatorios de potencias dos naturais
>
>
> Ol� pessoal,
>
> Na primeira vez em que vi o somat�rio 1� + 2� + 3� + ... + n� e sua
> f�rmula (1/6)(2n+1)(n+1)n fiquei curioso em tentar demonstrar tal
> f�rmula. Isso foi h� quase dois anos! Desde ent�o pensava frequentemente
> no assunto e as vezes procurava sobre ele na internet. Visito alguns
> f�runs de matem�tica, tanto nacionais como internacionais, e sempre que
> era questionada demonstra��o para tal f�rmula mostravam aquela que
> utiliza combina��o e mais algumas coisas. Confesso que n�o dei muita
> aten��o para tal demonstra��o, n�o tive simpatia com ela.
>
> Enfim, depois de algumas id�ias e algumas observa��es dos azuleijos do
> banheiro (rs), criei uma demonstra��o para tal f�rmula. N�o sei se j�
> foi feita, mas estou sendo sincero ao dizer que a criei sem consultar
> algo semelhante j� produzido. Gostaria que olhassem, criticassem
> poss�veis erros, etc. Mas, principalmente, me digam se j� est� na
> literatura corrente esta demonstra��o. Ela est� dispon�vel no meu blog
> (http://bbonagura.blog.uol.com.br/) no post com t�tulo "Empilhando
> quadrados".
>
> Vale ressaltar que n�o estou enviando essa mensagem para a lista apenas
> para fazer propaganda e conseguir visitas no meu blog. Meu intuito �
> compartilhar conhecimento e receber cr�ticas/sugest�es, n�o a coloco
> diretamente aqui por causa das f�rmulas matem�ticas e imagens que a
> envolvem.
>
> Bruno Bonagura
>