Sums of Integers

Computing the sums of powers of the integers

useful in statistics and data reduction

S_r(n) \equiv \sum_{i=1}^n i^r
Note that for r!=0 S_r(n) = \sum_{i=0}^n i^r
and S_0(n) = 1+n

Link to Tabulation


The brute force method for computing the polynomial coefficients

1a S_r(n) \equiv \sum_{j=1}^n j^r definition of S_r(n)
1b \equiv \sum_{j=1}^{r+1}{b_j n^j} declaration of bj.There is no b0 because Sr(0) = 0and r+1 is highest power
2a S_r(n+1) = \sum_{j=1}^{n+1} j^r substitute n+1 for n in 1a
2b = (n+1)^r +  \sum_{j=1}^n j^r extract final term of sum
2c = {(n+1)}^r + S_r(n) apply 1a in reverse
2d = {(n+1)}^r +  \sum_{j=1}^{r+1}{b_jn^j} apply 1b
2e = \sum_{k=0}^r{\binom{r}{k}n^k}+\sum_{j=1}^{r+1}{b_j n^j} binomial expansion of 1st term
= \binom{r}{0}n^0+  \sum_{k=1}^r {\binom{r}{k}n^k} +\sum_{j=1}^{r+1}{b_jn^j}  +  b_{r+1}n^{r+1} extract first term of k sum and
last of j
= 1 +  \sum_{k=1}^r{(\binom{r}{k}+b_k)n^k }  +b_{r+1}n^{r+1} independent indexes can be
merged into a single summation
3a S_r(n+1) = \sum_{j=1}^{r+1}{b_j(n+1)^j} substitute n+1 for n in 1b
3b = \sum_{j=1}^{r+1}  {b_j(  \sum_{k=0}^j{\binom{j}{k}n^k})} binomial expansion
3c = \sum_{j=1}^{r+1}{\sum_{k=0}^j{b_j*\binom{j}{k}n^k} bj does not depend on
k

Since eqn 3* equals eqn 2* (1a=1b) we can write r+2 equations for the coefficient
of n^k where k=0..r+1

k from 2e from 3c equating coefficients of n^j
4a 0 1 = \sum_{j=1}^{r+1}{ b_j*\binom{j}{0}} the 0th term of the inner
loop of 3c is included for each j
4b = \sum_{j=1}^{r+1}{ b_j} \binom{j}{0}=1 for all x.
5 r+1 b_{r+1} = b_{r+1}*\binom{r+1}{r+1} in 3c only j=R+1 and k=j
generate an
R+1 term in the sum
b_{r+1} = b_{r+1}*1 not a useful equation!but we
had one more than we needed so we still have enough to solve
for all coefficients
6a p=1..R CR,p+bp = Sum[j=p..R+1]{bj*Cj,p} the inner sum of 3c has a term
with np when j is at least p, and has only one such term for
each j
6b CR,p+bp = bp*Cp,p+Sum[j=p+1..R+1]{bj*Cj,p} extract first term of summation
CR,p = Sum[j=p+1..R+1]{bj*Cj,p} Cp,p=1 so bp*Cp,p=bp
so bpcan be subracted from both sides
6c 1 = Sum[j=p+1..R+1]{bj*Cj,p/CR,p} divide both sides by CR,p
6d 1 = Sum[j=p+1..R+1]{bj*[j!(R-p)!/R!(j-p)!]} resolve Cx,y‘s into
factorials, cancelling p! term from each’s denominator
Solving
these equations is fairly straightforward in that bR+1
appears
by itself in an equation (p=R), and each lower order bj
appears in an
equation with just it and higher order terms.Therefore we can solve
the equations from highest order descending with simple algebra at each
step, no simultaneous solving is required.
7 p=R 1 = Sum[j=R+1..R+1]{bj*[j!(R-R)!/R!(j-R)!]}
= bR+1*[(R+1)!(R-R)!/R!(R+1-R)!] only term to sum is j=R+1
= bR+1*(R+1) resolve factorials
bR+1 = 1/(R+1) which is what you would expect
from integral calculus
8 p=1..R-1 1 = Sum[j=p+1..R]{bj*[j!(R-p)!/R!(j-p)!]}+[(R+1)!(R-p)!/R!(R+1-p)!]/(R+1) substitute 7 into 6d
= Sum[j=p+1..R]{bj*[j!(R-p)!/R!(j-p)!]}+(R+1)!(R-p)!/(R+1)!(R+1-p)! merge (R+1)! =(R+1)*R!
= Sum[j=p+1..R]{bj*[j!(R-p)!/R!(j-p)!]}+[(R-p)!/(R-p+1)!]
= Sum[j=p+1..R]{bj*[j!(R-p)!/R!(j-p)!]}+1/(R-p+1)

Each remaining equation will be of the form 1= bx * (factorials in R
and x) +
expression created by substituting all known bx’s solutions into the
definition eqn of 6d adjusting the summation range.

Expression = Sum[k=x+1..R+1]{bk*[k!(R-p)!/R!(k-p)!]} with
each bk symbol replaced with the known expression for it.

Rearranging terms gives:  bx= (1- expression)/ (4 factorials in R
and x)

9 bp+1 = (1-expression) / (p+1)!(R-p)!/R!(p+1-p)! term from 6d exposed
= (1-expression) / (p+1)p!(R-p)!/R! (n+1)! = (n+1) n! from
definition of ! and p+1-p = 1 and 1!=1
= (1-expression) / (p+1)/CR,p
= (CR,p/(p+1)) * (1-expression)

Let’s work some examples to check our algebra so far.

The q below is a convenient variable for condensing the algebra.

q bR-q (CR,p/(p+1)) *(1- sums
of      j!(R-p)!/R!(j-p)!  (see following
table)
)
0 bR = (CR,R-1/(R)) *(1-( 1/(0+2) ) )
= (R/R*1!) *(1-( 1/2 ) )
= 1 * 1/2
bR = 1/2 2nd
coefficient is always 1/2 regardless of power
1 bR-1 = (CR,R-2/(R-1)) *(1-( 1/(1+2) + 1/2 ) )
= (R(R-1)/(R-1)2!) *(1-( 1/3 + 1/2 ) )
= R/2 *(1- 5/6 )
= R/12 3rd
coefficient is simple
since
the 2nd feedback term is always 1/2 we can combine that with the (1- so
we start now with (1/2-
2 bR-2 = (CR,R-3/(R-2)) *(1/2-( 1/(2+2) +(2+1)/12 ) )
= (CR,R-3/(R-2)) *(1/2-( 1/2 ) )
= 0 4th coefficient is
always 0 !
3 bR-3 = (CR,R-4/(R-3)) *(1/2- 1/(3+2) + (3+1)/12 ) )
= (R(R-1)(R-2)/4! *(15/30-( 6/30 + 10/30 ) )
= -R(R-1)(R-2)/6! 6!=
720.
we can
skip use of the Cx,y symbol as we are always expanding it into its
factorials,and we will directly resolve the summed terms instead of showing the
fine detail of the substitutions
4 bR-4 = (R!/(R-4)!5!) *(1/2-( 1/6+5/12-1/12 ) )
= (R!/(R-4)!5!) *(6/12- (2+5-1)/12 )
= 0 6th coefficient is
always 0 !
5 bR-5 = (R!/(R-5)!6!) *(1/2-( 1/7+ 1/2-1/6 ) )
= R!/(R-5)!7!*6 7!*6 = 30240
6 bR-6 = (R!/(R-6)!7!) *(1/2-( 1/8+7/12-7/24+1/12 ) )
= 0 8th coefficient is
always 0! a pattern seems to be emerging

feedback components
calculation

formula * j! (R-p)! / R! (j-p)! net q=R-p-1
bR+1 1/(R+1) * (R+1)! (R-p)! / R! (R+1-p)! 1/(R+1-p) 1/(q+2)
bR 1/2 * R! (R-p)! / R! (R-p)! 1/2 1/2 1/Prod[i=2..2]
bR-1 R/12 * (R-1)! (R-p)! / R! (R-1-p)! (R-p)/12 (q+1)/12 2* Prod[i=q+1..q+1]/Prod[i=2..4]
bR-3 -R(R-1)(R-2)/720 * (R-3)! (R-p)! / R! (R-3-p)! (R-p)(R-p-1)(R-p-2)(-1/720) -(q+1)(q)(q-1)/6! -Prod[i=q-1..q+1]/Prod[i=2..6]
bR-5 R!/(R-5)!7!6 (R-5)! (R-p)! / R! (R-5-p)! (R-p)!/(R-5-p)!(1/6*7!) (q+1)!/(q-4)!6*7! (4/3)*Prod[i=q-3..q+1]/Prod[i=2..8]

The ‘expression’ of eqn 9 is a function of the step that can be reduced
to a rational number. That means the form of bp is a
combinatorial in R times a rational number.

That ‘expression’ also is zero for even values of our ‘q’ index.

Which means, that bR-2k = 0 for
k>=1.


Direct
proof of 4b: Sum[j=1..R+1]
{bj} =1

A: SR(1) = Sum[j=1..1]{jR} = 1R = 1
B: SR(1) = Sum[j=1..R+1]{bj1j} = Sum[j=1..R+1] {bj}
A=B so Sum[j=1..R+1] {bj} = 1

Checking the formulae

The column headers are derived from the algebra, the inline comments at
the ends of rows are the sum of the coefficients, which by 4c are equal
to 1.

power 1/ 1/ R/ R(R-1)(R-2)/ R(R-1)(R-2)(R-3)(R-4)/ R(R-1)(R-2)(R-3)(R-4)(R-5)(R-6)/ R(R-1)(R-2)(R-3)(R-4)(R-5)(R-6)(R-7)(R-8)/
(R+1) 2 12  sep 1 -5*6*4*3! 6*7*6*5! -5*6*8*7! 10*9!*66/5 BC is “Bernoulli
number”
= CR,0/2 CR,1/2*2*3 CR,3/-3*5*6 CR,5/6*7*6 CR,7/8*(-5*6) CR,9/10*11*6/5 CR,C/(C+1)BC
0 n
1 1/2n2 +1/2n 1-1/2
=
1/2
2 1/3n3 +1/2n2 + 1/6n 1-1/3-1/2
=
1/6
=
2/x=>x=12
3 1/4n4 +1/2n3 + 1/4n2
4 1/5n5 +1/2n4 +
1/3n3
− 1/30n 1-(1/5+1/2+1/3)=(30-(6+15+10))/30
=-1/30=-(4*3*2)/x =>x = 24*30 = 720 = 6!
5 1/6n6 +1/2n5 + 5/12n4 − 1/12n2
6 1/7n7 +1/2n6 + 1/2n5 − 1/6 n3 + 1/42 n 1-(1/7+1/2+1/2-1/6)=(42-6-24-24+7)/42=1/42=6*5*4*3*2/x =>x=42*6!=6*7!
7 1/8n8 +1/2n7 + 7/12n6 − 7/24n4 + 1/12 n2
8 1/9n9 +1/2n8 + 2/3n7 – 7/15n5 + 2/9 n3
1/30 n
1-(1/9+1/2+2/3-7/15+2/9)=(90-10-45-60+42-20)/90=-3/90=-1/30=8!/x => x=-30*8!
9 1/10n10 +1/2n9 + 3/4n8 – 7/10n6 1/2n4 – 3/20n2
10 1/11n11 +1/2n10 +
5/6n9
–  n7 +  n5 – 1/2n3 + 5/66n 5/66
=
10!/x
=>x=10!*66/5
11 1/12n12 +1/2n11 +11/12n10 – 11/8n8 +  11/6n6 – 11/8n4 + 5/12 n2

Incremental computation of all coefficients up to power of interest:

  1. coefficient(row, col>=row)=0
  2. coefficient(row,0) is always 1/row. (could be folded into teh
    subsequent rules, but is worth optimizing)
  3. coefficient(row,1) is always 1/2. since we will be computing
    1-sum(…) where … includes this 1/2
  4. coefficient(row, col>1 &&odd)=0
  5. for col<row
    coefficient(row,col>2)=coefficient(row,col)*row/(row-col)
  6. if row is even then
    coefficient(row,row-1)=1/2-1/(row+1)-sum(col=1..row-3){coefficient(row,col)}

Once the first non-zero quantity in a column is calculated the
remaining terms in that column can be calculated.

The first non-zero quantity in a column is calculated from the already
calculated members of its row. So another algorithm is:

  1. coefficient(row, col>=row)=0
  2. coefficient(row,0) is always 1/row. (could be folded into teh
    subsequent rules, but is worth optimizing)
  3. coefficient(row,1) is always 1/2. since we will be computing
    1-sum(…) where … includes this 1/2
  4. coefficient(row, col>1 &&odd)=0
  5. for col<row
    coefficient(row,col>2)=coefficient(row,col)*row/(row-col)
  6. if row is even then
    coefficient(row,row-1)=1/2-1/(row+1)-sum(col=1..row-3){coefficient(row,col)}
    (=
    Bournoulli
    number (row) )

If you don’t need all the lower
order Sk’s then use this method, derived by T.J. Pfaff from
combinatorial reasoning.

Pfaff’s method counts combinations via two different approaches and
shows that they are equal.

Sk(n) = Sum [j=1 .. k]{ Sum[i=0..j] {(-1)j-i
ikCj,iCn+1,j+1}}
TJ Pfaff
if k>0 = Sum [j=1 .. k]{ Cn+1,j+1 * Sum[i=1..j]
{(-1)j-i ikCj,i}}
can drop useless 0 term of inner
sumand move term that doesn’t depend upon sum outside of the sum
S1(n) = Sum [j=1 .. 1]{ Cn+1,j+1 * Sum[i=1..j]
{(-1)j-i
i1Cj,i}}
k->1
= Cn+1,1+1 * Sum[i=1..1]
{(-1)1-i i1C1,i}
expand sum over j
= Cn+1,2 * (-1)1-1
1C1,1
expand sums over i
= Cn+1,2 =
(n+1)(n)/2
correct!
S2(n) = Sum [j=1 .. 2]{ Sum[i=1..j] {(-1)j-i
i2Cj,iCn+1,j+1}}
R->2
= Cn+1,1+1 *
Sum[i=1..1] {(-1)1-i i2C1,i}+Cn+1,2+1 * Sum[i=1..2] {(-1)2-i i2C2,i}
expand sum over j
= Cn+1,2* (-1)1-1 12C1,1
+Cn+1,3 * ((-1)2-1 12C2,1
+(-1)2-2 22C2,2 )
expand sums over i
Cn+1,2 + Cn+1,3 *(-2+ 4) simple reductions
Cn+1,2 +2*Cn+1,2
* (n-1)/3
Cx,r+1 = Cx,r (x-r)/(r+1)
Cn+1,2 *(1+(2*(n-1)/3)
Cn+1,2 *(3+2n-2)/3)
Cn+1,2 *(2n+1)/3
n(n+1)*(2n+1)/(2*3) correct!

Pfaff’s approach readily
generates the expressions factored.

power integer factorization convenient relationships nested monomial form
1 n(n+1)/2 S1
2 n(n+1)(2n+1)/6 S1*(2n+1)/3
3 n2(n+1)2/4 S12
4 n(n+1)(2n+1)(3n2+3n-1)/(6*5) S2*(3n2+3n-1)/5 S2*((n+1)3n-1)/5
5 n2(n+1)2 (2n2+2n-1)/(4*3) S3*(2n2+2n-1)/3 S3*((n+1)2n-1)/3
6 n(n+1)(2n+1)(3n4+6n3-3n+1)/(6*7) S2*(3n4+6n3-3n+1)/7 S2*((n+2)n2-1)3n+1)/7
7 n2(n+1)2(3n4+6n3-n2-4n+2)/(4*6) S3*(3n4+6n3-n2-4n+2)/6 S3*((((n+2)3n-1)n-4)n+2)/6
8 n(n+1)(2n+1)(5n6+15n5+5n4-15n3-n2+9n-3)/(6*15) S2*(5n6+15n5+5n4-15n3-n2+9n-3)/15 S2*((((((n+3)n+1)n-3)5n-1)n+9)n-3)/15
9 n2(n+1)2(n2+n-1)(2n4+4n3-n2-3n+3)/(4*5) S3*(n2+n-1)(2n4+4n3-n2-3n+3)/5 S3*((n+1)n-1)*((((n+2)2n-1)n-3)n+3)/5
10 n(n+1)(2n+1)(n2+n-1)(3n6+9n5+2n4-11n3+3n2+10n-5)/(6*11) S2*(n2+n-1)(3n6+9n5+2n4-11n3+3n2+10n-5)/11 S3*((n+1)n-1)*((((((n+3)3n+2)n-11)n+3)n+10)n-5)/11

Observations

  • all sums have a factor of n as the ‘0’ term of the polynomial has
    a
    coefficient of 0.
  • all sums for R>0 are also divisible by (n+1).
  • all sums for Even R>0 are divisible by S2: S2k(n)=S2(n)Rk(n)
    where
    Rk(n) is a polynomial of degree 2*(k-1).
  • all sums for Odd R>3 are divisible by S3: S2k+1(n)=S3(n)*Tk(n) where Tk(n) is a
    polynomial of degree 2*k.


SR(n)=Sum[i=1..R]{
Sum[j=0..i]{-1j (i-j)R
Cn+p-i+1,n-i CR+1,j}}

sumsOfPowersOfIntegers

Computing the sums of powers of the integers

useful in statistics and data reduction

S_r(n) \equiv \sum_{i=1}^n i^r
Note that for r!=0 S_r(n) = \sum_{i=0}^n i^r
and S_0(n) = 1+n


first, a tabulation

power as sum factored
0 n n
1 1/2n2 + 1/2n n(n+1)/2
2 1/3n3 + 1/2n2
+ 1/6n
n(n+1)(2n+1)/6
3 1/4n4 + 1/2n3
+ 1/4n2
n2(n+1)2/4
4 1/5n5 + 1/2n4
+
1/3n3 − 1/30n
n(n+1)(2n+1)(3n2+3n-1)/(6*5)
5 1/6n6 + 1/2n5
+ 5/12n4− 1/12 n2
n2(n+1)2 (2n2+2n-1)/(4*3)
6 1/7n7 + 1/2n6
+ 1/2n5 − 1/6  n3 + 1/42 n
n(n+1)(2n+1)(3n4+6n3-3n+1)/(6*7)
7 1/8n8 + 1/2n7
+ 7/12n6− 7/24 n4 + 1/12 n2
n2(n+1)2(3n4+6n3-n2-4n+2)/(4*6)
8 1/9n9 + 1/2n8
+ 2/3n7 – 7/15 n5 + 2/9  n3
1/30 n
n(n+1)(2n+1)(5n6+15n5+5n4-15n3-n2+9n-3)/(6*15)
9 1/10n10+1/2n9
+ 3/4n8 – 7/10 n6 + 1/2n4 – 3/20n2
n2(n+1)2(n2+n-1)(2n4+4n3-n2-3n+3)/(4*5)
10 1/11n11+1/2n10+
5/6n9 –      n7 +  n5
– 1/2n3 + 5/66 n
n(n+1)(2n+1)(n2+n-1)(3n6+9n5+2n4-11n3+3n2+10n-5)/(6*11)

Some convenient relationships exist:

S_3 = S_1^2

For odd r>=3: $latex   S_r = S_3*R_{r-2}$ where R_k is a polynomial of degree k.

For even r>=2 S_r = S_2*T_{r-2} where T_k is a
polynomial of degree k.


The brute force method

1a S_r(n) \equiv \sum_{j=1}^n j^r definition of S_r(n)
1b \equiv \sum_{j=1}^{r+1}{b_jn^j} declaration of bj.There is no b0 because Sr(0) = 0and r+1 is highest power
2a S_r(n+1) = \sum_{j=1}^{n+1} j^r substitute n+1 for n in 1a
2b = {(n+1)}^r +  \sum_{j=1}^n j^r extract final term of sum
2c = {(n+1)}^r +   S_r(n) apply 1a in reverse
2d = {(n+1)}^r +  \sum_{j=1}^{r+1}{b_jn^j} apply 1b
2e = \sum_{k=0}^r\binom{r}{k}n^k}+\sum_{j=1}^{r+1}{b_jn^j} binomial expansion of 1st term
= \binom{r}{0}n^0+  \sum_{k=1}^r\binom{r}{k}n^k} +\sum_{j=1}^{r+1}{b_jn^j}  +  b_{r+1}n^{r+1} extract first term of k sum and
last of j
= 1 +  \sum_{k=1}^r{(\binom{r}{k}+b_k)n^k }  +b_{r+1}n^{r+1} independent indexes can be
merged into a single summation
3a S_r(n+1) = \sum_{j=1}^{r+1}{b_j(n+1)^j} substitute n+1 for n in 1b
3b = $latex \sum_{j=1}^{r+1}  {bj(
\sum_{k=0}^j{\binom{j}{k}n^k})}$
binomial expansion
3c = \sum_{j=1}^{r+1}{\sum_{k=0}^j{b_j*\binom{j}{k}n^k} bj does not depend on
k

Since eqn 3* equals eqn 2* (1a=1b) we can write
R+2
equations for the coefficient
of  nk where k=0..R+1

k from 2e from 3c equating coefficients of nj
4a 0 1 = Sum[j=1..R+1]{ bj*Cj,0} the 0th term of the inner
loop of 3c is included for each j
4b = Sum[j=1..R+1] {bj} Cx,0=1 for all x.
5 R+1 bR+1 = bR+1*CR+1,R+1 in 3c only j=R+1 and k=j
generate an
R+1 term in the sum
bR+1 = bR+1*1 not a useful equation!but we
had one more than we needed so we still have enough to solve
for all coefficients
6a p=1..R CR,p+bp = Sum[j=p..R+1]{bj*Cj,p} the inner sum of 3c has a term
with np when j is at least p, and has only one such term for
each j
6b CR,p+bp = bp*Cp,p+Sum[j=p+1..R+1]{bj*Cj,p} extract first term of summation
CR,p = Sum[j=p+1..R+1]{bj*Cj,p} Cp,p=1 so bp*Cp,p=bp
so bpcan be subracted from both sides
6c 1 = Sum[j=p+1..R+1]{bj*Cj,p/CR,p} divide both sides by CR,p
6d 1 = Sum[j=p+1..R+1]{bj*[j!(R-p)!/R!(j-p)!]} resolve Cx,y‘s into
factorials, cancelling p! term from each’s denominator
Solving
these equations is fairly straightforward in that bR+1
appears
by itself in an equation (p=R), and each lower order bj
appears in an
equation with just it and higher order terms.Therefore we can solve
the equations from highest order descending with simple algebra at each
step, no simultaneous solving is required.
7 p=R 1 = Sum[j=R+1..R+1]{bj*[j!(R-R)!/R!(j-R)!]}
= bR+1*[(R+1)!(R-R)!/R!(R+1-R)!] only term to sum is j=R+1
= bR+1*(R+1) resolve factorials
bR+1 = 1/(R+1) which is what you would expect
from integral calculus
8 p=1..R-1 1 = Sum[j=p+1..R]{bj*[j!(R-p)!/R!(j-p)!]}+[(R+1)!(R-p)!/R!(R+1-p)!]/(R+1) substitute 7 into 6d
= Sum[j=p+1..R]{bj*[j!(R-p)!/R!(j-p)!]}+(R+1)!(R-p)!/(R+1)!(R+1-p)! merge (R+1)! =(R+1)*R!
= Sum[j=p+1..R]{bj*[j!(R-p)!/R!(j-p)!]}+[(R-p)!/(R-p+1)!]
= Sum[j=p+1..R]{bj*[j!(R-p)!/R!(j-p)!]}+1/(R-p+1)

Each remaining equation will be of the form 1= bx * (factorials in R
and x) +
expression created by substituting all known bx’s solutions into the
definition eqn of 6d adjusting the summation range.

Expression = Sum[k=x+1..R+1]{bk*[k!(R-p)!/R!(k-p)!]} with
each bk symbol replaced with the known expression for it.

Rearranging terms gives:  bx= (1- expression)/ (4 factorials in R
and x)

9 bp+1 = (1-expression) / (p+1)!(R-p)!/R!(p+1-p)! term from 6d exposed
= (1-expression) / (p+1)p!(R-p)!/R! (n+1)! = (n+1) n! from
definition of ! and p+1-p = 1 and 1!=1
= (1-expression) / (p+1)/CR,p
= (CR,p/(p+1)) * (1-expression)

Let’s work some examples to check our algebra so far.

The q below is a convenient variable for condensing the algebra.

q bR-q (CR,p/(p+1)) *(1- sums
of      j!(R-p)!/R!(j-p)!  (see following
table)
)
0 bR = (CR,R-1/(R)) *(1-( 1/(0+2) ) )
= (R/R*1!) *(1-( 1/2 ) )
= 1 * 1/2
bR = 1/2 2nd
coefficient is always 1/2 regardless of power
1 bR-1 = (CR,R-2/(R-1)) *(1-( 1/(1+2) + 1/2 ) )
= (R(R-1)/(R-1)2!) *(1-( 1/3 + 1/2 ) )
= R/2 *(1- 5/6 )
= R/12 3rd
coefficient is simple
since
the 2nd feedback term is always 1/2 we can combine that with the (1- so
we start now with (1/2-
2 bR-2 = (CR,R-3/(R-2)) *(1/2-( 1/(2+2) +(2+1)/12 ) )
= (CR,R-3/(R-2)) *(1/2-( 1/2 ) )
= 0 4th coefficient is
always 0 !
3 bR-3 = (CR,R-4/(R-3)) *(1/2- 1/(3+2) + (3+1)/12 ) )
= (R(R-1)(R-2)/4! *(15/30-( 6/30 + 10/30 ) )
= -R(R-1)(R-2)/6! 6!=
720.
we can
skip use of the Cx,y symbol as we are always expanding it into its
factorials,and we will directly resolve the summed terms instead of showing the
fine detail of the substitutions
4 bR-4 = (R!/(R-4)!5!) *(1/2-( 1/6+5/12-1/12 ) )
= (R!/(R-4)!5!) *(6/12- (2+5-1)/12 )
= 0 6th coefficient is
always 0 !
5 bR-5 = (R!/(R-5)!6!) *(1/2-( 1/7+ 1/2-1/6 ) )
= R!/(R-5)!7!*6 7!*6 = 30240
6 bR-6 = (R!/(R-6)!7!) *(1/2-( 1/8+7/12-7/24+1/12 ) )
= 0 8th coefficient is
always 0! a pattern seems to be emerging

feedback components
calculation

formula * j! (R-p)! / R! (j-p)! net q=R-p-1
bR+1 1/(R+1) * (R+1)! (R-p)! / R! (R+1-p)! 1/(R+1-p) 1/(q+2)
bR 1/2 * R! (R-p)! / R! (R-p)! 1/2 1/2 1/Prod[i=2..2]
bR-1 R/12 * (R-1)! (R-p)! / R! (R-1-p)! (R-p)/12 (q+1)/12 2* Prod[i=q+1..q+1]/Prod[i=2..4]
bR-3 -R(R-1)(R-2)/720 * (R-3)! (R-p)! / R! (R-3-p)! (R-p)(R-p-1)(R-p-2)(-1/720) -(q+1)(q)(q-1)/6! -Prod[i=q-1..q+1]/Prod[i=2..6]
bR-5 R!/(R-5)!7!6 (R-5)! (R-p)! / R! (R-5-p)! (R-p)!/(R-5-p)!(1/6*7!) (q+1)!/(q-4)!6*7! (4/3)*Prod[i=q-3..q+1]/Prod[i=2..8]

The ‘expression’ of eqn 9 is a function of the step that can be reduced
to a rational number. That means the form of bp is a
combinatorial in R times a rational number.

That ‘expression’ also is zero for even values of our ‘q’ index.

Which means, that bR-2k = 0 for
k>=1.


Direct
proof of 4b: Sum[j=1..R+1]
{bj} =1

A: SR(1) = Sum[j=1..1]{jR} = 1R = 1
B: SR(1) = Sum[j=1..R+1]{bj1j} = Sum[j=1..R+1] {bj}
A=B so Sum[j=1..R+1] {bj} = 1

Checking the formulae

The column headers are derived from the algebra, the inline comments at
the ends of rows are the sum of the coefficients, which by 4c are equal
to 1.

power 1/ 1/ R/ R(R-1)(R-2)/ R(R-1)(R-2)(R-3)(R-4)/ R(R-1)(R-2)(R-3)(R-4)(R-5)(R-6)/ R(R-1)(R-2)(R-3)(R-4)(R-5)(R-6)(R-7)(R-8)/
(R+1) 2 12  sep 1 -5*6*4*3! 6*7*6*5! -5*6*8*7! 10*9!*66/5 BC is “Bernoulli
number”
= CR,0/2 CR,1/2*2*3 CR,3/-3*5*6 CR,5/6*7*6 CR,7/8*(-5*6) CR,9/10*11*6/5 CR,C/(C+1)BC
0 n
1 1/2n2 +1/2n 1-1/2
=
1/2
2 1/3n3 +1/2n2 + 1/6n 1-1/3-1/2
=
1/6
=
2/x=>x=12
3 1/4n4 +1/2n3 + 1/4n2
4 1/5n5 +1/2n4 +
1/3n3
− 1/30n 1-(1/5+1/2+1/3)=(30-(6+15+10))/30
=-1/30=-(4*3*2)/x =>x = 24*30 = 720 = 6!
5 1/6n6 +1/2n5 + 5/12n4 − 1/12n2
6 1/7n7 +1/2n6 + 1/2n5 − 1/6 n3 + 1/42 n 1-(1/7+1/2+1/2-1/6)=(42-6-24-24+7)/42=1/42=6*5*4*3*2/x =>x=42*6!=6*7!
7 1/8n8 +1/2n7 + 7/12n6 − 7/24n4 + 1/12 n2
8 1/9n9 +1/2n8 + 2/3n7 – 7/15n5 + 2/9 n3
1/30 n
1-(1/9+1/2+2/3-7/15+2/9)=(90-10-45-60+42-20)/90=-3/90=-1/30=8!/x => x=-30*8!
9 1/10n10 +1/2n9 + 3/4n8 – 7/10n6 1/2n4 – 3/20n2
10 1/11n11 +1/2n10 +
5/6n9
–  n7 +  n5 – 1/2n3 + 5/66n 5/66
=
10!/x
=>x=10!*66/5
11 1/12n12 +1/2n11 +11/12n10 – 11/8n8 +  11/6n6 – 11/8n4 + 5/12 n2

Incremental computation of all coefficients up to power of interest:

  1. coefficient(row, col>=row)=0
  2. coefficient(row,0) is always 1/row. (could be folded into teh
    subsequent rules, but is worth optimizing)
  3. coefficient(row,1) is always 1/2. since we will be computing
    1-sum(…) where … includes this 1/2
  4. coefficient(row, col>1 &&odd)=0
  5. for col<row
    coefficient(row,col>2)=coefficient(row,col)*row/(row-col)
  6. if row is even then
    coefficient(row,row-1)=1/2-1/(row+1)-sum(col=1..row-3){coefficient(row,col)}

Once the first non-zero quantity in a column is calculated the
remaining terms in that column can be calculated.

The first non-zero quantity in a column is calculated from the already
calculated members of its row. So another algorithm is:

  1. coefficient(row, col>=row)=0
  2. coefficient(row,0) is always 1/row. (could be folded into teh
    subsequent rules, but is worth optimizing)
  3. coefficient(row,1) is always 1/2. since we will be computing
    1-sum(…) where … includes this 1/2
  4. coefficient(row, col>1 &&odd)=0
  5. for col<row
    coefficient(row,col>2)=coefficient(row,col)*row/(row-col)
  6. if row is even then
    coefficient(row,row-1)=1/2-1/(row+1)-sum(col=1..row-3){coefficient(row,col)}
    (=
    Bournoulli
    number (row) )

If you don’t need all the lower
order Sk’s then use this method, derived by T.J. Pfaff from
combinatorial reasoning.

Pfaff’s method counts combinations via two different approaches and
shows that they are equal.

Sk(n) = Sum [j=1 .. k]{ Sum[i=0..j] {(-1)j-i
ikCj,iCn+1,j+1}}
TJ Pfaff
if k>0 = Sum [j=1 .. k]{ Cn+1,j+1 * Sum[i=1..j]
{(-1)j-i ikCj,i}}
can drop useless 0 term of inner
sumand move term that doesn’t depend upon sum outside of the sum
S1(n) = Sum [j=1 .. 1]{ Cn+1,j+1 * Sum[i=1..j]
{(-1)j-i
i1Cj,i}}
k->1
= Cn+1,1+1 * Sum[i=1..1]
{(-1)1-i i1C1,i}
expand sum over j
= Cn+1,2 * (-1)1-1
1C1,1
expand sums over i
= Cn+1,2 =
(n+1)(n)/2
correct!
S2(n) = Sum [j=1 .. 2]{ Sum[i=1..j] {(-1)j-i
i2Cj,iCn+1,j+1}}
R->2
= Cn+1,1+1 *
Sum[i=1..1] {(-1)1-i i2C1,i}+Cn+1,2+1 * Sum[i=1..2] {(-1)2-i i2C2,i}
expand sum over j
= Cn+1,2* (-1)1-1 12C1,1
+Cn+1,3 * ((-1)2-1 12C2,1
+(-1)2-2 22C2,2 )
expand sums over i
Cn+1,2 + Cn+1,3 *(-2+ 4) simple reductions
Cn+1,2 +2*Cn+1,2
* (n-1)/3
Cx,r+1 = Cx,r (x-r)/(r+1)
Cn+1,2 *(1+(2*(n-1)/3)
Cn+1,2 *(3+2n-2)/3)
Cn+1,2 *(2n+1)/3
n(n+1)*(2n+1)/(2*3) correct!

Pfaff’s approach readily
generates the expressions factored.

power integer factorization convenient relationships nested monomial form
1 n(n+1)/2 S1
2 n(n+1)(2n+1)/6 S1*(2n+1)/3
3 n2(n+1)2/4 S12
4 n(n+1)(2n+1)(3n2+3n-1)/(6*5) S2*(3n2+3n-1)/5 S2*((n+1)3n-1)/5
5 n2(n+1)2 (2n2+2n-1)/(4*3) S3*(2n2+2n-1)/3 S3*((n+1)2n-1)/3
6 n(n+1)(2n+1)(3n4+6n3-3n+1)/(6*7) S2*(3n4+6n3-3n+1)/7 S2*((n+2)n2-1)3n+1)/7
7 n2(n+1)2(3n4+6n3-n2-4n+2)/(4*6) S3*(3n4+6n3-n2-4n+2)/6 S3*((((n+2)3n-1)n-4)n+2)/6
8 n(n+1)(2n+1)(5n6+15n5+5n4-15n3-n2+9n-3)/(6*15) S2*(5n6+15n5+5n4-15n3-n2+9n-3)/15 S2*((((((n+3)n+1)n-3)5n-1)n+9)n-3)/15
9 n2(n+1)2(n2+n-1)(2n4+4n3-n2-3n+3)/(4*5) S3*(n2+n-1)(2n4+4n3-n2-3n+3)/5 S3*((n+1)n-1)*((((n+2)2n-1)n-3)n+3)/5
10 n(n+1)(2n+1)(n2+n-1)(3n6+9n5+2n4-11n3+3n2+10n-5)/(6*11) S2*(n2+n-1)(3n6+9n5+2n4-11n3+3n2+10n-5)/11 S3*((n+1)n-1)*((((((n+3)3n+2)n-11)n+3)n+10)n-5)/11

Observations

  • all sums have a factor of n as the ‘0’ term of the polynomial has
    a
    coefficient of 0.
  • all sums for R>0 are also divisible by (n+1).
  • all sums for Even R>0 are divisible by S2: S2k(n)=S2(n)Rk(n)
    where
    Rk(n) is a polynomial of degree 2*(k-1).
  • all sums for Odd R>3 are divisible by S3: S2k+1(n)=S3(n)*Tk(n) where Tk(n) is a
    polynomial of degree 2*k.


SR(n)=Sum[i=1..R]{
Sum[j=0..i]{-1j (i-j)R
Cn+p-i+1,n-i CR+1,j}}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s