SiteMap of SciRealm | About John | Send email to JohnJohn's Science, Math, Philosophy Stuff: |
4-Vectors |
Ambigrams |
Antipodes |
Covert Ops Fragments |
Cyrillic Projector |
Forced Induction (Sums Of Powers Of Integers) |
Frontiers |
IFS Fractals |
JavaScript Graphics |
JavaScript Graphics Using Table |
Kid Science |
Kryptos |
Photography |
Prime Sieve |
QM from SR |
QM from SR-Simple RoadMap |
Quantum Phase |
Quotes |
RuneQuest Cipher Challenge |
Secret Codes & Ciphers |
Scientific Calculator |
Science+Math |
Sci-Pan Pantheist Poems |
Stereograms |
Turkish Grammar
The Science Realm: John's Virtual Sci-Tech Universe |
May the treasures buried herein spark the fires of imagination like the twinkling jewels of celestial light crowning the midnight sky...
Quantum Mechanics is derivable from Special Relativity
See QM from SR-Simple RoadMap
***Learn, Discover, Explore***
Melike Wilson Art
Site last modified: 2015-Apr-25 |

Note: This work is basically finished (although I somehow keep managing to add more to it...),

but if you notice errors or have comments, please let me know

METHOD OF FORCED INDUCTION (or GENERATIVE INDUCTION)

used to calculate the Sums of Powers of Integers

N

Sum[ x^{n}]

x=1

**Normally, the method of induction is used to logically prove that a given mathematical
or symbolic relation is true, after the relation has already been found by other methods.
However, in this analysis, the method of Forced Induction (or Generative Induction) will
be introduced to force a relation to be true. When used to calculate the sum of integers
to a given power, the result it gives is very powerful and quite elegant. It basically
generates the general expression for the sum of integers to any positive integer power. I
have never seen the general expression from any other method.
Notes/Usage:
**N = # of terms in the sum

n = power of the integers in the sum

Sum[x

Binom[a,b] = Binomial function = a!/[b!(a-b)!)]

LHS = Left-Hand Side, RHS = Right-Hand Side

delta function

What is the sum of the 1

Well, there are a couple of ways to calculate this...

One is to actually add all of these numbers one-by-one

1+2+3+...+998+999+1000 = 500500

Or, we can be clever and see if there is a easier way that will do the counting for us...

First, the

N

Sum[ x ] = N^{2}/2+N/2

x=1

Mathematical Induction can be used in the following manner to prove this relation true.

**Step 1**: Show that the first case is true. So, set N
equal to 1.

1

Sum[ x ] = 1^{2}/2+1/2

x=1

1 = 1/2+1/2

1 = 1 True!

**Step 2**: Show that the subsequent cases are true. So,
set N to the value N+1.

N+1

Sum[ x ] = (N+1)^{2}/2+(N+1)/2

x=1

N

Sum[ x ]+(N+1) = [(N^{2}+2N+1)+(N+1)]/2

x=1

(N^{2}/2+N/2)+(N+1) = (N^{2}/2+3N/2+1)

(N^{2}/2+3N/2+1) = (N^{2}/2+3N/2+1)

**Proof Complete!**

Therefore, the relation is also true for all integer values greater than 1; N=1 proves
N=2, N=2 proves N=3, N=3 proves N=4, etc. assuming that N=1 is true, which was shown in
the first step. Thus, in the last step, the formula is proven true for all positive
integers. This is the manner in which standard method of induction is used.

N

Sum[ x ] = N^{2}/2+N/2

x=1

1000

Sum[ x ] = 1000^{2}/2+1000/2 = 500500

x=1

Next, the Method of Forced Induction will be demonstrated for a specific case. Let us say that one wants to sum the first N integers to the 2

N 3

Sum[ x^{2}] =Sum[ c_{i}N^{i}] = c_{1}N^{1}+c_{2}N^{2}+c_{3}N^{3}

x=1 i=1

where the c_{i}'s are constants to be determined.

**Step 1**: Force the first case to be true. So, set N
equal to 1.

1

Sum[ x^{2}] = c_{1}1^{1}+c_{2}1^{2}+c_{3}1^{3}

x=1

1^{2}= c_{1}1^{1}+c_{2}1^{2}+c_{3}1^{3}

1 = c_{1}+c_{2}+c_{3}

so the sum of the c_{i}'s equals 1.

**Step 2**: Force the subsequent cases to be true. So, set
N to the value N+1.

N+1

Sum[ x^{2}] = c_{1}(N+1)^{1}+c_{2}(N+1)^{2}+c_{3}(N+1)^{3}

x=1

N

Sum[ x^{2}]+(N+1)^{2}= c_{1}(N+1)^{1}+c_{2}(N+1)^{2}+c_{3}(N+1)^{3}

x=1

c_{1}N^{1}+c_{2}N^{2}+c_{3}N^{3}+(N+1)^{2}= c_{1}(N+1)^{1}+c_{2}(N+1)^{2}+c_{3}(N+1)^{3}

c_{1}(N+1)^{1}+c_{2}(N+1)^{2}+c_{3}(N+1)^{3}-c_{1}N^{1}-c_{2}N^{2}-c_{3}N^{3 }= (N+1)^{2}

c_{1}N^{1}+c_{1}+c_{2}N^{2}+2c_{2}N+c_{2}+c_{3}N^{3}+3c_{3}N^{2}+3c_{3}N+c_{3}-c_{1}N^{1}-c_{2}N^{2}-c_{3}N^{3 }= N^{2}+2N+1_{ }c_{1}+2c_{2}N+c_{2}+3c_{3}N^{2}+3c_{3}N+c_{3}= N^{2}+2N+1

