ELEMENTOS: 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:

tavano4 de abril de 2012 às 12:46
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
Respostas
tavano4 de abril de 2012 às 13:09
Oi Teixeira! Acima onde se lê "Sum of Power" leia-se "Sum of Powers" OK
ResponderExcluir
Respostas
Aloisio Teixeira4 de abril de 2012 às 13:48
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
Respostas
tavano5 de abril de 2012 às 10:27
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
Respostas
Aloisio Teixeira5 de abril de 2012 às 11:24
Valeu, amigo Tavano! Fiz algumas pequenas modificações no texto e coloquei um link alternativo para os internautas.
ResponderExcluir
Respostas
Matheus5 de agosto de 2012 às 13:50
Muito bom, assim como todo conteúdo do blogue!
ResponderExcluir
Respostas
Matheus5 de agosto de 2012 às 13:51
Parabéns!
ResponderExcluir
Respostas

Adicionar comentário

Páginas

terça-feira, 3 de abril de 2012

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

7 comentários:

V.O