Deriving the Formula for the Polynomial Series

Suppose we have an arbitrary series, Sn = {1, 3, 10, 26, 45, 91, 158, 250, …}, and we want to find the rule for the series. Given the condition that the series fits the model knxn + kn–1xn–1 + kn–2xn–2 + kn–3xn–3 + … + k0, how do we find the coefficients of the model. One way is to solve an n × n matrix to find the coefficients but that would be cumbersome for large n.

Another approach involves finding the n-level differences of the series. For the series above, the n-level differences are given below:

Sn: 1 3 10 26 55 101 168 260 …
1st level differences: 2 7 16 29 46 67 92 …
2nd level differences: 5 9 13 17 21 25 …
3rd level differences: 4 4 4 4 4 …

Notice that after the 3rd level differences are constant and the differences henceforth are 0. Therefore, the polynomial model for our series Sn is a third-degree polynomial. The first level differences is a series of a 2nd degree polynomial. The 2nd level differences is an arithmetic series. And finally, the 3rd level differences is a constant series.

Notice that each level of difference starts with a certain number. The question is: How do the initial terms of the n-level differences affect the model of Sn? In order to expose the effect of the initial terms of n-level differences, we build a general sequence which covers series of every degree.

Table 1: The General Polynomial Series
  0 1 2 3 4
0 K0 K1 K2 K3 K4
1 K0 K1 + 1K0 K2 + K1 K3 + K2 K4 + K3
2 K0 K1 + 2K0 K2 + 2K1 + K0 K3 + 2K2 + K1 K4 + 2K3 + K2
3 K0 K1 + 3K0 K2 + 3K1 + 3K0 K3 + 3K2 + 3K1 + K0 K4 + 3K3 + 3K2 + K1
4 K0 K1 + 4K0 K2 + 4K1 + 6K0 K3 + 4K2 + 6K1 + 4K0 K4 + 4K3 + 6K2 + 4K1 + K0
5 K0 K1 + 5K0 K2 + 5K1 + 10K0 K3 + 5K2 + 10K1 + 10K0 K4 + 5K3 + 10K2 + 10K1 + 5K0
6 K0 K1 + 6K0 K2 + 6K1 + 15K0 K3 + 6K2 + 15K1 + 20K0 K4 + 6K3 + 15K2 + 20K1 + 15K0
7 K0 K1 + 7K0 K2 + 7K1 + 21K0 K3 + 7K2 + 21K1 + 35K0 K4 + 7K3 + 21K2 + 35K1 + 35K0
8 K0 K1 + 8K0 K2 + 8K1 + 28K0 K3 + 8K2 + 28K1 + 56K0 K4 + 8K3 + 28K2 + 56K1 + 70K0
9 K0 K1 + 9K0 K2 + 9K1 + 36K0 K3 + 9K2 + 36K1 + 84K0 K4 + 9K3 + 36K2 + 84K1 + 126K0
10 K0 K1 + 10K0 K2 + 10K1 + 45K0 K3 + 10K2 + 45K1 + 120K0 K4 + 10K3 + 45K2 + 120K1 + 210K0

In this table, the first row numbers represent the degree of polynomial. The first column numbers represent the nth term in the series.

Only five series are shown which progress downward. The series in the n – 1 column represents the 1st level differences of the series in the nth column.

The pattern is obvious and we can derive a model for any term that is located in a specific column and row:

f(n)=K_{n}+ \frac{K_{n-1}}{1!}n+ \frac{K_{n-2}}{2!}n(n-1)+\frac{K_{n-3}}{3!}n(n-1)(n-2)+\frac{K_{n-4}}{4!}n(n-1)(n-2)(n-3)+...

The model f(n) for the polynomial series above has 2 terms if the series is arithmetic, 3 terms if the series is quadratic, 4 terms if the series is cubic, and so on.

For our series above: 1, 3, 10, 26, 55, 101, 168, 260, …, K3 = 1, K2 = 2, K1 = 5, K0 = 4. Hence, we have: f(n)= 1+\frac{2}{1!}n+\frac{5}{2!}n(n-1)+ \frac{4}{3!}n(n-1)(n-2) = 1+2n+\frac{5}{2}n(n-1)+\frac{2}{3}n(n-1)(n-2)

It is a bit of work to expand this in polymonial form; however, when simplifying we get: f(n)= 1+\frac{5}{6}n+\frac{1}{2}n^2+\frac{2}{3}n^3.

Sum of the Power Series

We can find a formula for the sum of the powers of integers, \sum_{i}^{n}i^k, using the model above. We only need to find the coefficients (Kn, Kn–1, Kn–2, Kn–3, …) and make the proper substitution. The coefficients are the initial terms of the n-level differences.

Table 2: The 1st term of nth-Level Differences for a Power Series

f(n) 1st term of nth–level diff. = Ki
0 1x
1x 2x
1x + 2x 3x – 2x
1x + 2x + 3x 4x – 2×3x + 2x
1x + 2x + 3x + 4x 5x – 3×4x + 3×3x – 2x
1x + 2x + 3x + 4x + 5x 6x – 4×5x + 6×4x – 4×3x + 2x
1x + 2x + 3x + 4x + 5x + 6x 7x – 5×6x + 10×5x – 10×4x + 5×3x – 2x
1x + 2x + 3x + 4x + 5x + 6x + 7x 8x – 6×7x + 15×6x – 20×5x + 15×4x – 6×3x + 2x
1x + 2x + 3x + 4x + 5x + 6x + 7x + 8x 9x – 7×8x + 21×7x – 35×6x + 35×5x – 21×4x + 7×3x – 2x

Amazingly, the Pascal’s triangle appears in the 1st-level differences. The x is kept general so that we can find as many K’s as needed. We always start the series with n = 0, so that 0 is the first term. Substituting in the model, we have:

\sum_{i=0}^{n}i^x =1+\frac{2^x}{1!}n+\frac{3^x-2^x}{2!}n(n-1)+\frac{4^x-2\cdot 3^x+2^x}{3!}n(n-1)(n-2)+\frac{5^x-3\cdot4^x+3\cdot3^x-2^x}{4!}n(n-1)(n-2)(n-3)+...

Of course, this series is not at all simple. We have to work quite a bit to evaluate the coefficients. But, the series terminates to 3 terms when we are summing i, 4 terms when summing i2, 5 terms when summing i3, and so on.