1. Preamble

During junior high school, I was introduced to a formula for finding the nth term of a certain sequence with a second difference that went something like:

Tn = 1/2(n)2 - 1/2(n) + 1, for a sequence 1, 2, 4, 7 ... and n >= 1.

At first, the formula seemed quite random (similar to the quadratic formula) and I could not wrap my head around it at the time.

I wondered how adding a second difference could make the trivial arithmetic formula so complex, and I was inspired by a textbook I was reading (“Concrete Mathematics” by Donald Knuth), so I tried to derive the formula myself. I also did not like to use things I did not understand, and there is no better way to understand something than to make it yourself from scratch.

I wrote this blog post to share in hopes that someone may find it useful.

2. What is a 2nd Difference?

Say there is a sequence 1, 2, 4, 7 .... You may have come across quite a few of these types of sequences on IQ tests and whatnot, and it is easy to find that the fifth term is 11 and so on.

However, it is obvious at a glance that the sequence does not follow the familiar arithmetic or geometric formulas, so we cannot yet find an arbitrary nth term of the sequence without knowing the previous terms. Finding the general formula for this will be the goal of this derivation.

The difference or ratio between every term and its subsequent term is not constant, unlike what is needed for a+(n-1)d or arn-1 to work properly. Instead, the difference (which we will now call the ‘first difference’) increases by a constant amount as the sequence goes on.

We can see this clearly if we construct a new sequence from the first differences:

T2 - T1 = 2 - 1 = 1;

T3 - T2 = 4 - 2 = 2;

T4 - T3 = 7 - 4 = 3;

…

so the sequence of first differences is:

1, 2, 3 ....

Unlike the original sequence, it is easy to see that this sequence has a constant difference of one, so the nth term can be found using the familiar formula (albeit with some notation modifications):

(d1)n = a2 + (n - 1)d2, for n >= 1,

where (d1)n is the nth first difference, a2 is the first term of the sequence of first differences (a1 would be the first term of the original sequence), and d2 is the difference for the sequence of first differences (or the second difference).

3. Derivation of the Formula

Using the approach we naturally used to find that 11 was the fifth term in the original sequence earlier, we can model the sequence as a recursive problem:

T1 = a1;

Tn = Tn-1 + (d1)n-1, for n >= 2.

Note that it is (d1)n-1 and not (d1)n because the 1st term of the first difference is

(d1)1 = T2 - T1 = 2 - 1 = 1,

so it is

(d1)n = Tn+1 - Tn

and not

(d1)n = Tn - Tn-1.

Moving on, we expand—or “unfold”—the recursive formula to try and spot some patterns we could use to find a closed-form solution:

Tn = Tn-1 + (d1)n-1

= Tn-2 + (d1)n-2 + (d1)n-1

= Tn-3 + (d1)n-3 + (d1)n-2 + (d1)n-1.

…

Although not particularly useful by itself, there is an easy to spot pattern:

Tn = Tn-k + (d1)n-k + (d1)n-(k-1) + (d1)n-(k-2) + … + (d1)n-2 + (d1)n-1, for 1 <= k < n.

Now if we unfold all the way (k = n - 1):

Tn = Tn-(n-1) + (d1)n-(n-1) + (dn-(n-2))2 + (d1)n-(n-3) + … + (d1)n-2 + (d1)n-1

= T1 + (d1)1 + (d1)2 + (d1)3 + … + (d1)n-2 + (d1)n-1

= a1 + (d1)1 + (d1)2 + (d1)3 + … + (d1)n-2 + (d1)n-1.

Substituing the formula for finding the nth term in the sequence of first differences:

Tn = a1 + (a2 + (1 - 1)d2) + (a2 + (2 - 1)d2) + (a2 + (3 - 1)d2) + … + (a2 + ((n - 1) - 1)d2)

= a1 + a2 + (1 - 1)d2 + a2 + (2 - 1)d2 + … + a2 + ((n - 2) - 1)d2 + a2 + ((n - 1) - 1)d2.

Since it goes from (d1)1 to (d1)n-1, there will be (n - 1) number of a2’s on the right-hand side of the equation:

Tn = a1 + (n - 1)a2 + (1 - 1)d2 + (2 - 1)d2 + … + ((n - 2) - 1)d2 + ((n - 1) - 1)d2.

Attempting to factorise the remaining open-form part into d2, we can start to spot a pattern:

Tn = a1 + (n - 1)a2 + ((1 - 1) + (2 - 1) + … + ((n - 2) - 1) + ((n - 1) - 1))d2.

Again, because it goes from (d1)1 to (d1)n-1, there will be (n - 1) number of (-1)’s:

Tn = a1 + (n - 1)a2 + ((1 + 2 + 3 + … + (n - 3) + (n - 2) + (n - 1)) + (n - 1)(-1))d2.

