Discrete Math › Section E · Sequences › Topic E.3
Polynomial sequences
Some sequences are neither arithmetic nor geometric, yet their differences settle into a pattern after a few rounds. Those are exactly the sequences with polynomial closed formulas, and a short table of differences tells you which polynomial to look for.
Counting diagonals
A triangle has no diagonals, a square has 2, a pentagon 5, a hexagon 9, a heptagon 14 and an octagon 20. The sequence 0, 2, 5, 9, 14, 20 is not arithmetic, since the differences are 2, 3, 4, 5, 6, and it is not geometric. But those differences form an arithmetic sequence. In the topic "Arithmetic and geometric sequences" we met the triangular numbers, which behave the same way. This topic shows that whenever the differences are arithmetic with a non-zero common difference, the closed formula is a quadratic, and more generally how the number of rounds of differencing reveals the degree of a polynomial formula.
Reverse and add
Let \(T_n = 1 + 2 + \cdots + n\). Write the sum forwards and then backwards, \(T_n = n + (n - 1) + \cdots + 1\), and add the two lines column by column. Every column sums to \(n + 1\), and there are \(n\) columns, so \(2T_n = n(n + 1)\) and
This proves the triangular-number formula used in "Describing sequences and sums". The trick works for any arithmetic sequence, because pairing the first term with the last, the second with the second-last, and so on always gives equal pair sums. In general, an arithmetic sum equals the number of terms times the sum of the first and last terms, divided by 2.
Worked example: an arithmetic sum
Find \(7 + 11 + 15 + \cdots + 203\). 1. The terms are \(7 + 4k\). Solve \(7 + 4k = 203\) to get \(k = 49\), so \(k\) runs from 0 to 49: that is 50 terms, not 49. 2. Reverse and add: each pair, such as \(7 + 203\) or \(11 + 199\), sums to 210. 3. Twice the sum is \(50 \times 210 = 10500\), so the sum is 5,250. 4. Check the size: 50 terms averaging \(\frac{7 + 203}{2} = 105\) give \(50 \times 105 = 5250\). Counting the terms is where most errors happen, so do it carefully every time.
Arithmetic differences give a quadratic
Suppose a sequence starts at \(a_0 = 1\) and its differences are 3, 6, 9, 12, …, so \(a_n = a_{n-1} + 3n\). Then each term is the first term plus a partial sum of the differences:
This gives 1, 4, 10, 19, 31, matching \(1 + 3 + 6 + 9 + 12 = 31\). The pattern is general. A recurrence \(a_n = a_{n-1} + p(n)\) in which \(p\) is a polynomial of degree \(k - 1\) produces a closed formula of degree \(k\): adding up a linear sequence gives a quadratic, adding up a quadratic gives a cubic, and so on.
Difference tables
Take the differences of a sequence, then the differences of those, and keep going. If the \(k\)th differences are constant, the sequence is called \(\Delta^k\)-constant. The cubes 0, 1, 8, 27, 64, 125 have first differences 1, 7, 19, 37, 61, second differences 6, 12, 18, 24, and third differences 6, 6, 6: they are \(\Delta^3\)-constant. Arithmetic sequences are \(\Delta^1\)-constant. The powers of 2 never become constant, because the differences of 1, 2, 4, 8, 16 are 1, 2, 4, 8 again, the same sequence. Lay the rows out under each other in a table, so that each entry sits between the two numbers it came from.
The polynomial fitting theorem
The link between differences and formulas is exact. A sequence has constant \(k\)th differences (and non-constant earlier ones) precisely when its closed formula is a polynomial in \(n\) of degree \(k\). Moreover, if the leading term is \(c\,n^k\), the constant \(k\)th difference is \(k! \cdot c\). For the cubes, \(c = 1\) and the third differences are \(3! = 6\), as the table showed. So a difference table tells you two things before you solve anything: the degree of the polynomial to look for, and its leading coefficient. A sequence whose differences never settle has no polynomial formula at all.
Worked example: fitting a quadratic
Find a closed formula for 2, 5, 12, 23, 38, … starting at \(a_0\). 1. First differences: 3, 7, 11, 15. Second differences: 4, 4, 4. Constant, so \(a_n = An^2 + Bn + C\). 2. Leading coefficient: \(2! \cdot A = 4\), so \(A = 2\). 3. From \(a_0 = 2\): \(C = 2\). From \(a_1 = 5\): \(2 + B + 2 = 5\), so \(B = 1\). 4. So \(a_n = 2n^2 + n + 2\). Check terms not used: \(a_3 = 18 + 3 + 2 = 23\) and \(a_4 = 32 + 4 + 2 = 38\). Always test on terms you did not use to find the coefficients.
Worked example: the sum of the squares
Find a closed formula for \(s_n = 1^2 + 2^2 + \cdots + n^2\), with \(s_0 = 0\). 1. Terms: 0, 1, 5, 14, 30, 55. Differences 1, 4, 9, 16, 25, then 3, 5, 7, 9, then 2, 2, 2. So \(s_n\) is a cubic. 2. Leading coefficient: \(3! \cdot a = 2\), so \(a = \frac{1}{3}\). Since \(s_0 = 0\), there is no constant term: \(s_n = \frac{1}{3}n^3 + bn^2 + cn\). 3. From \(s_1 = 1\) and \(s_2 = 5\): \(b + c = \frac{2}{3}\) and \(4b + 2c = \frac{7}{3}\), giving \(b = \frac{1}{2}\) and \(c = \frac{1}{6}\). 4. Factored,
Check: \(s_3 = \frac{3 \cdot 4 \cdot 7}{6} = 14\) and \(s_{10} = 385\).
Back to the diagonals
The diagonal counts 0, 2, 5, 9, 14 for polygons with 3, 4, 5, 6, 7 sides have second differences 1, 1, 1, so the formula is a quadratic with leading coefficient \(\frac{1}{2}\). Fitting it gives \(\frac{n(n-3)}{2}\) for an \(n\)-sided polygon. A counting argument confirms it: each vertex joins to \(n - 3\) others by a diagonal (not to itself or its two neighbours), and \(n(n-3)\) counts every diagonal twice, once from each end. When a fitted formula and a direct argument agree, you can trust the formula, not just the first few terms.
Common mistakes to avoid
First, miscounting terms in an arithmetic sum: \(7, 11, \ldots, 203\) has 50 terms, not 49. Second, forgetting that the \(k\)th difference is \(k!\) times the leading coefficient, not the coefficient itself. Third, stopping the difference table too early: two equal entries are not enough evidence, so compute several. Fourth, fitting a polynomial and never testing it on unused terms. Fifth, expecting every sequence to be polynomial: 1, 3, 7, 15, 31 has differences that keep doubling, so no polynomial fits it for all \(n\).
Key takeaways
Reverse and add gives \(1 + 2 + \cdots + n = \frac{n(n+1)}{2}\), and any arithmetic sum is the number of terms times the average of the first and last. A sequence whose \(k\)th differences are constant has a degree-\(k\) polynomial closed formula, with constant difference \(k!\) times the leading coefficient. Find the remaining coefficients from the first few terms, and check on others. The sum of the first \(n\) squares is \(\frac{n(n+1)(2n+1)}{6}\).
Flashcards
Flashcard
n(n + 1)/2
Test your understanding
Question 1 of 5
What is 3 + 7 + 11 + … + 79?
Question 2 of 5
The sequence 4, 6, 12, 22, 36, 54, … has a polynomial closed formula. What is its degree?
Question 3 of 5
Which closed formula fits 1, 3, 7, 13, 21, … for every n, starting at a₀?
Question 4 of 5
The third differences of aₙ = 2n³ + n are constant. What is that constant?
Question 5 of 5
What is 1² + 2² + 3² + … + 10²?