Now let's rewrite the last equation in terms of the powers of N.

(3c_{3}-1) N^{2}+(2c_{2}+3c_{3}-2) N^{1}+(c_{1}+c_{2}+c_{3}-1) N^{0}= 0

Now then, we want the last equation to hold for any value of N. Therefore, one must set
the coefficients of the N's to zero separately. For this case, that will give us 3
equations to solve. Let's rewrite the equations to a nicer [matrix] form.

3c_{3}= 1

2c_{2}+3c_{3}= 2

1c_{1}+1c_{2}+1c_{3}= 1

One now has an already matrix-triangulized set of linear equations for the c_{i}'s
which are independent of the value of N. Also note that condition from step 1 is satisfied
automatically by the last equation. These equations are easily solved to give: c_{1}=1/6,
c_{2}=1/2, c_{3}=1/3

Therefore, the sum of squared integers is:

N

Sum[ x^{2}] = N^{3}/3+ N^{2}/2+ N^{1}/6

x=1

This equation is True for all integers N>=1 by construction using the method of forced
induction.

Now, the extreme power of the Method of Forced Induction, in regard to the sums of powers of integers, lies in the fact that it can be used very generally to generate the matrix-triangulized equations for any positive integer power. A solution of the following form is assumed:

N n+1

Sum[ x^{n}] =Sum[ c_{i}N^{i}]

x=1 i=1

**Step 1**: Force the first case to be true. So, set N
equal to 1.

1 n+1

Sum[ x^{n}] =Sum[ c_{i}1^{i}]

x=1 i=1

n+1

1^{n}=Sum[ c_{i}]

i=1

n+1

Sum[ c_{i}] = (c_{1}+c_{2}+ ... + c_{n+1}) = 1

i=1

As before, the sum of the c_{i}'s must equal 1.

**Step 2**: Force the subsequent cases to be true. So, set
N to the value N+1.

N+1 n+1

Sum[ x^{n}] =Sum[ c_{i}(N+1)^{i}]

x=1 i=1

N n+1

Sum[ x^{n}]+(N+1)^{n}=Sum[ c_{i}(N+1)^{i}]

x=1 i=1

n+1 N

Sum[ c_{i}(N+1)^{i}]-Sum[ x^{n}] = (N+1)^{n}

i=1 x=1

Using the assumed solution form on the middle term:

n+1 n+1

Sum[ c_{i}(N+1)^{i}]-Sum[ c_{i}N^{i}] = (N+1)^{n}

i=1 i=1

n+1

Sum[ c_{i}( (N+1)^{i}- N^{i}) ] = (N+1)^{n}

i=1

Using the binomial expansion on the LHS:

n+1 i

Sum[ c_{i}(Sum[Binom[i,j] N^{j}] - N^{i}) ] = (N+1)^{n}

i=1 j=0

n+1 i-1

Sum[ c_{i}(Sum[Binom[i,j] N^{j}] +Binom[i,i] N^{i}- N^{i}) ] = (N+1)^{n}

i=1 j=0

n+1 i-1