Now the pattern is easier to see. It is the sum of integers from 1 to (n - 1):

Tn = a1 + (n - 1)a2 + (Sn-1 + (n - 1)(-1))d2

= a1 + (n - 1)a2 + (Sn-1 - (n - 1))d2.

Luckily for us, the great mathematician Gauss had already found a closed-form solution for finding the sum of integers from 1 to n when he was apparently 9 years-old or something (dubious):

Tn = a1 + (n - 1)a2 + (1/2(n - 1)((n - 1) + 1) - (n - 1))d2

= a1 + (n - 1)a2 + (1/2(n - 1)(n) - (n - 1))d2

= a1 + (n - 1)a2 + 1/2(n - 2)(n - 1)d2.

The above is the closed-form solution of the general formula for finding the nth term of a sequence with a 2nd difference. We can test it against the earlier sequence that we used as an example (1, 2, 4, 7 ...):

Tn = a1 + (n - 1)a2 + 1/2(n - 2)(n - 1)d2

= 1 + (n - 1)(1) + 1/2(n - 2)(n - 1)(1), for a1 = 1, a2 = 1, d2 = 1

= 1 + (n - 1) + 1/2(n - 2)(n - 1)

= n + 1/2(n - 2)(n - 1)

= n + 1/2(n2 - 3n + 2)

= n + 1/2n2 - 3/2(n) + 1

= 1/2(n)2 - 1/2(n) + 1.

Which matches what I wrote on the preamble. You can try out a few examples to check for any counter-examples, but you will not know for certain if it will always be correct unless you prove it, which will be talked about in the next section.

4. Proof by Mathematical Induction

Continuing from the previous section: the derivation makes sense, and we can try a few examples, but how do we know for sure that there is no counter-example somewhere we did not check? We need to be mathematically rigorous to show our formula will always work.

Fortunately, there is a convenient method called “proof by induction” that fits nicely for our sequences situation. If we show that our formula is true for a base case and also that it is true for any n if it was true for (n - 1), we can confidently conclude that the formula is true for all n.

4.1 Induction Step

Let us first go back to our definitions:

T1 = a1;

Tn = Tn-1 + (d1)n-1, for n >= 2;

(d1)n = a2 + (n - 1)d2, for n >= 1.

The formula we derived and want to prove is

Tn = a1 + (n - 1)a2 + 1/2(n - 2)(n - 1)d2.

Plugging in the formula we derived, but for Tn-1:

Tn = a1 + ((n - 1) - 1)a2 + 1/2((n - 1) - 2)((n - 1) - 1)d2 + (d1)n-1

= a1 + (n - 2)a2 + 1/2(n - 3)(n - 2)d2 + (d1)n-1

= a1 + (n - 2)a2 + 1/2(n - 3)(n - 2)d2 + (a2 + ((n - 1) - 1)d2)

= a1 + (n - 2)a2 + 1/2(n - 3)(n - 2)d2 + (a2 + (n - 2)d2)

= a1 + (n - 2)a2 + a2 + 1/2(n - 3)(n - 2)d2 + (n - 2)d2

= a1 + (n - 1)a2 + 1/2(n - 3)(n - 2)d2 + (n - 2)d2

= a1 + (n - 1)a2 + (1/2(n - 3) + 1)(n - 2)d2

= a1 + (n - 1)a2 + ((n - 3)/2 + 2/2)(n - 2)d2

= a1 + (n - 1)a2 + (((n - 3) + 2)/2)(n - 2)d2

= a1 + (n - 1)a2 + (((n - 3) + 2)/2)(n - 2)d2

= a1 + (n - 1)a2 + ((n - 1)/2)(n - 2)d2

= a1 + (n - 1)a2 + 1/2(n - 1)(n - 2)d2

= a1 + (n - 1)a2 + 1/2(n - 2)(n - 1)d2

That matches our formula, and hence proves that the formula will hold true for any n if (n - 1) is true. However, we are still missing our base case (n = 1), which is covered in the next subsection.

4.2 Base Case

Plugging in the formula for T1:

T1 = a1 + (n - 1)a2 + 1/2(n - 2)(n - 1)d2

= a1 + (1 - 1)a2 + 1/2(1 - 2)(1 - 1)d2, for n = 1

= a1 + (0)a2 + 1/2(-1)(0)d2, for n = 1

= a1 + 0 + 0

= a1.

Which matches our definition, and hence proves that the formula is true for n = 1. Combining that with the earlier induction step, we get that it is also true for n = 2, n - 1 = 1. Then that also shows that the formula is true for n = 3, n - 1 = 2. This then continues on infinitely, which shows that our formula holds true for any n.

QED.

5. Conclusion

So thats the derivation and proof of the formula for finding the nth term of a sequence with a second difference. Hopefully after reading through all that, you have gained a better understanding of how sequences with 2nd differences work.