Generating Recursive Formulas from Non-Recursive Formulas

Introduction

Consider a sequence of numbers with a distinct pattern, such as

1, 4, 7, 10, 13, 16, 19, …

For this thought exercise, the sequence needs to be chosen with some purpose, rather than at complete random. When this is achieved, the sequence can be described by two types of formulas. For this specific example, those formulas take the following two forms:

S_n = 3n + 1

AND

S_n = S_{n-1} + 3 (with S_1 = 1)

Both formulas above help to describe the sequence we started with, but there is one significant difference between them. The first formula contains S_n but not S_{n-1}. What’s the significance of that? Well, to use the second formula, you need to know the value of the previous term in the sequence, which is what S_{n-1} represents. This may seem like a huge disadvantage, because the first formula requires no information about prior terms in the sequence. The second formula it comes with one perk to help compensate for its shortcomings though: it gives us intuition for how the terms of the sequence grow (or shrink) over time. For instance, the “+3” in the second formula indicates that each term is three more than the previous. It also says that the size of this change is the same; at every step, it is “+3”.

In general, formulas that look like the first one are called non-recursive formulas, and those that look like the second one are called recursive formulas.

Photo courtesy of TheDigitalArtist via Pixabay

While I talk about how to check if a recursive and non-recursive formula are equivalent in this article I wrote a few months ago, in this article I’m going to focus on a slightly different question: given a non-recursive formula, how can you generate a recursive formula from it? One highlight of such a question is that you can’t always uniquely find a recursive formula. Sometimes multiple recursive formulas will be satisfied by the same non-recursive formula. Nonetheless we’ll focus on systematic ways to find recursive formulas, using some friendly and familiar examples of sequences as starting points.

Example 1: Triangular Numbers

%example 1: triangular numbers

Our first example is the triangular numbers. They are defined as the following sequence of numbers:

1, 3, 6, 10, 15, 21, 28, …

At the same time, they are usually denoted as T_n; that is, T_n is the nth triangular number, so T_1 = 1, T_2 = 3, and so on. As many math textbooks and online forums would tell you, the non-recursive formula describing this sequence is

T_n = n(n+1)/2

Our task now will be to derive a recursive formula for this. The idea for constructing such a formula is that a recursive formula relates the next term in the sequence to the previous one. Thus, we want a formula that involves T_n and T_{n-1} at the same time. Remember, T_{n-1} means the “previous” term in the sequence. Let’s find a formula for the previous term, by replacing n with n-1 in the formula for the nth triangular number. In other words we want a formula for the (n-1)st triangular number:

T_{n-1} = (n-1)(n-1+1)/2 = (n-1)n/2

Now, we need to figure out what type of relationship we want to have between T_n and T_{n-1}. While there are many choices, a natural question to look at is, “what is the difference (subtraction) between T_n and T_{n-1}?” We have a formula for both of these terms, so we can subtract them and find out:

T_n-T_{n-1}=n(n+1)/2-(n-1)n/2 = (n(n+1)-(n-1)n)/2 = (n²+n-n²+n)/2 = n

In other words, the squared terms of n cancel each other out (which is great news!) and

T_n-T_{n-1} = n

It’s usually a good practice to write a recursive formula so that the T_n (the current term) is by itself on one side of the equation. The reason for this is that we want to use such a formula to get an expression for T_n immediately, without other “junk” thrown in. To do this we add T_{n-1} to both sides; we are treating T_n as the variable and isolating it.

T_n = T_{n-1} + n

That will be a recurrence formula for the triangular numbers.

Example 2: Perfect Cubes

For our second example we’ll use a different sequence:

1, 8, 27, 64, 125, 216, …

You probably recognized this as the sequence of [positive] perfect cubes. The notation we’ll use is

S_n = n³

where the S stands for “sequence.” We will repeat the procedure of the first example on this new sequence. That procedure begins by finding a formula for the previous term, S_{n-1}:

S_{n-1} = (n-1)³ = n³-3n²+3n-1

Now, we find a relationship between S_n and S_{n-1} by subtracting them:

S_n-S_{n-1} = n³-(n³-3n²+3n-1) = 3n²-3n+1

This is a recursive formula for the perfect cubes. For the same reasons as with the previous example, we get S_n by itself on the left-hand side of the equation by adding S_{n-1} to both sides:

S_n = S_{n-1}+3n²-3n+1

And that’s all there is to it. For this example, at least. We’ll add some extra complications in the next example.

\What About Deeper Recurrences?

For the last example, we try to push our idea a little bit further and consider a deeper recurrence. That is, we’ll build a recurrence for a sequence S_n that not only includes S_{n-1}, but also S_{n-2}. There are even more possibilities for how to do this, when a non-recursive formula is a starting point. For simplicity we’ll even consider the same non-recursive formula as the previous example, the perfect cubes:

S_n = n³

As suggested by the previous examples, we want formulas for the previous terms in the sequence:

S_{n-1} = (n-1)³ = n³-3n²+3n-1

S_{n-2} = (n-2)³ = n³-6n²+12n-8

For sake of illustration we will do something slightly more sophisticated than a subtraction. We will use what’s called a linear combination of the two formulas above. By combining like terms we can calculate

4S_{n-1}-S_{n-2} = 3n³-6n²+4

We can also play around with the original non-recursive formula a little bit. Since S_n = n³, we can multiply by 3 and add -6n²+4 to see that

3S_n-6n²+4 = 3n³-6n²+4

We’ve found two expressions that equal 3n³-6n²+4, so we can set them equal to each other:

3S_n-6n²+4 = 4S_{n-1}-S_{n-2}

In practice we want to use a recurrence relation to immediately get S_n, given the two previous terms. This means we want S_n by itself on one side of the equation. Luckily it’s easy enough to solve for S_n algebraically. Add 6n²-4 to both sides of the above equation:

3S_n = 4S_{n-1}-S_{n-2}+6n²-4

Now, divide by 3:

S_n = 4/3S_{n-1}-1/3S_{n-2}+2n²-4/3

This is our final recurrence formula.

Concluding Remarks

To conclude, let’s talk briefly about how to reverse the procedure I explained in detail in this article. Given a recursive formula, there is no guarantee that there is only one non-recursive formula that satisfies it (in fact we found two recursive formulas for the perfect cubes). For instance, the Fibonacci numbers and the Lucas numbers are defined with the same recursive formula, albeit with different base cases.

There is a procedure to check if a non-recursive formula satisfies a recursive formula though: plug the non-recursive formula into the recursive formula, do some algebra, and determine if both sides of the equation are actually the same (for all values of n). In the last example, we’d plug

S_n = n³, S_{n-1} = n³-3n²+3n-1, S_{n-2} = n³-6n²+12n-8

into our final recurrence formula, and check that the equality is in fact still true. I’ll leave those details to you.

Math PhD Student University of Tennessee | Academic Sales Engineer | Writer, Educator, Researcher

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store