Conic SectionsDeriving the Formula for the Polynomial Sequence
Introduction
When trying to find a rule for polymonial sequences in an easier way, I stumbled upon an alternative formula for the sum of the powers. First, we need to learn polynomial sequences and then we will derive the formula for the sum of the powers.
A polynomial sequence is a sequence that results from evaluating a polymonial with real coefficients at integer values. Our goal here is to find the rule, or formula, that gives the nth term if we know the first few terms in the sequence.
For example, suppose we are given the sequence, Sn = {1, 3, 10, 26, 45, 91, 158, 250, …}, and we want to find the rule for the sequence. Given the condition that the sequence fits the model \(S_n = k_{i}x^n + k_{i-1}x^{n-1} + \) \( k_{i-2}x^{n-2} + k_{i-3}x^{n-3} + \) \(k_{i-4}x^{n-4} + ... + k_0\), how do we find the coefficients denoted by k’s 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 sequence. For the sequence 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 sequence Sn is a third-degree polynomial.
The nth level differences themselves are a sequence. The first level differences is a sequence of a 2nd degree polynomial. The 2nd level differences is an arithmetic sequence. And finally, the 3rd level differences is a constant sequence.
But what we are concerned with is the first terms of each level of differences. 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 sequence of every degree. But, we will be writing our sequence in a different way as shown in the table below.
Table 1: The General Polynomial sequence
| 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 numbers in the first row represent the degree of polynomial: 0, 1, 2, 3, 4, and so on. The numbers in the first column represent the nth term in the sequence.
So, we have a sequence in the Column 0, which are all K0. The rule for the sequence in Column 0 would be a polynomial of 0 degree.
The sequence in Column 1 is: K1, K1 + 1K0, K1 + 2K0, K1 + 3K0, K1 + 4K0 K1 + 5K0, ... K1 + nK0. The nth term can be represented by the expression: \(K_1 + K_{0}n\).
The first level difference for the sequence in Column 1 is the sequence in Column 0!
Similarly, the sequence in Column 2 is: K2, K2 + K1, K2 + 2K1 + K0, K2 + 3K1 + 3K0, K2 + 4K1 + 6K0, ... and so no. The nth term in this sequence is given by\(K_2 + K_{1}n + K_{0}\frac{n(n-1)}{2}\).
And the 1st level difference for sequence in Column 2 is Column 1 and the 2nd level difference is Column 0!
Hence, with our table, we can represent any polynominal sequence. And the coefficients are basically the numbers in Pascal’s triangle.
Remember we were interested in how the first terms in the nth level differences compute in our formula for the rule for the sequence. Well, Row 0 represents our first terms in the nth level differences, since the sequence progresses downward.
We have five sequences progressing downward in the 5 columns marked 0 to 4.
Because the pattern is obvious, meaning that the coefficients are Pascal’s triangle numbers, we can derive a model for any term that is located in a specific column and row:
A polymonial sequence can be represented by the following formula:
\(f(n)=K_{i}+ \frac{K_{i-1}}{1!}n+ \frac{K_{i-2}}{2!}n(n-1)+\) \(\frac{K_{i-3}}{3!}n(n-1)(n-2)+\) \(\frac{K_{i-4}}{4!}n(n-1)(n-2)(n-3)+...\)
where Ki represent the first terms of the nth level differences.
The model f(n) for the polynomial sequence above has 2 terms if the sequence is arithmetic, 3 terms if the sequence is quadratic, 4 terms if the sequence is cubic, and so on.
Our method is simple. We continue to find the differences until they become 0’s. Then we take the first terms in the differences (excluding the 0) to be the coefficients in our model above. We can illustrate with an example.
Example 1
For our sequence 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\).
Let’s check with n = 6: \(f(6)= 1+\frac{5}{6}(6)+\frac{1}{2}(6^2)+\frac{2}{3}(6^3) = 1 + 5 + 18 + 144 = 168\). And the 7th term is indeed 168. Remember that \(f(0)\) is the first term.
Example 2
Let’s work backward with a given polynomial (since there’s hardly a chance we come across a sequence we need to find the formula for). Suppose our polymonial is \(f(n) = n^4 - 2n^3 + 3n^2 - 4n + 5\). The first few terms of the sequence, Sn, produced by this polynomial are:
(i) Sn = 5, 3, 9, 47, 165, 435, 953, 1839, 3237, 5315, 8265, ...
Now, let’s find the difference until they are constant.
1st: –2, 6, 38, 118, 270, 518, 886, 1398, 2078, 2950, ...
2nd: 8, 32, 80, 152, 248, 368, 512, 680, 872, ...
3rd: 24, 48, 72, 96, 120, 144, 168, 192, ...
The 3rd level is quite a surprise, revealing the even multiples of 12. We expect the 4th level differences to be constant since our polynomial was 4th degree.
4th: 24, 24, 24, 24, 24, 24, 24, ...
And indeed, the 4th level differences are a constant 24. Now, the first terms of the differences are 5, –2, 8, 24, and 24. Remember to include 5 from the original series itself. So, our model for this sequence is:
(ii) \(f(n)=5 - 2n + \frac{8}{2!}n(n-1)+\) \(\frac{24}{3!}n(n-1)(n-2)+\) \(\frac{24}{4!}n(n-1)(n-2)(n-3)\)
(iii) \(f(n)=5 - 2n + 4n^2 - 4n+\) \(4n^3-12n^2+8n+\) \(n^4-6n^3+11n^2-6n\)
Equation (ii) actually does reduce to \(f(n) = n^4 - 2n^3 + 3n^2 - 4n + 5\).
Sum of the Power Series
The above discussion has been about sequences and not sums. However, we are actually dealing with sums when we compare the (n – 1)th level differences with the nth level differences, meaning that the 2nd level differences would be the sums of the 3rd level differences, since we found the 3rd level differences by substracting.
We can find a formula for the sum of the powers of integers, \(\sum_{i}^{n}i^k\), by writing our sum of the first n terms as a sequence, then finding the nth level differences. We only need to find the coefficients (Ki, Ki–1, Ki–2, Ki–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 |
| 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 |
Our sums sequence, or a series, progresses downward in the first column. The second column are the differences. The pattern becomes obvioius. Pascal’s triangle appears in the 1st-level differences as we would have expected.
We have been evaluating the first term of the sequence with n = 0 in our sequences above, but we will shift to n = 1 because our first sum will be 1. Substituting in the model, we have:
The sum of the power series is given by the formula:
(1) \(\displaystyle \sum_{i=1}^{n}i^x = 1+\frac{2^x}{1!}(n-1)+\) \(\displaystyle \frac{3^x-2^x}{2!}(n-1)(n-2)+\) \(\displaystyle \frac{4^x-2\cdot 3^x+2^x}{3!}(n-1)(n-2)(n-3)+\) \(\displaystyle \frac{5^x-3\cdot4^x+3\cdot3^x-2^x}{4!}(n-1)(n-2)(n-3)(n-4)+...\)
Of course, this formula is not simple if one tries to expand it, and we have to work quite a bit to evaluate the coefficients. But, the series does not require knowing Bernoulli numbers and there’s a pattern in the formula. Also, the series terminates to 3 terms when we are summing i, 4 terms when summing i2, 5 terms when summing i3, and so on. If the formula is left as it without expanding the terms and simplifying, we do have a good formula.
We will evaluate equation (1) now and derive the formulas for the first few powers.
The Sum of the Powers Formulas
x = 0
We will evaluate the formulas of the first few power series. When x = 0, we have the simple series of 1’s:
(i) \(\sum_{i=1}^{n}i^0 = \sum_{i=1}^{n} 1 = 1+\frac{2^0}{1!}(n-1)+\) \(\frac{3^0-2^0}{2!}(n-1)(n-2)+\) \(\frac{4^0-2\cdot 3^0+2^0}{3!}(n-1)(n-2)(n-3)+\) \(\frac{5^0-3\cdot4^0+3\cdot3^0-2^0}{4!}(n-1)(n-2)(n-3)(n-4)+... \)
(ii) \(\sum_{i=1}^{n} 1 = 1 + \frac{1}{1!}(n-1)+\) \(\frac{1-1}{2!}(n-1)(n-2)+\) \(\frac{1-2+1}{3!}(n-1)(n-2)(n-3)+\) \(\frac{1-3+3-1}{4!}(n-1)(n-2)(n-3)(n-4)+...\)
(iii) \(\sum_{i=1}^{n} 1 = 1 + n - 1\)
(1) \(\sum_{i=1}^{n} 1 = n \)
That was a bit silly. Let’s march forward for the higher powers.
x = 1
When x = 1, our formula should reduce to the triangular numbers formula:
(i) \(\sum_{i=1}^{n}i^1 = 1+\frac{2^1}{1!}(n-1)+\) \(\frac{3^1-2^1}{2!}(n-1)(n-2)+\) \(\frac{4^1-2\cdot 3^1+2^1}{3!}(n-1)(n-2)(n-3)+\) \(\frac{5^1-3\cdot4^1+3\cdot3^1-2^1}{4!}(n-1)(n-2)(n-3)(n-4)+...\)
(ii) \(\sum_{i=1}^{n}i = 1+2(n-1)+\) \(\frac{1}{2}(n-1)(n-2)+\) \(\frac{4-6+2}{3!}(n-1)(n-2)(n-3)+\) \(\frac{5-12+9-2}{4!}(n-1)(n-2)(n-3)(n-4)+...\)
(iii) \(\sum_{i=1}^{n}i = 1+2n-2+\) \(\frac{1}{2}n^2-\frac{3}{2}n+1\)
(2) \(\sum_{i=1}^{n}i = \frac{1}{2}n^2+\frac{1}{2}n = \frac{n(n+1)}{2}\)
Equation (2) is indeed the formula for the triangular numbers.
x = 2
(i) \(\sum_{i=1}^{n}i^2 = 1+\frac{2^2}{1!}(n-1)+\) \(\frac{3^2-2^2}{2!}(n-1)(n-2)+\) \(\frac{4^2-2\cdot 3^2+2^2}{3!}(n-1)(n-2)(n-3)+\) \(\frac{5^2-3\cdot4^2+3\cdot3^2-2^2}{4!}(n-1)(n-2)(n-3)(n-4)+...\)
(ii) \(\sum_{i=1}^{n}i^2 = 1+4(n-1)+\) \(\frac{5}{2}(n-1)(n-2)+\) \(\frac{1}{3}(n-1)(n-2)(n-3)+\) \(\frac{25-48+27-4}{4!}(n-1)(n-2)(n-3)(n-4)+...\)
(iii) \(\sum_{i=1}^{n}i^2 = 1 + 4n - 4 +\) \(\frac{5}{2}n^2 - \frac{15}{2}n + 5 +\) \(\frac{1}{3}(n^3-6n^2+11n-6)\)
(3) \(\sum_{i=1}^{n}i^2 = \frac{1}{3}n^3 + \frac{1}{2}n^2+\frac{1}{6}n = \) \(\frac{1}{6}n(n+1)(2n+1)\)
Shall we check with the sum of the first 10 squares?
Per WolframAlpha, \(\sum_{i=1}^{10}i^2 = 385\). Using our formula, we get \(\frac{1}{6}(10)(11)(21) = \frac{2310}{6} = 385\). Well... we knew this would work since these formulas are well-known.
As the power increases, carrying out the expansion and simplication gets more and more complex. At some point, it is better to leave the formula as is and only compute the coefficients. We will find the expanded form for a few more.
x = 3
The sum of this sequence is well known to be the squares of triangular numbers. We will add an extra term to make sure it evaluates to 0.
(i) \(\sum_{i=1}^{n}i^3 = 1 + \frac{2^3}{1!}(n-1)+\) \(\frac{3^3-2^3}{2!}(n-1)(n-2)+\) \(\frac{4^3-2\cdot 3^3+2^3}{3!}(n-1)(n-2)(n-3)+\) \(\frac{5^3-3\cdot4^3+3\cdot3^3-2^3}{4!}(n-1)(n-2)(n-3)(n-4)+ \) \(\frac{6^3-4\cdot5^3+6\cdot4^3-4\cdot3^3+2^3}{5!}(n-1)(n-2)(n-3)(n-4)(n-5)+...\)
(ii) \(\sum_{i=1}^{n}i^3 = 1 + 8(n-1)+\) \(\frac{19}{2}(n-1)(n-2)+\) \(3(n-1)(n-2)(n-3)+\) \(\frac{1}{4}(n-1)(n-2)(n-3)(n-4)+ \) \((0)(n-1)(n-2)(n-3)(n-4)(n-5)+...\)
(iii) \(\sum_{i=1}^{n}i^3 = 1 + 8n - 8 +\) \(\frac{19}{2}(n-1)(n-2)+\) \(3(n-1)(n-2)(n-3)+\) \(\frac{1}{4}(n-1)(n-2)(n-3)(n-4)\)
(4) \(\sum_{i=1}^{n}i^3 = \frac{1}{4}n^2(n+1)^2 = \left( \frac{n(n+1)}{2} \right)^2\)
x = 4
(i) \(\sum_{i=1}^{n}i^4 = 1 + \frac{2^4}{1!}(n-1)+\) \(\frac{3^4-2^4}{2!}(n-1)(n-2)+\) \(\frac{4^4-2\cdot 3^4+2^4}{3!}(n-1)(n-2)(n-3)+\) \(\frac{5^4-3\cdot4^4+3\cdot3^4-2^4}{4!}(n-1)(n-2)(n-3)(n-4)+ \) \(\frac{6^4-4\cdot5^4+6\cdot4^4-4\cdot3^4+2^4}{5!}(n-1)(n-2)(n-3)(n-4)(n-5)\)
(ii) \(\sum_{i=1}^{n}i^4 = 1 + 16(n-1)+\) \(\frac{65}{2}(n-1)(n-2)+\) \(\frac{55}{3}(n-1)(n-2)(n-3)+\) \(\frac{7}{2}(n-1)(n-2)(n-3)(n-4)+ \) \(\frac{1}{5}(n-1)(n-2)(n-3)(n-4)(n-5)\)
(5) \(\sum_{i=1}^{n}i^4 = \frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30} = \) \(\frac{1}{30}n(n+1)(2n+1)(3n^3+3n-1)\)
Let’s check the formula in (ii) for n = 7.
(iii) \(\sum_{i=1}^{7}i^4 = 1 + 16(7-1)+\) \(\frac{65}{2}(7-1)(7-2)+\) \(\frac{55}{3}(7-1)(7-2)(7-3)+\) \(\frac{7}{2}(7-1)(7-2)(7-3)(7-4)+ \) \(\frac{1}{5}(7-1)(7-2)(7-3)(7-4)(7-5)\)
(iv) \(\sum_{i=1}^{7}i^4 = 1 + (16)(6)+\) \(\frac{65}{2}(6)(5)+\) \(\frac{55}{3}(6)(5)(4)+\) \(\frac{7}{2}(6)(5)(4)(3)+ \) \(\frac{1}{5}(6)(5)(4)(3)(2)\)
(v) \(\sum_{i=1}^{7}i^4 = 1 + 96 + 975 + 2200 + 1260 + 144 = 4676\)
WolframAlpha gives the same result.
x = 5
(i) \(\sum_{i=1}^{n}i^5 = 1+\frac{2^5}{1!}(n-1)+\) \(\frac{3^5-2^5}{2!}(n-1)(n-2)+\) \(\frac{4^5-2\cdot 3^5+2^5}{3!}(n-1)(n-2)(n-3)+\) \(\frac{5^5-3\cdot4^5+3\cdot3^5-2^5}{4!}(n-1)(n-2)(n-3)(n-4)+\) \(\frac{6^5-4\cdot5^5+6\cdot4^5-4\cdot3^5+2^5}{5!}(n-1)(n-2)(n-3)(n-4)(n-5) + \) \(\frac{7^5-5\cdot6^5+10\cdot5^5-10\cdot4^5+5\cdot3^5-2^5}{6!}(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)\)
(ii) \(\sum_{i=1}^{n}i^5 = 1 + 32(n-1)+\) \(\frac{211}{2}(n-1)(n-2)+\) \(95(n-1)(n-2)(n-3)+\) \(\frac{375}{12}(n-1)(n-2)(n-3)(n-4)+\) \(4(n-1)(n-2)(n-3)(n-4)(n-5) + \) \(\frac{1}{6}(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)\)
Expanding Equation (ii) is a task of its own. Rather, we will use it as is and find the sum of the first 4 terms. Notice that when n = 4, last two terms equal 0, so not all terms come into play. Then we will sum the first 8 terms.
(iii) \(\sum_{i=1}^{4}i^5 = 1 + 32(3)+\) \(\frac{211}{2}(3)(2)+\) \(95(3)(2)(1)+\) \(\frac{375}{12}(3)(2)(1)(0)+\) \(4(3)(2)(1)(0)(-1) + \) \(\frac{1}{6}(3)(2)(1)(0)(-1)(-2)\)
(iv) \(\sum_{i=1}^{4}i^5 = 1 + 96 + 633 + 570 = 1300\)
A quick check with WolframAlpha confirms the result. Now, let’s try n = 8.
(v) \(\sum_{i=1}^{8}i^5 = 1 + 32(7)+\) \(\frac{211}{2}(7)(6)+\) \(95(7)(6)(5)+\) \(\frac{375}{12}(7)(6)(5)(4)+\) \(4(7)(6)(5)(4)(3) + \) \(\frac{1}{6}(7)(6)(5)(4)(3)(2)\)
(v) \(\sum_{i=1}^{8}i^5 = 1 + 224 + 4431 + 19950 + 26250 + 10080 + 840 = 61776\)
Again, this confirms with Wolfram Alpha. The sum gets large quickly.
Pattern of Zeroes in the Coefficients
You may have notices that the coefficients evaluate to 0 for a certain number of powers before they produce a non-zero value. Visit this page to see the pattern: Power Series Sum Formula Coefficients and a Pattern of Zeros.