Deriving the Formula for the Polynomial Series
Suppose we have an arbitrary series, S_{n} = {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 k_{n}x^{n} + k_{n}_{–1}x^{n}^{–1} + k_{n}_{–2}x^{n}^{–2} + k_{n}_{–3}x^{n}^{–3} + … + k_{0}, 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:
S_{n}: | 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 S_{n}? 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 Series0 | 1 | 2 | 3 | 4 | |
0 | K_{0} | K_{1} | K_{2} | K_{3} | K_{4} |
1 | K_{0} | K_{1} + 1K_{0} | K_{2} + K_{1} | K_{3} + K_{2} | K_{4} + K_{3} |
2 | K_{0} | K_{1} + 2K_{0} | K_{2} + 2K_{1} + K_{0} | K_{3} + 2K_{2} + K_{1} | K_{4} + 2K_{3} + K_{2} |
3 | K_{0} | K_{1} + 3K_{0} | K_{2} + 3K_{1} + 3K_{0} | K_{3} + 3K_{2} + 3K_{1} + K_{0} | K_{4} + 3K_{3} + 3K_{2} + K_{1} |
4 | K_{0} | K_{1} + 4K_{0} | K_{2} + 4K_{1} + 6K_{0} | K_{3} + 4K_{2} + 6K_{1} + 4K_{0} | K_{4} + 4K_{3} + 6K_{2} + 4K_{1} + K_{0} |
5 | K_{0} | K_{1} + 5K_{0} | K_{2} + 5K_{1} + 10K_{0} | K_{3} + 5K_{2} + 10K_{1} + 10K_{0} | K_{4} + 5K_{3} + 10K_{2} + 10K_{1} + 5K_{0} |
6 | K_{0} | K_{1} + 6K_{0} | K_{2} + 6K_{1} + 15K_{0} | K_{3} + 6K_{2} + 15K_{1} + 20K_{0} | K_{4} + 6K_{3} + 15K_{2} + 20K_{1} + 15K_{0} |
7 | K_{0} | K_{1} + 7K_{0} | K_{2} + 7K_{1} + 21K_{0} | K_{3} + 7K_{2} + 21K_{1} + 35K_{0} | K_{4} + 7K_{3} + 21K_{2} + 35K_{1} + 35K_{0} |
8 | K_{0} | K_{1} + 8K_{0} | K_{2} + 8K_{1} + 28K_{0} | K_{3} + 8K_{2} + 28K_{1} + 56K_{0} | K_{4} + 8K_{3} + 28K_{2} + 56K_{1} + 70K_{0} |
9 | K_{0} | K_{1} + 9K_{0} | K_{2} + 9K_{1} + 36K_{0} | K_{3} + 9K_{2} + 36K_{1} + 84K_{0} | K_{4} + 9K_{3} + 36K_{2} + 84K_{1} + 126K_{0} |
10 | K_{0} | K_{1} + 10K_{0} | K_{2} + 10K_{1} + 45K_{0} | K_{3} + 10K_{2} + 45K_{1} + 120K_{0} | K_{4} + 10K_{3} + 45K_{2} + 120K_{1} + 210K_{0} |
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, …, K_{3} = 1, K_{2} = 2, K_{1} = 5, K_{0} = 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 (K_{n}, K_{n}_{–1}, K_{n}_{–2}, K_{n}_{–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. = K_{i} |
0 | 1^{x} |
1^{x} | 2^{x} |
1^{x} + 2^{x} | 3^{x} – 2^{x} |
1^{x} + 2^{x} + 3^{x} | 4^{x} – 2×3^{x} + 2^{x} |
1^{x} + 2^{x} + 3^{x} + 4^{x} | 5^{x} – 3×4^{x} + 3×3^{x} – 2^{x} |
1^{x} + 2^{x} + 3^{x} + 4^{x} + 5^{x} | 6^{x} – 4×5^{x} + 6×4^{x} – 4×3^{x} + 2^{x} |
1^{x} + 2^{x} + 3^{x} + 4^{x} + 5^{x} + 6^{x} | 7^{x} – 5×6^{x} + 10×5^{x} – 10×4^{x} + 5×3^{x} – 2^{x} |
1^{x} + 2^{x} + 3^{x} + 4^{x} + 5^{x} + 6^{x} + 7^{x} | 8^{x} – 6×7^{x} + 15×6^{x} – 20×5^{x} + 15×4^{x} – 6×3^{x} + 2^{x} |
1^{x} + 2^{x} + 3^{x} + 4^{x} + 5^{x} + 6^{x} + 7^{x} + 8^{x} | 9^{x} – 7×8^{x} + 21×7^{x} – 35×6^{x} + 35×5^{x} – 21×4^{x} + 7×3^{x} – 2^{x} |
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 i^{2}, 5 terms when summing i^{3}, and so on.