Vlad Bercovici

Write down a number, any number. Now multiply it by 2, add 3 and write down the result. Now take the number you just wrote, double it again, add 3 and write down the new result. Do this infinitely many times and…congratulations, you defined a sequence using recursion! All you needed was a simple rule (multiply by 2 then add 3), which is formally known as a recurrence relation. But what exactly is a recurrence relation, and how could one “solve” an equation such as x_n+1 = 2x_n + 3? How can one classify such relations, and, most importantly, how can you use them to compute, say, the 7th term of the sequence you just built?

To answer that, we first need to clarify recursion. Simply put, recursion happens when something is defined in terms of itself or something of the same type. Rather surprisingly, one can observe such a phenomenon without putting pen to paper or pressing a key. This visual recursion is known as the Droste effect, or “picture within a picture”. An image appears recursively within itself, giving the impression of an infinite loop which really only goes as far as the quality can allow.

In mathematics, the most common form of recursion is generating a sequence of numbers (such as the sequence of odd integers). This is done by applying an equation which gives a term as a function of preceding terms in the sequence. Usually it’s nice and it only depends on the previous number, for example x_n=x_n-1 + 2, but at times it can rely on even earlier terms, such as x_n = x_n-1 + x_n-2 + 17n. Much like Spongebob holding an image in the meme above, each equation represents a rule by which an entire thing can be constructed. This rule is the “recurrence relation”. 

A key observation is that, in the Droste effect example, we needed an original image on which to recurse. A mathematical sequence also requires some initial terms to get the recursive ball rolling. These terms are known as “boundary conditions”, and any respectable sequence has at least one such term (usually just one, but there may be more).

Now actually solving recurrence relations can be a dark art, but there is a subclass of these which can be solved rather quickly. That subclass is referred to as “linear” recurrence relations and contains some of the most famous recursive formulas. Any equation where a general term x_n (or sometimes x_n+1, depending on the convention) is written as a sum of preceding terms, each multiplied by constants that do not change regardless of n (those are known as “constant coefficients”), or multiplied by a function depending on n, can be put into this class. For example x_n = (-3)x_n-1 + 4n², x_n = x_n-1 – 2x_n – 3 + 5x_n – 4, or the three equations mentioned before in the article are linear. However, relations such as x_n =(x_n-1)² + (x_n-2)⁵ or x_n = x_n-1 x_n-4 + x_n-2 are not. A sequence (x_n) for which the equation is true for any n ≥ 0 is considered a “solution”. It is this type of recurrence relation that we will learn to solve today, starting from the simplest ones: linear recurrence relations of first order.

The reason they are called “first order” is that every term in the sequence, except for the first one, can be written as the same function taking only one input: the previous term. The most common cases are of the type x_n+1 = ax_n + b or x_n+1 = ax_n + bn. It should be pointed out that a cannot be zero, as otherwise you are not defining a recursion, but rather a constant or linear sequence as boring as watching Arteta’s Arsenal play. 

The method we will use, which can be generalised to higher orders where more preceding terms are referenced, makes use of homogeneous recurrence relations. In layman’s terms, these are equations containing only the terms of the sequence, each multiplied by constant coefficients; the unattached constant or expression dependent on n is removed (or, better put, is zero).  One can see that, for the first order case, the homogeneous linear recurrence relation is x_n+1 = ax_n.

After finding a sequence (u_n) that “solves” this homogeneous equation, we can find a particular solution (v_n) to the initial recurrence relation by continuously “trying the next most complex thing” (constants, then 1st-degree polynomials involving n, then 2nd-degree polynomials involving n and so on), a trick which some may recognise from solving differential equations. Adding the 2 relations up and factorising properly on each side, one can obtain a general solution (x_n), such that x_n = u_n + v_n for each n ≥ 0. We then only need to plug in the “boundary conditions”; that is, replace x_n and v_n with the corresponding values to find more information about u_n. This will be enough to deduce the general term of the solution we actually need.