Sum[ c_{i}(Sum[Binom[i,j] N^{j}) ] = (N+1)^{n}

i=1 j=0

Using the binomial expansion on the RHS:

n+1 i-1 n

Sum[ c_{i}(Sum[Binom[i,j] N^{j}) ] =Sum[Binom[n,k] N^{k}]

i=1 j=0 k=0

Now expand in terms of powers of N:

n+1

Sum[ c_{i}(Binom[i,0] N^{0}+Binom[i,1] N^{1}+...+Binom[i,i-1] N^{i-1}) ] =Binom[n,0] N^{0}+Binom[n,1] N^{1}+ ... +Binom[n,n] N^{n}

i=1

Again, one gathers the terms for each power of N (I have left out the exact indices...):

(Binom[n,0]-Sum[ c_{i}(Binom[i,0] ))N^{0}+(Binom[n,1]-Sum[ c_{i}(Binom[i,1]))N^{1}+ ... +(Binom[n,n]-Sum[ c_{i}(Binom[i,i-1]))N^{i-1}= 0

Again, the coefficients of each power of N must equate to zero separately, and then one
obtains the following (n+1) relations labeled by j=[0..n]:

n+1

Sum[Binom[i,j] * c_{i}] =Binom[n,j] for j=[0..n]

i=j+1

These relations are an already matrix-triangulized set of linear equations for the c_{i}'s.
They are easy to solve, especially if one starts with the (j=n) equation and works down to
the (j=0) equation. Again, the (j=0) equation says that the sum of the c_{i}'s
must equal 1, in agreement with the first condition. Now, let us say that one wants to sum
the first N integers to the 3^{rd} power. We will use the relations given by the
forced induction. Note that n=3 for the sum of cubes.

3+1

Sum[Binom[i,j] c_{i}] =Binom[3,j] for j=[0..3]

i=j+1

For (j=3) we get:

Binom[4,3] c_{4}=Binom[3,3]

4c_{4 }= 1

c_{4 }= 1/4

For (j=2) we get:

Binom[3,2] c_{3}+Binom[4,2] c_{4}=Binom[3,2]

3c_{3 }+ 6(1/4)= 3

c_{3 }= 1/2

For (j=1) we get:

Binom[2,1] c_{2}+Binom[3,1] c_{3}+Binom[4,1] c_{4}=Binom[3,1]

2c_{2 }+ 3(1/2) + 4(1/4)= 3

c_{2 }= 1/4

For (j=0) we get:

Binom[1,0] c_{1}+Binom[2,0] c_{2}+Binom[3,0] c_{3}+Binom[4,0] c_{4}=Binom[3,0]

c_{1}+ (1/4) + (1/2) + (1/4) = 1

c_{1 }= 0

Thus, the sum of cubed integers is:

N

Sum[ x^{3}] = N^{4}/4+ N^{3}/2+ N^{2}/4

x=1

Now, the true elegance of this formulation for the sums of powers of integers is that the matrix-triangulized linear equations can be solved totally

For (j=n) we get:

Binom[n+1,n] c_{n+1}=Binom[n,n]

[(n+1)n!] c_{n+1}/ [n!1!] = 1

c_{n+1}= 1/(n+1)

For (j=n-1) we get (using the result from above):

Binom[n,n-1] c_{n}+Binom[n+1,n-1] c_{n+1}=Binom[n,n-1]

[n(n-1)!] c_{n}/ [(n-1)!1!] + [(n+1)n(n-1)!] [1/(n+1)] / [(n-1)!2!] = [n(n-1)!] / [(n-1)!1!]

n c_{n}+ n/2 = n

c_{n}= 1/2

For (j=n-2) we get (using the results from above):

Binom[n-1,n-2] c_{n-1}+Binom[n,n-2] c_{n}+Binom[n+1,n-2] c_{n+1}=Binom[n,n-2]

[(n-1)!] c_{n-1}/ [(n-2)!1!] +[n!] c_{n }/ [(n-2)!2!] + [(n+1)!] c_{n+1}/ [(n-2)!3!] = [n!] / [(n-2)!2!]

[(n-1)(n-2)!] c_{n-1}/ [(n-2)!1!] +[n(n-1)(n-2)!] c_{n }/ [(n-2)!2!] + [(n+1)n(n-1)(n-2)!] c_{n+1}/ [(n-2)!3!] = [n(n-1)(n-2)!] / [(n-2)!2!]

[(n-1)] c_{n-1}/ [1!] +[n(n-1)] c_{n }/ [2!] + [(n+1)n(n-1)] c_{n+1}/ [3!] = [n(n-1)] / [2!]

[(n-1)] c_{n-1}/ [1] +[n(n-1)] [1/2]_{ }/ [2] + [(n+1)n(n-1)] / [(n+1)][6] = [n(n-1)] / [2]

[(n-1)] c_{n-1}/ [1] +[n(n-1)] / [4] + [(n+1)n(n-1)] / [(n+1)][6] = [n(n-1)] / [2]

c_{n-1}/ [1] +[n] / [4] + [(n+1)n] / [(n+1)][6] = [n] / [2]

c_{n-1}+[n/4] + [(n+1)n] / [6(n+1)] = [n/2]

c_{n-1}+[n/4] + [n/6] = [n/2]

c_{n-1}= n/12

and so forth. The following are the generalized coefficients c_{i}, found by
solving the matrix-triangulized linear equations from above, starting with the (j=n)
equation and working down towards the (j=0) equation:

c_{n+1}= 1/(n+1)

c_{n}= 1/2

c_{n-1}= n/12

c_{n-2}= 0

c_{n-3}= -n(n-1)(n-2)/720

c_{n-4}= 0

c_{n-5}= n(n-1)(n-2)(n-3)(n-4)/30240

c_{n-6}= 0

c_{n-7}= -n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)/1209600

c_{n-8}= 0

c_{n-9}= n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)(n-7)(n-8)/47900160

c_{n-10}= 0

c_{n-11}= -n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)(n-7)(n-8)(n-9)(n-10)/13076743680000

c_{n-12}= 0

etc.

Thus, one finds that the general formula for sums of powers of integers is:

N

Sum[ x^{n}] = (1/(n+1)) N^{n+1}+ (1/2) N^{n}+ (n/12) N^{n-1}+ (0) N^{n-2}+ (-n(n-1)(n-2)/720) N^{n-3}+ (0) N^{n-4}+...+ (.?.) N^{1}

x=1

where the final term in a given series is the first power of N term (.?.) N^{1}.

Thus, there are (n+1) terms in a given series, although some of the coefficients may be
zero (about half of them in fact).

So what would be the sum of integers to the 4^{th} power? In that case, n=4. There
will be (4+1=5) coefficients.

cThus, the sum of 4_{4+1}= c_{5}= 1/(4+1) = 1/5

c_{4}= c_{4}= 1/2

c_{4-1}= c_{3}= 4/12 = 1/3

c_{4-2}= c_{2}= 0

c_{4-3}= c_{1}= -4(4-1)(4-2)/720 = (-4)(3)(2)/720 = -24/720 = -1/30

N

Sum[ x^{4}] = N^{5}/5+N^{4}/2+N^{3}/3-N/30

x=1

Looking at patterns in the previous formulas gives the following relations (no proof given, but it seems to work):

c _{j+1}[n] = c_{1}[n-j] *Binom[n,j] / (j+1) for j=[0..n]

Combining this relation with the last term coefficients, {c_{1}[n]}, gives another
way to build the formulas:

cSo what would be the sum of integers to the 5_{1}[n=0] = 1/(0+1) = 1

c_{1}[n=1] = 1/2

c_{1}[n=2] = 2/12 = 1/6

c_{1}[n=3] = 0

c_{1}[n=4] = -4(4-1)(4-2)/720 = (-4)(3)(2)/720 = -1/30

c_{1}[n=5] = 0

c_{1}[n=6] = 6(6-1)(6-2)(6-3)(6-4)/30240 = (6)(5)(4)(3)(2)/30240 = 1/42

c_{1}[n=7] = 0

c_{1}[n=8] = -8(8-1)(8-2)(8-3)(8-4)(8-5)(8-6)/1209600 = (-8)(7)(6)(5)(4)(3)(2)/1209600 = -1/30

c_{1}[n=9] = 0

etc., but here are a few more just for fun...

c_{1}[n=10] = 5/66

c_{1}[n=11] = 0

c_{1}[n=12] = -691/2730

c_{1}[n=13] = 0

etc.

Thus, the sum of 5th power integers is:c

_{j+1}[5] =...........= c_{1}[5-j] *Binom[5,j] / (j+1) for j=[0..5]

c_{5+1}[5] = c_{6}[5] = c_{1}[5-5] *Binom[5,5] / (5+1) = c_{1}[0] *Binom[5,5] / (6) = (1) * 1 / 6 = 1/6

c_{4+1}[5] = c_{5}[5] = c_{1}[5-4] *Binom[5,4] / (4+1) = c_{1}[1] *Binom[5,4] / (5) = (1/2) * 5 / 5 = 1/2

c_{3+1}[5] = c_{4}[5] = c_{1}[5-3] *Binom[5,3] / (3+1) = c_{1}[2] *Binom[5,3] / (4) = (1/6) * 10 / 4 = 5/12

c_{2+1}[5] = c_{3}[5] = c_{1}[5-2] *Binom[5,2] / (2+1) = c_{1}[3] *Binom[5,2] / (3) = (0) * 10 / 3 = 0

c_{1+1}[5] = c_{2}[5] = c_{1}[5-1] *Binom[5,1] / (1+1) = c_{1}[4] *Binom[5,1] / (2) = (-1/30) * 5 / 2 = -1/12

c_{0+1}[5] = c_{1}[5] = c_{1}[5-0] *Binom[5,0] / (0+1) = c_{1}[5] *Binom[5,0] / (1) = (0) * 1 / 1 = 0

N

Sum[ x^{5}] = N^{6}/6+N^{5}/2+5N^{4}/12-N^{2}/12

x=1

Relations based on differences between successive formulas gives

c_{1}[0]=1

n+1

c_{1}[n]=1-Sum[ c_{j}[n] ] ; c_{j}[n]=(n / j) c_{j-1}[n-1] for j=[2..n+1]

j=2

Another way to say this: To get the n^{th }sum:

Integrate the (n-1)^{th} sum formula;

Multiply all terms by n;

Add a term c_{1}[n]*N such that the sum of the c_{i}[n]'s = 1

...

Combining all these relations gives the recursion relation for the c_{1}'s:

n

c_{1}[n]=1-Sum[ c_{1}[n-j]*Binom[n,j] / (j+1) ]

j=1

Rewriting gives:

c _{1}[0] = 1n-1

c_{1}[n] = 1 -Sum[ c_{1}[k] *Binom[n+1,k] ] / (n+1)

k=0

Note: The c

The Bernoulli numbers can be generated as follows:

B= 1_{0}n-1

B= -_{n}Sum[Binom[n+1,k] *B] / (n+1)_{k}

k=0

c_{1}[n=0] =B= 1_{0}

c_{1}[n=1] = 1/2 **(B= -1/2)**_{1}

c_{1}[n=2] =B= 1/6_{2}

c_{1}[n=3] =B= 0_{3}

c_{1}[n=4] =B= -1/30_{4}

c_{1}[n=5] =B= 0_{5}

c_{1}[n=6] =B= 1/42_{6}

c_{1}[n=7] =B= 0_{7}

c_{1}[n=8] =B= -1/30_{8}

c_{1}[n=9] =B= 0_{9}

c_{1}[n=10] =B= 5/66_{10}

c_{1}[n=11] =B= 0_{11}

c_{1}[n=12] =B= -691/2730_{12}

c_{1}[n=13] =B= 0_{13}

etc.

c _{1}[0] = 1n-1

c_{1}[n] = 1 -Sum[Binom[n+1,k] * c_{1}[k] ] / (n+1)

k=0

The Sum Integer Power recursion is just 1+Bernoulli recursion

This is the reason for c_{1}[n=1]=(+1/2) and **B _{1}**=(-1/2)

N

Sum[ x^{0}] = N

x=1

N

Sum[ x^{1}] = N^{2}/2+N/2

x=1

N

Sum[ x^{2}] = N^{3}/3+N^{2}/2+N/6

x=1

N

Sum[ x^{3}] = N^{4}/4+N^{3}/2+N^{2}/4

x=1

N

Sum[ x^{4}] = N^{5}/5+N^{4}/2+N^{3}/3-N/30

x=1

N

Sum[ x^{5}] = N^{6}/6+N^{5}/2+5N^{4}/12-N^{2}/12

x=1

N

Sum[ x^{6}] = N^{7}/7+N^{6}/2+N^{5}/2-N^{3}/6+N/42

x=1

N

Sum[ x^{7}] = N^{8}/8+N^{7}/2+7N^{6}/12-7N^{4}/24+N^{2}/12

x=1

N

Sum[ x^{8}] = N^{9}/9+N^{8}/2+2N^{7}/3-7N^{5}/15+2N^{3}/9-N/30

x=1

N

Sum[ x^{9}] = N^{10}/10+N^{9}/2+3N^{8}/4-7N^{6}/10+N^{4}/2-3N^{2}/20

x=1

N

Sum[ x^{10}] = N^{11}/11+N^{10}/2+5N^{9}/6-N^{7}+N^{5}-N^{3}/2+5N/66

x=1

etc.

Assume the following solution form:

N n+1

Sum[ x^{n}] =Sum[ c_{i}N^{i}]

x=1 i=1

The (n+1) coefficient c_{i}'s for the powers of N are generated from the linear
equations:

n+1

Sum[Binom[i,j] c_{i}] =Binom[n,j] for j=[0..n]

i=j+1

Remember to start with the n^{th} equation and work down to the 0^{th}

One finds that the general formula is:

N

Sum[ x^{n}] = (1/(n+1)) N^{n+1}+ (1/2) N^{n}+ (n/12) N^{n-1}+ (0) N^{n-2}+ (-n(n-1)(n-2)/720) N^{n-3}+ (0) N^{n-4}+...+ (.?.) N^{1}

x=1

where the last term is (.?.)N. All terms after this have a coefficient of zero. The
formula for a given sum of powers will have (n+1) terms.

If one already has the c_{1} values ( i.e. the Bernoulli numbers; but remember
that c_{1}[n=1]=(+1/2), not (-1/2) ) then:

c _{j+1}[n] = c_{1}[n-j] *Binom[n,j] / (j+1) for j=[0..n]

Finally, the recursion relations for the c_{1}'s are:

c _{1}[0] = 1n-1

c_{1}[n] = 1 -Sum[Binom[n+1,k] * c_{1}[k] ] / (n+1)

k=0

I originally came upon this formulation while playing with patterns contained in Pascal's
Triangle, which of course is where all the binomial expansions used above come from, and
playing with mathematical induction. The idea of forced induction came about with a little
intuition plus lots of pattern analysis. Physicists are always looking for the patterns in
nature, including in the realm of mathematics. Note that I am of the opinion that
mathematics itself is NOT a free creation of the human mind. It is a subset of
nature/universe that is discovered by a creative thinker. The particular symbology
representing the mathematics, however, is a free/arbitrary creation, as any symbols could
be used by common agreement. The language used is arbitrary, and therefore is a creation.
The concepts that the language refers to are not arbitrary, and therefore are a discovery.

I was asked in Jan 2003 about the sufficiency of the assumed solution form. In other words, is

N n+1

Sum[ x^{n}] =Sum[ c_{i}N^{i}]

x=1 i=1

always a sufficient assumption for any power of n (integer n>=0). I will show that it
is.

Assume a more general solution form, an indefinitely-infinite polynomial on the RHS
ranging from i=[0..a],

where a>>(n+1) is a suitably huge number, like infinity.

N a>>(n+1)

Sum[ x^{n}] =Sum[ c_{i}N^{i}]

x=1 i=0

During the forced/generative induction step, we get equations that look like:

[c_{0} N^{0}+ c_{1} N^{1}+c_{2} N^{2}+...+
c_{(n+1)} N^{(n+1)}+...+c_{a} N^{a} ] + (N+1)^{n}
= [c_{0} (N+1)^{0}+c_{1} (N+1)^{1}+c_{2} (N+1)^{2}+...+
c_{(n+1)} (N+1)^{(n+1)}+...+c_{a} (N+1)^{a} ]

Like before, start at the maximum value and work your way down. Since we are working with
a>>(n+1), the (N+1)^{n} term on the LHS won't
come into the equations till later (when we get down to N^{n} ). Again as before,
gather terms in powers of N, and the coefficients must be set to zero separately for the
solutions to work for any value of N. Gathering...

(N^{a} terms) gives (c_{a} N^{a} = c_{a} N^{a})
>===> No info about c_{a}

*Not a very promising start, but don't worry yet, it gets better!*

(N^{a-1} terms) gives (c_{a-1} N^{a-1} = c_{a-1} N^{a-1}
+ **Binom**[a,a-1] c_{a} N^{a-1}) >===> No info about
c_{a-1} but ( c_{a} = 0 )

(N^{a-2} terms) gives (c_{a-2} N^{a-2} = c_{a-2} N^{a-2}
+ **Binom**[a-1,a-2] c_{a-1} N^{a-2} + **Binom**[a,a-2] c_{a}
N^{a-2}) >===> No info about c_{a-2} but ( c_{a-1}
= 0 )

Note that the c_{a} term can be ignored in subsequent equations since it was found
to be zero. Thus...

(N^{a-2} terms) gives (c_{a-2} N^{a-2} = c_{a-2} N^{a-2}
+ **Binom**[a-1,a-2] c_{a-1} N^{a-2}) >===> No info
about c_{a-2} but ( c_{a-1} = 0 )

Now the c_{a-1} term can be ignored in subsequent equations, and so on. Keep
going...

(N^{a-3} terms) gives (c_{a-3} N^{a-3} = c_{a-3} N^{a-3}
+ **Binom**[a-2,a-3] c_{a-2} N^{a-3}) >===> No info
about c_{a-3} but ( c_{a-2} = 0 )

(N^{a-4} terms) gives (c_{a-4} N^{a-4} = c_{a-4} N^{a-4}
+ **Binom**[a-3,a-4] c_{a-3} N^{a-4}) >===> No info
about c_{a-4} but ( c_{a-3} = 0 )

and so on... We continue like this, with each gathering of (N^{i} terms) setting a
term (c_{i+1} = 0) to zero.

Eventually, continuing down, we get to...

(N^{n+2} terms) gives (c_{n+2} N^{n+2} = c_{n+2} N^{n+2}
+ **Binom**[n+3,n+2] c_{n+3} N^{n+2}) >===> No info
about c_{n+2} but ( c_{n+3} = 0 )

(N^{n+1} terms) gives (c_{n+1} N^{n+1} = c_{n+1} N^{n+1}
+ **Binom**[n+2,n+1] c_{n+2} N^{n+1}) >===> No info
about c_{n+1} but ( c_{n+2} = 0 )

At this point, we have shown that all of the c_{i}'s from i=[(n+2)..a] have been
set to zero. Since a is arbitrary, we can assume that all higher terms up to infinity are
zero. Thus, the highest c_{i} we have to worry about is the (c_{n+1})
term, which is what we want for these sums.

We continue with the original solution form as before, finding the particular coefficients
for a given n. This is where that (N+1)^{n} term
comes in; it is the term responsible for the non-zero c_{i}'s for the [N^{0}..N^{n+1}]
powers. It generates the sums of powers of integers. Everything is normal, like the
original calculations, until the last gathering, since the (c_{0}) term won't come
in until we gather...

(N^{0} terms) gives (c_{0} N^{0} + 1 = c_{0} N^{0}
+ c_{1} N^{0} _{ }+ c_{2} N^{0} _{ }+
... + c_{n+1} N^{0} ) >===> No info about c_{0
}*Not a very promising finish, but don't worry yet, it gets better!*

Remember, this was the inductive part of the method. We still have our starting point,
which is to set N=1 and see what happens...

1^{n} = 1 = c_{0} 1^{0} + c_{1} 1^{1} + c_{2}
1^{2} + ... + c_{n+1} 1^{n+1}

1 = c_{0 }+ c_{1 }+ c_{2 }+ ... + c_{n+1}

Thus, re-gathering the final terms with this new info...

(N^{0} terms) gives ( c_{0} N^{0} + 1 = c_{0 }+ c_{1 }+
c_{2 }+ ... + c_{n+1} = 1)

(N^{0} terms) gives ( c_{0} + 1 = 1) >===> ( c_{0}
= 0 )

**Proof complete!**

N n+1

Sum[ x^{n}] =Sum[ c_{i}N^{i}]

x=1 i=1

is always a sufficient assumption for any power of n (integer n>=0), when used to solve
sums of powers of integers.

Comments/praise/adoration welcome...* email John *
;-)

Let's say that one wants the sum of odd squares. One can use the previously found formulas to generate this formula.

Start with the sum to be solved, and then manipulate to get the desired format:Sum[ (2x-1)^{2}] = 1^{2}+ 3^{2}+ 5^{2}+ 7^{2}+ 9^{2}+ 11^{2}+ ...

Sum[ (2x-1)^{2}]

[ (4x

Sum^{2}-4x+1) ]

[ 4x

Sum^{2}] -Sum[4x] +Sum[1]

4*Sum[ x^{2}] - 4*Sum[x] +Sum[1]

Now replace with the previously discovered formulas:

Note that N = # of terms to be summed in these formulas (not the final term which is 2N-1 for this example)4*(N

^{3}/3+N^{2}/2+N/6) - 4*(N^{2}/2+N/2) + N

