terça-feira, 3 de abril de 2012

031-Fórmula Geral para Somatórios de Potências

Na maior parte das ciências, uma geração põe abaixo
o que a outra construiu, e o que a outra estabeleceu
a outra desfaz. Somente na Matemática é que 
cada geração constrói um novo andar sobre a
antiga estrutura. (Hermann Hankel

 [;P(n;p);] é o preenchimento de [;n;] elementos, tomados [;p;] elementos

 O leitor e colaborador matemático Antonio Carlos Tavano, de São Paulo-SP, em suas pesquisas em Análise Combinatória, se deparou com a seguinte função nas variáveis [;n;] e [;p;][;\in \mathbb{N};], com [;n \leq p;].

[;P(n;p);] = número de sequências de [;p;] termos que, em cada uma delas, haja todos os elementos de um conjunto de [;n;] elementos.

Exemplo 1:  considere a sequência de [;p=4;] termos.

[;S=(a,a,b,c);]
 
Nela, seus termos formam um conjunto de [;n=3;] elementos:

[;C={\left{a,b,c \right};]

Neste caso, [;P(n;p)=P(3;4)=36;] é o número de sequências do tipo [;S;], com [;p=4;] termos em que haja todos os elementos do conjunto [;C;] com [;n=3;] elementos.

Algumas destas sequências: [;(a,a,b,c);] [;(a,a,c,b);],[;(b,b,a,c);],[;(c,a,b,c);], etc em um total de [;P(3;4)=36;].

Observem que [;P(3;4);] não é o [;n^o;] de anagramas de [;S;] porque o número de repetições de cada termo pode se alterar. É claro que também não é a combinação de [;4;] elementos tomados [;3;] a [;3;].

Nas palavras do próprio Tavano,

[;P(n;p);] é o preenchimento de [;n;] elementos, tomados [;p;] elementos

Exemplo 2: Calcular [;P(1;5);]. Temos [;\left{(a,a,a,a,a) \right};] , assim [;P(1;5)=1;] 

Exemplo 3: Calcular [;P(2;3);]. Temos [;\left{(a,a,b),(a,b,b),(b,b,a),(b,a,a),(a,b,a),(b,a,b) \right};], logo [;P(2;3)=6;]. Notem que [;(a,a,a);] e [;(b,b,b);] , por definição, não fazem parte da contagem, pois apenas um elemento aparece.

Exemplo 4: Calcular [;P(3,3);]. Temos [;\left{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)};]. [;P(3,3)=3!=6;]. Reparem que [;(a,a,c);],[;(c,c,b);],[;(b,b,c);],[;(a,a,a);],[;(b,b,b);], etc, não pertencem a este conjunto, pois nenhuma destas sequências têm [;3;] elementos diferentes.

Valores iniciais com [;p;] fixo.

[;P(1,p)=1;]

[;P(2,p)=1.2^p-2.1^p+1.0^p;]

[;P(3,p)=1.3^p-3.2^p+3.1^p-1.0^p;]

[;P(4,p)=1.4^p-4.3^p+6.2^p-4.1^p+1.0^p;]

De forma que

 [;P(n;p) = {n \choose 0}n^p-{n \choose 1}(n-1)^p+{n \choose 2}(n-2)^p-...+(-1)^{n-1}{n \choose {n-1}}1^p;]

Antes da demonstração desta fórmula, veremos uma aplicação.

Somatórios de potências: Levando em consideração que [;\sum_{1}^{n-1}a_i{n \choose i}={n \choose i+1};] , no post Representação de Potências por Combinações, mostrei a vantagem em transformar [;n^p;] em uma soma de múltiplos de combinações do tipo [;a_i {n \choose i};], tendo em vista a grande facilidade para somatórios, conforme os seguintes exemplos:

[; \sum_{1}^{n-1} n^1=\sum_{1}^{n-1}{n \choose 1}={n \choose 2};]

[;\sum_{1}^{n-1}n^2=\sum_{1}^{n-1}[{n \choose 1} + 2 {n \choose 2}]={n \choose 2} + 2 {n \choose 3};]

[;\sum_{1}^{n-1}n^3=\sum_{1}^{n-1}[{n \choose 1} + 6 {n \choose 2}+6 {n \choose 3}]={n \choose 2} + 6 {n \choose 3}+6 {n \choose 4};]

[;\sum_{1}^{n-1}n^4=\sum_{1}^{n-1}[{n \choose 1}+14{n \choose 2}+36{n \choose 3}+24{n \choose 4}]={n \choose 2}+14{n \choose 3}+36{n \choose 4}+24{n \choose 5};]

Naquele artigo, o método que utilizei para achar os coeficientes combinativos [;a_1,a_2,a_3,...,a_p;]  de

[;n^p=a_1 {n \choose 1}+a_2{n \choose 2}+a_3{n \choose 3}+...+a_p{n \choose p};]

foi um processo recursivo onde utilizei  a relação [;n{n \choose k}=k{n \choose k}+(k+1){n \choose k+1};].

Mas em [;n^4=1.{n \choose 1}+14.{n \choose 2}+36.{n \choose 3}+24.{n \choose 4};]Tavano observou que

[;1=P(1;4)=1;]

[;14=P(2;4)=1.2^4-2.1^4+1.0^4;]

[;36=P(3;4)=1.3^4-3.2^4+3.1^4-1.0^4;] 

[;24=P(4,4)=1.4^4-4.3^4+6.2^4-4.1^4+1.0^4=4!;]

Assim, os coeficientes combinativos de [;n^p;] são calculados diretamente pela função [;P(n;p);]:

[;a_i=P(i;p) = {i \choose 0}i^p-{i \choose 1}(i-1)^p+{i \choose 2}(i-2)^p-...+(-1)^{i-1} {i \choose {i-1}}1^p;]

Alguns exemplos destes coeficientes:
             1









1
2








1
6
6







1
14
36
24






1
30
150
240
120





1
62
540
1560
1800
720




1
126
1806
8400
16800
15120
5040



1
254
5796
40824
126000
191520
141120
40320


1
510
18150
186480
834120
1905120
2328480
1451520
362880











              ............................................................................................................................ETC

[;\rightarrow;] Os leitores ficam convidados para acharem uma relação de formação entre as células deste triângulo aritmético.

Vamos, agora, a demonstração da fórmula [;P(n;p);] do preenchimento de [;n;] elementos, tomados [;p;] elementos, e em seguida, veremos o porque da relação dos valores desta função com os coeficientes combinativos [;a_i;] de [;n^p=a_1{ n\choose 1}+a_2{ n\choose 2}+...+a_p{ n\choose p;].
  
Teorema: Dados os inteiros não-negativos [;n \leq p;], se [;P(n;p);] = número de sequências de [;p;] termos que, em cada uma delas, haja todos os elementos de um conjunto de [;n;] elementos, então

[;P(n;p) = {n \choose 0}n^p-{n \choose 1}(n-1)^p+{n \choose 2}(n-2)^p-...+(-1)^{n-1}{n \choose {n-1}}1^p;]

Demonstração: Considere os seguintes conjuntos

Conjunto [;A;] com [;n;] elementos [;\left{\alpha_1, \alpha_2,...,\alpha_n \right};];

Conjunto [;P;] formado por sequências de [;p;] termos onde cada sequência é formada por um, alguns ou todos  elementos de [;A;]. Como [;n \leq p;] os elementos [;\alpha_i;] se repetirão, as vezes, para "preencherem" estas sequências. Como para cada termo de uma sequência do conjunto [;P;] temos [;n;] possibilidades, então [;N(P)=n^p;] é o número de elementos do conjunto [;P;];

Conjunto [;P_i;] formado por sequências de [;p;] termos onde cada sequência é formada por todos os [;i \leq n;]  elementos de [;A;]. Para cada grupo de elementos da combinação [;n \choose i;] de elementos de [;A;], vamos ter uma  formação ( preenchimento) de natureza diferente na sequência de [;p;] termos. Assim, [;N(P_i)=P(i,p).{ n\choose i};].

É claro que [;P_i \subset P;]. Assim, para [;i=1,2,...,i,...,n \leq p;], temos

[;P=;][;P_1;] [;U;] [;P_2;] [;U;][;...;][;U;][;P_i;] [;U;]...[;U;] [;P_n;]

Portanto, [;N(P)=N(P_1)+N(P_2)+...+N(P_i)+...+N(P_n) \Rightarrow;]

[;n^p=P(1;p){n \choose 1}+P(2;p){n \choose 2}+...+P(i;p){n \choose i}+...+P(n;p){n \choose n};]

Com o último resultado, temos uma fórmula recursiva para [;P(n;p);], com [;P(1;p)=1^p;].Veja:

[;P(n;p)=P(n;p){n \choose n}=n^p-P(1;p){n \choose 1}-P(2;p){n \choose 2}-...-P(i;p){n \choose i}-...-P(n-1;p){n \choose n-1};]

[;P(1;p)=1^p=1;]
[;P(2;p)=2^p-P(1;p){2 \choose 1}=2^p-2;]
[;P(3;p)=3^p-{3 \choose 1}P(1;p)-{3 \choose 2}P(2;p)=3^p-3(1)-3(2^p-2)=3^p-3.2^p+3;]
etc

Para vizualizármos uma fórmula não-recursiva, é vantajoso colocar os valores iniciais de [;P(n;p);]  no seguinte formato:

[;P(1;p)=1^p-0^p;] 

[;P(2;p)=2^p-2.1^p+0^p;] 

[;P(3;p)=3^p-3.2^p+3.1^p-0^p;]

Notamos que os coeficientes de [;P(3;p);] são os mesmos de [;(p-1)^3;] e escrevemos [;Coef[ P(3;p)]= Coef[(p-1)^3];]. Será que [;Coef[P(n;p)]=Coef[(p-1)^n];] ? De fato. Vamos provar por indução. Está claro que para [;k=1;], [;k=2;] e [;k=3;] vale a afirmação, Suponhamos que valha para todo [;k<n;]. Vamos provar que vale para [;n;]. De fato,
[;P(n;p)=n^p-{n \choose n-1}P(n-1;p)-...-{n \choose 1}P(1;p)-0^p;]. Como, por hipótes, o teorema vale para todo [;k<n;] então [;Coef[P(n-i;p)]=Coef[(p-1)^{n-i}];] para todo [;i \leq n;]. Seja o polinômio. [;Q(p)=p^n-{n \choose n-1}(p-1)^{n-1}-{n \choose n-2}(p-1)^{n-2}-...-{n \choose 1}(p-1)-p^0;]. Fica claro que [;Coef[P(n;p)]=Coef[Q(p)];]. Na igualdade acima que define [;Q(p);], vamos somar à ambos os membro [;-(p^n) - (p-1)^n;] e daí obtemos [;Q(p)-(p^n)-(p-1)^n=-{(p-1)+1}^n;], donde [;Q(p)=(p-1)^n;] e como [;Q(p);] tem os coeficientes de [;P(n;p);] então [;P(n;p);] tem os coeficientes de [;(p-1)^n;] e, portanto, [;P(n;p)=n^p-{n \choose n-1}(n-1)^p+{n \choose n-2}(n-2)^p-...-(-1)^p0^p;]. E, da equivalência [; {n \choose n-k}={n \choose k};] , temos


[;P(n;p) = {n \choose 0}n^p-{n \choose 1}(n-1)^p+{n \choose 2}(n-2)^p-...+(-1)^{n-1}{n \choose {n-1}}1^p;]

_*_

Coeficientes combinativos: seja a igualdade

[;n^p=a_1{ n\choose 1}+a_2{ n\choose 2}+...+...+a_i{ n\choose i}+...+a_p{ n\choose p;] (1)
comparada com

[;n^p=P(1;p){n \choose 1}+P(2;p){n \choose 2}+...+P(i;p){n \choose i}+...+P(n;p){n \choose n};] (2)

Nesta última, foi estipulado que [;n \leq p;]. Porque? Se [;n>p;] é impossível preencher uma sequência de [;p;] termos onde todos os [;n;] elementos apareçam. Logo, se [;n>p;], [;P(n;p)=0;].
Na fórmula (2), admitindo válida para qualquer [;n \in \mathbb{N};], eliminaremos as parcelas [;P(i;p){ n \choose i}=0;]em que [;i>p;].  Desta forma, temos

[;n^p=P(1;p){n \choose 1}+P(2;p){n \choose 2}+...+P(i;p){n \choose i}+...+P(p;p){n \choose p};] (3) 

Comparando (3) com (1), concluímos que [;a_i=P(i;p);], com

[;a_i=P(i;p) = {i \choose 0}i^p-{i \choose 1}(i-1)^p+{i \choose 2}(i-2)^p-...+(-1)^{i-1} {i \choose {i-1}}1^p;]


Exemplo: fornecer uma fórmula combinativa para [;\sum_1^{n-1}n^5;] 

Resolução: temos que achar os coeficientes [;a_i;]  de

[;n^5=a_1{n \choose1}+ a_2{n \choose 2}+a_3{n \choose 3}+ a_4{n \choose 4}+ a_5{n \choose 5};] 

Usando a fórmula [;P(n;p);] , temos 

[;a_i=P(i;p) = {i \choose 0}i^p-{i \choose 1}(i-1)^p+{i \choose 2}(i-2)^p-...+(-1)^{i-1} {i \choose {i-1}}1^p;]
 

[;a_1=P(1;5)=1^5=1;]

[;a_2=P(2;5)=1.2^5-2.1^5=30;]

[;a_3=P(3;5)=1.3^5 -3.2^5+ 3.1^5=150;]

[;a_4=P(4;5)=1.4^5-4.3^5 +6.2^5 -4.1^5=240;]

[;a_5=P(5;5)=1.5^5-5.4^5+10.3^5-10.2^5-5.1^5=5!=120;]

 que são os números da  [;5^o;] linha do triângulo dos coeficientes combinativos.


Assim,  [;n^5={n \choose1}+ 30{n \choose 2}+150{n \choose 3}+ 240{n \choose 4}+ 120{n \choose 5};] 

e [;\sum_1^{n-1}n^5= {n \choose 2}+ 30{n \choose 3}+150{n \choose 4}+ 240{n \choose 5}+ 120{n \choose 6};]

Para saber mais: http://mathworld.wolfram.com/PowerSum.html

7 comentários:

  1. Oi Teixeira! Ficou ótimo! Mas acho que o título deveria ser algo como: "Fórmula Geral para Somatório de Potências" com subtítulo "Sum of Power (closed form)" os P(n;p) são coadjuvantes. Salvo melhor juízo, essa é a formula mais simples que encontrei na WEB. Algumas fórmulas de aparência mais simples exigem fórmulas recursivas e/ou infinitas... Obrigado

    ResponderExcluir
  2. Oi Teixeira! Acima onde se lê "Sum of Power" leia-se "Sum of Powers" OK

    ResponderExcluir
  3. Oi, Tavano! Obrigado.

    O assunto principal é P(n;p). Somatório é apenas uma das aplicações.

    Vc pode indicar o link da WEB onde encontrou algo parecido?

    ResponderExcluir
  4. Oi Teixeira! Ok! Coloque no Google "Power sum" e entre em "Wolfram Mathword" e na Wikipédia "Bernoulli Numbers" Lá diz que Bernoulli estava tentando resolver esse problema de soma de potências quando descobriu esses números e calculou os seis primeiros, diz também, que é a fórmula mais usada para esse cálculo. Obrigado

    ResponderExcluir
  5. Valeu, amigo Tavano! Fiz algumas pequenas modificações no texto e coloquei um link alternativo para os internautas.

    ResponderExcluir
  6. Muito bom, assim como todo conteúdo do blogue!

    ResponderExcluir