If this explanation sounds confusing, it will hopefully make sense in practice. As a first application, we will work on the sequence created at the start of the article. The equation mentioned there, x_n+1 = 2x_n + 3, wasn’t entirely random, since it is the exact mathematical translation of the rule we used: multiply by 2, then add 3. Firstly, we solve the corresponding homogeneous equation, which is u_n+1 = 2u_n, using the revolutionary method of… “putting it into itself”:

u_n = 2u_n-1 = 2(2u_n-2) = 2²u_n-2 = … = 2ⁿu₀

(Notice that the exponent of the constant coefficient and the index of the term always add up to n: for 2¹u_n-1 we get 1 + (n-1) = n, for 2²u_n-2 we have 2 + (n-2) = n, and so on until for 2ⁿu₀ we have n + 0 = n).

As we have no useful information available about u₀, we will note it down as an unknown constant A (it could be anything), and write the solution of the homogeneous equation as u_n=2ⁿA.

To find the particular solution (v_n), we first look through constants to see if they can provide a solution. Namely, we try v_n = C and replace the values conveniently in the original equation, finding either the value of C or a contradiction:

v_n+1 = 2v_n + 3 becomes

C = 2C + 3, or C – 2C = 3, which gives C = -3.

Hence v_n = -3 is a particular solution of the recurrence relation, and the general sequence (x_n) thus has the following formula:

x_n = u_n + v_n = 2ⁿA – 3

(Knowing that u_n+1 = 2u_n, v_n+1 = 2v_n + 3, you can check that indeed x_n+1 = 2x_n + 3. You can also check that the first few “general” terms, namely A – 3, 2A – 3, 4A – 3 and so on, obey the rule).

As a “boundary condition”, we can use the first number you wrote down, namely the initial term x₀. We will assume that it’s 1 (it probably isn’t, I’m not a clairvoyant), and replace n with 0 and x_n with 1 to find A:

1 = 2⁰A – 3, which gives A – 3 = 1, so A = 4.

So the general term for that sequence you wrote down might have been 4*2ⁿ – 3 or, if you prefer, 2ⁿ⁺² – 3. Now instead of writing down 999 numbers to find the 1000th one, you can simply plug n = 1000 into this formula to compute it directly. Amazing!

First order linear recurrence relations have surprising applications in real world finance, as well. Suppose that your friend down the pub opens an investment account with an initial sum of £1000. They tell you their account should grow at a fixed interest rate of 1% per month, and that they add 5 pounds to it at the end of every month. By writing down the recurrence relation x_n+1 = (1 + 0.01)x_n + 5 (careful: 1% = 0.01) and using the boundary condition x₀ = 1000 and the same method as above, you too can compute how deep your buddy’s pockets will be after 36 months, or 3 years. (Spoiler alert: not that much).

We will now take a look at “second order” linear recurrence relations, named so because, as you may have guessed, the terms in the sequence are written as an equation of the 2 preceding terms. Their most common form is x_n+1 + ax_n + bx_n-1 = f(n); we will analyse the simpler cases where the right-hand side is a constant. Here both a and b must be non-zero: b since otherwise the relation is just first order, and a because otherwise the rule would be incomplete, skipping every other term and ruining the recursion.

The method applied in the first order case works just fine here, however, finding the homogeneous solution is a bit trickier. We assume that our solution is not a dull as dishwater sequence of 0’s (formally, it’s non-trivial) and just skip straight to taking u_n = Aλⁿ. We have Aλⁿ⁺¹ + aAλⁿ + bAλ^n-1 = 0. Each term has a common factor of Aλ^n-1, so we can rewrite this as Aλ^n-1(λ² + aλ + b) = 0. Now, if we divide by Aλ^n-1 (this is possible, as both A and λ are non-zero), we will finish the derivation of what is known as the “auxiliary equation”: λ² + aλ + b = 0.

If this derivation proves difficult to memorise, just remember that we can “reach” the auxiliary equation by replacing the terms of the sequence with powers of λ. The quadratic itself is important to remember, however, since in order to find the homogeneous solution we need to solve it and compare the roots, giving us 2 cases:

1. The roots λ₁ and λ₂ are different. Then the homogeneous solution is u_n = Cλ₁ⁿ + Dλ₂ⁿ
2. The roots λ₁ = λ₂ = λ are the same. By “trying the next most complex thing” (just as we did before), we get the homogeneous solution u_n = (C + nD)λⁿ.

Like Michael Schumacher at the wheel of a Ferrari, these solutions work brilliantly (but you may check if you’re a Hamilton fan). More importantly, you need to compute 2 constants to get your general term; hence you need at least 2 boundary conditions in this case (after all, 3 + 7 and 4 + 6 both give 10, but 3 + 2*7 ≠ 4 + 2*6).

We will now look at a rather artificial example, meant to show the quirks of repeated roots and of the process for finding a particular solution: x_n+1 – 2x_n + x_n-1 = 1. The auxiliary equation is pretty nice here: λ₂ – 2λ + 1 = (λ – 1)² = 0, with repeated root 1. By looking at the scheme above, our homogeneous solution is u_n = An + B. For the particular solution, we will yet again try things that are as simple as possible. Notice that taking x_n as a constant would just cancel the left-hand side out. A 1st-degree linear polynomial already solves the homogeneous equation, so we can ignore it as a component for the particular solution since it cannot contribute (remember: A and B may still be any number). We hence try a 2nd-degree polynomial which means taking v_n = C_n². Substituting in we obtain:

C(n+1)² – 2Cn² + C(n-1)² = 1, which simplifies to 2C = 1 or C = 1/2.

The general solution is hence x_n = An + B + 1/2n². Indeed, you can check the equation and verify that this is the correct solution (we won’t do the computation here, but If you know the rules of squaring and are careful enough, a lot of terms should cancel out nicely).

To finish things off in a beautiful way, we will look at the most famous recurrence relation: Fibonacci. The idea is simple: we write down 1, then 1 again, and every number after that is the sum of the 2 preceding it (1,1,2,3,5,8,13,21, and so on). While cute at the surface, this recursion hides something incredible, which can only be revealed via the methods we have learned thus far.

Firstly, from the rule we can pinpoint the recurrence relation x_n+2 = x_n+1 + x_n, or, in a more useful form, x_n+2 – x_n+1 – x_n = 0, as well as the boundary conditions x₀ = x₁ = 1. The resulting auxiliary equation, as one can hopefully see, is λ² – λ – 1 = 0. This is a particular case of the general quadratic formula aλ² + bλ + c = 0 for a = 1, b = -1, c = -1. b² – 4ac = 5 > 0, so we have 2 real roots, namely (-b + (b2-4ac)^1/2)/2a and (-b + (b2-4ac)^1/2)/2a or, in our case, (1 + 5^1/2)/2 and (1 – 5^1/2)/2. Notice that both roots are irrational, even though the quadratic has integer coefficients.

While we had more work to do to solve the quadratic, this is where the fun begins, as Anakin Skywalker once said: the relation is already homogeneous. Great, no need to do any more guess work, we can just plug the roots in:

The two initial terms now tell us that A + B = 1, A(1 + 5^1/2)/2 + B(1 – 5^1/2)/2 = 1, from where we obtain (by solving the system of equations) that:

Which gives us for any n ≥ 0:

Quite incredibly, an entire sequence of integers is generated only by irrational numbers, even if they have absolutely no overlap! This observation is at the heart of the golden spiral, a geometrical object that at every quarter turn gets wider by a factor of 1 + 5^1/2, an unfathomable number, but which can be created using squares we can actually draw.

Whether you want to calculate the student loan you will give back to Boris with interest, the exponentially increasing price tag of Kylian Mbappe, or just draw a very attractive spiral, recurrence relations may be there with you. Linear recurrence relations, in particular, can have applications of the most surprising kind, one of which is going to be explored in Part 3 of the series (coming soon), as we dive into a mathematical model of the “Gambler’s ruin”. We hope to see you there!

Article 1: Probability is everywhere. But what is it exactly?