4N^{3}/3 + 4N^{2}/2 + 4N/6 - 4N^{2}/2 - 4N/2 + N

4N^{3}/3 + 2N/3 - 2N + N

4 N^{3}/3 - N/3

(N terms)

Sum[ (2x-1)^{2}] = 4N^{3}/3 - N/3

x=1

1

1

1

1

...

2*(50)-1 = 100-1 = 99

Taking N=50 gives the sum of odd integers to 99

1

By inputting a given sum formula, one can manipulate to get the desired result.

This works for evens, odds, multiples, multiples plus a constant, etc.

============================

Another interesting manipulation is as follows:

Sum[ x^{1}] = N^{2}/2+N/2

Sum[ x ] = (N^{2}+N)/2

2*Sum[ x ] = N^{2}+ N

2*Sum[ x ] = N^{2}+Sum[ x^{0}]

2*Sum[ x ] = N^{2}+Sum[ 1 ]

2*Sum[ x ] -Sum[ 1 ] = N^{2}

N

Sum[ 2x-1 ] = N^{2 }x=1

The sum of N odd integer terms (2x-1) gives the exact square N^{2}

1 = 1

1+3 = 4

1+3+5 = 9

1+3+5+7 = 16

1+3+5+7+9 = 25

1+3+5+7+9+11 = 36

1+3+5+7+9+11+13 = 49

1+3+5+7+9+11+13+15 = 64

1+3+5+7+9+11+13+15+17 = 81

1+3+5+7+9+11+13+15+17+19 = 100

etc.

============================

If you like that, Check this out!

You can manipulate the equations, as the example above, so that the sum will always be a
single power N^{n}.

Can you spot the pattern?

N

Sum[ 1 ] = N^{1}

x=1

N

Sum[ 2x - 1 ] = N^{2}

x=1

N

Sum[ 3x^{2}- 3x + 1 ] = N^{3}

x=1

N

Sum[ 4x^{3}- 6x^{2}+ 4x - 1 ] = N^{4}

x=1

N

Sum[ 5x^{4}- 10x^{3}+ 10x^{2}- 5x + 1 ] = N^{5}

x=1

N

Sum[ 6x^{5}- 15x^{4}+ 20x^{3}- 15x^{2}+ 6x - 1 ] = N^{6}

x=1

N

Sum[ 7x^{6}- 21x^{5}+ 35x^{4}- 35x^{3}+ 21x^{2}- 7x + 1 ] = N^{7}

x=1

or generally...because there is always a pattern ;-) ...

N

Sum[ x^{n}- (x-1)^{n}] = N^{n}(for integer n>=1)

x=1

We can again use regular Mathematical Induction to prove this relation true.

**Step 1**: Show that the first case is true. So, set N
equal to 1.

1

Sum[ x^{n}- (x-1)^{n}] = 1^{n}

x=1

1^{n}- (1-1)^{n}= 1^{n}

1^{n}- 0^{n}= 1^{n}True! for integer n>=1

**Step 2**: Show that the subsequent cases are true. So,
set N to the value N+1.

N+1

Sum[ x^{n}- (x-1)^{n}] = (N+1)^{n}

x=1

N

Sum[ x ]+( (N+1)^{n}- ((N+1)-1)^{n}) = (N+1)^{n}

x=1

N^{n}+( (N+1)^{n}- ((N+1)-1)^{n}) = (N+1)^{n}

N^{n}+( (N+1)^{n}- N^{n}) = (N+1)^{n}

(N+1)^{n}= (N+1)^{n}True! for all n, but we must use the more restrictive case from above

**Proof Complete!**

CRC Standard Mathematical Tables -- Sums of Powers of Integers

There is a technique listed in the CRC (at least in the version that I had, I don't know if it still is in the current versions) which uses a recursion formula to generate the sum formulas, based on smaller sum formulas. The Method of Forced Induction, however, does not require the "previous" formula to get the "next" formula; you can just straight away solve for whichever power you want to work with. Thus, if you want to know the sum of integers^1000, you can just plug in the number 1000. You don't have to generate the first 999 formulas to get it. Also, the format is an already matrix-triangulized set of linear equations. These are very easily and very quickly solved, especially on a computer.

Ars Conjectandi, Jakob (James) Bernoulli (1654-1705)

various works by Leonhard Euler (1707-1783)

(both of these Mathematicians did pioneer work on integer number formulas)

(* :Title: Summation of Powers of Integers based on Forced Induction Method for Mathematica *)

(* :Author: John B. Wilson *)

(* :Summary: Summation of powers of integers using results from Method of Forced Induction *)

(* :Context: DiscreteMath`SumIntegerPowers` *)

(* :Package Version: 2.0 *)

(* :Copyright:

(* :History: Initial work (paper) done in 1992, original program in 1994, original HTML in 1997 *)

(* :Keywords: Sums,Integers,Powers,Forced Induction *)

(* :Mathematica Version: 2.0 *)

(* :Limitation: Only works for non-negative integer or symbolic inputs *)

(* :Discussion: See paper by John Wilson "Method of Forced Induction used to calculate the Sums of Powers of Integers *)

(* Times are for 486-66MHz w/ 16MB RAM in seconds for the symbolic calculation (

Power | SymbolicSum | intsum1 | intsum2 | intsum3 | intsum4 |

10 | 0.28 | 0.17 | 0.17 | 0.06 | 0.05 |

20 | 1.32 | 0.44 | 0.33 | 0.22 | 0.11 |

30 | 5.43 | 0.88 | 0.55 | 0.33 | 0.22 |

40 | 17.03 | 1.59 | 0.88 | 0.60 | 0.28 |

50 | 43.28 | 2.69 | 1.31 | 0.83 | 0.33 |

60 | 130.12 | 3.96 | 1.86 | 1.15 | 0.44 |

100 | - | 13.62 | 4.89 | 3.02 | 1.54 |

150 | - | 40.32 | 11.75 | 8.24 | 3.46 |

200 | - | - | 22.36 | 15.38 | 6.48 |

250 | - | - | 31.20 | 25.32 | 10.55 |

300 | - | - | - | 38.45 | 16.26 |

350 | - | - | - | 71.40 | 22.79 |

400 | - | - | - | - | 31.52 |

450 | - | - | - | - | 42.24 |

*)

BeginPackage["DiscreteMath`SumIntegersToPower`"]

intsum1::usage =

"intsum1[n,m] gives the summation from 1 to m of integers to the nth power, using
binomial calculations based on method of Forced Induction. This method is faster than
SymbolicSum, and can be used to generate the Bernoulli numbers by examining the N^1
coefficient of the sum to the nth power to get Bernoulli[n]"

intsum2::usage =

"intsum2[n,m] gives the summation from 1 to m of integers to the nth power, using
Bernoulli number calculations based on method of Forced Induction. This method is faster
than intsum1, but requires knowing the Bernoulli numbers to begin with."

intsum3::usage =

"intsum3[n,m] gives the summation from 1 to m of integers to the nth power, using
Bernoulli number calculations based on method of Forced Induction. This method is faster
than intsum2, also requires knowing the Bernoulli numbers, but takes advantage of the fact
that half of the Bernoulli numbers are zero."

intsum4::usage =

"intsum4[n,m] gives the summation from 1 to m of integers to the nth power, using
Bernoulli number calculations based on method of Forced Induction. This method is faster
than intsum3, also requires knowing the Bernoulli numbers, takes advantage of the fact
that half of the Bernoulli numbers are zero, and the fact that there is a simple relation
between the coefficients of a given power."

Begin["`Private`"]

intsum1[n_ , m_]:=

Module[{i,j,k,result,sum,c},

Do[result=Binomial[n,j];sum=0;Do[sum=sum+c[i]*Binomial[i,j],{i,j+2,n+1,1}];c[j+1]=(result-sum)/(j+1),{j,n,0,-1}];

Sum[c[k]*m^k,{k,1,n+1}]

]

intsum2[n_ , m_]:=

Module[{i,j,k,c},

Do[c[j+1]=BernoulliB[n-j]*Product[(n-i),{i,-2,n-j-2}]/((n+2)*(n+1)*(n-j)!),{j,n,0,-1}];

c[n]:=1/2;(* Sets BernoulliB[1] to +1/2 instead of -1/2 *)

Sum[c[k]*m^k,{k,1,n+1}] (* See paper for details *)

]

intsum3[n_ , m_]:=

Module[{i,j,k,c},

Do[c[j+1]=BernoulliB[n-j]*Product[(n-i),{i,-2,n-j-2}]/((n+2)*(n+1)*(n-j)!),{j,n,0,-2}];

Do[c[j+1]=0,{j,n-1,0,-2}];

c[n]:=1/2;(* Sets BernoulliB[1] to +1/2 instead of -1/2 *)

Sum[c[k]*m^k,{k,1,n+1}] (* See paper for details *)

]

intsum4[n_ , m_]:=

Module[{i,j,k,c},

c[n+1]=1/(n+1);

Do[c[j-1]=c[j+1]*BernoulliB[n-j+2]*j*(j+1)/(BernoulliB[n-j]*(n-j+2)*(n-j+1)),{j,n,0,-2}];

Do[c[j+1]=0,{j,n-1,0,-2}];

c[n]:=1/2;(* Sets BernoulliB[1] to +1/2 instead of -1/2 *)

Sum[c[k]*m^k,{k,1,n+1}] (* See paper for details *)

]

End[]

EndPackage[]

N

Sum[ 1/(x^{2}+x) ] = N/(N+1)

x=1

N

Sum[ (2x+1)/( (x^{2}(x+1)^{2}) ) ] = N (N+2) / (N+1)^{2}

x=1

=====

N

Sum[ (x+a)^{n}-(x+a-1+d^{x1})^{n}+(a+1)^{n}*d^{x1}] = (N+a)^{n}(for all integer n, N>=1, a>=0)

x=1

=====

N

Sum[ x^{n}- (x-1+d^{x1})^{n}+d^{x1}] = N^{n}(for all integer n, N>=1)

x=1

=====

N

1+Sum[ x^{n}- (x-1)^{n}] = N^{n}(for all integer n, N>=1)

x=2

=====

This simplifies to the following cases

N

2+Sum[ -1/(x(x-1+d^{x1})) ] = N^{-1}= 1/N

x=1

N

Sum[d^{x1}] = N^{0}= 1

x=1

N

Sum[ x^{n}- (x-1)^{n}] = N^{n}(for integer n>=1)

x=1

=====

b

Sum[ c^{x}] = { (c^{b+1}- c^{a})/(c-1) for c<>1; (b+1-a) for c=1 }

x=a

=====

N

Sum[ an+b ] = (a/2)N^{2}+(a/2+b)N

n=1

============

R

Sum[Binom[n+z,z] ] =Binom[n+1+R,R] This can be proved true by induction, and can help with the following

z=0

=============

k-1

let f_{k}(N) =Prod[ N+x ]/k!

x=0

then

f_{0}(N) = 1

f_{1}(N) = N

f_{2}(N) = N(N+1)/2

f_{3}(N) = N(N+1)(N+2)/6

Why is this interesting?

Well, f_{k}(N) =Prod[x=0..k-1, N+x ]/k! = (N+k-1)!/((n-1)!k!) =Binom[ N-1+k, k]

From, the sum formula above, this sets up f_{k}(N) so that f_{k+1}(N) =Sum[z=1..N, f_{k}(z)]

In other words,

the Nth term of f_{1}(N) is the sum of the 1st N terms of f_{0}

the Nth term of f_{2}(N) is the sum of the 1st N terms of f_{1}

the Nth term of f_{3}(N) is the sum of the 1st N terms of f_{2}

Or in other words,

f_{0}(N) is the fundamental constant 1

f_{1}(N) is the integers

f_{2}(N) is the sum of integers

f_{3}(N) is the sum of the sum of integers (1st partial sum of integers)

f_{4}(N) is the sum of the sum of the sum of integers (2nd partial sum of integers)

etc.

Or in yet other words, we now have a closed form expression for the sum of sum of sum (...etc) of integers.

=====================

Examine the following:

k-1

let f_{k,1}(N) =Prod[ N+x ]/(k+0)!

x=0

where f_{1}(N) is the Nth integer to the 1st power

where f_{2}(N) is the sum of the first N integers to the 1st power

====

k-1

let f_{k,2}(N) =Prod[ N+x ]/(k+1)! * (2N+k-1)

x=0

where f_{1}(N) is the Nth integer to the 2nd power

where f_{2}(N) is the sum of the first N integers to the 2nd power

====

k-1

let f_{k,3}(N) =Prod[ N+x ]/(k+2)! * ( 6N(N+k)+(k-1)(k-2) )

x=0

where f_{1}(N) is the Nth integer to the 3rd power

where f_{2}(N) is the sum of the first N integers to the 3rd power

I claim that for each of these formulae, the sum formula above, f_{k+1}(N) =Sum[z=1..N, f_{k}(z)], is true.

So, each of these is a closed form expression for the sums of sums of sums (etc.)

The Science Realm: John's Virtual Sci-Tech UniverseJohn's Science & Math Stuff: | About John | Send email to John4-Vectors | Ambigrams | Antipodes | Covert Ops Fragments | Cyrillic Projector | Forced Induction (Sums Of Powers Of Integers) | Fractals | Frontiers | JavaScript Graphics | Kid Science | Kryptos | Photography | Prime Sieve | QM from SR | QM from SR-Simple RoadMap | Quantum Phase | Quotes | RuneQuest Cipher Challenge | Scientific Calculator | Secret Codes & Ciphers | Science+Math | Sci-Pan Pantheist Poems | Stereograms | Turkish Grammar | |

Quantum Mechanics is derivable from Special RelativitySee QM from SR-Simple RoadMap |