Semu Serunjogi

1, 2, 3, 4, 5…   1, 2, 4, 8, 10…   -12, 14, -18, 110, -112…     1, 4, 9, 16, 25…    e, 7, -2.5, 19…

You are likely able to continue some of the lists of numbers above, but not necessarily all of them. I can assure you that one is pretty random – can you guess which?

What they do all have in common is that they are all what are known as sequences. A sequence is simply an ordered list of numbers. And if we have a sequence, let’s say a₀, a₁, … a_n, … then a recurrence relation is a formula that allows us to calculate the n^th term of the sequence using previous terms. It could be very simple, eg. starting with a₀ = 1 and adding 1 to each term to give the next one (a_n = a_n-1 + 1  for n > 0). This gives the all-to-familiar positive whole numbers, which are in fact the very first list of numbers above.

You may have noticed in this example that to calculate a_n explicitly, we need to first calculate all of the previous terms. Each term is like a falling domino in a line of closely packed standing dominos: the previous block strikes it, causing it to fall and hit the next domino, thus continuing the process. This may sound like a strange, scary thing, but don’t worry – you’re already an expert at using recurrence relations! Indeed, recurrence relations are all around us, embedded in the way we go about everyday life.

Have you ever counted a group of anything? Of course you have. So you’ll realise that you need to know how many items you already have before counting the next item. Bang – recurrence relation. Ever counted in pairs in order to speed this process up? Now, you’re adding two to your previous total each time, rather than one. Bang – recurrence relation. Ever used tally marks? Well, you guessed it. Bang – recurrence relation (and some modular arithmetic…)!

These processes represent the one, two and five multiplication tables, respectively. In fact, each multiplication table represents a sequence which has been generated by using a recurrence relation: in the k^th multiplication table, each term is found by starting with k and adding k to the previous term to find the next.

But why start with and add k each time? We could start with one number and choose to add a different constant each time to get the next term. For example, the sequence -2, 1, 4, 7, 10 … is generated by letting the first term be -2 and adding 3 to each term to get the next one. This is an example of what is known as an arithmetic progression. All this means is that we are starting with a constant a, and adding another constant d to each term, in order to get the next term. This can be written as:

a₀ = a and a_n = a_n-1 + d  for n > 0, for some fixed numbers a and d.

Let us look at the sequence -2, 1, 4, 7, 10… in a little more detail. We know that 1 = (-2) + 3, then 4 = 1 + 3 = (-2) + 3 + 3 = (-2) + 2 * 3 and finally 7 = 4 + 3 = (-2) + 2 * 3 + 3 = (-2) + 3 * 3. If we continue in this way, hopefully you can see that the n^th term of the sequence is given by (-2) + 3n. We can now look at the general case where where we start with a and add d each time. For the nth term, if we repeatedly substitute previous terms into the formula for a_n we end up with:

a_n = a_n-1 + d = (a_n-2 + d) + d = a_n-2 + 2d = … = a₀ + n*d = a + n*d for n > 1

Clearly, if a = 0, then a_n = n*d for n > 0. This means that the sequence a₀, a₁, … a_n, … has become the d^th multiplication table.

Let us now look at a different way to generate a sequence. Let the first and second terms be 1. Add them. This gives us a third term of 2. Now, if we add the second and third terms, we get 3 as the next term. Continuing like this, adding the third and fourth terms gives us the fifth term. Hopefully you can see what we’re doing (and I urge you to try to calculate a few more terms of this sequence for yourself!). This process gives the very famous sequence known as the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55… The Fibonacci sequence can be generated by a recurrence relation that simply writes the process we have described above in words using equations:

F₀ = F₁ = 1 and F_n = F_n-1 + F_n-2   for n > 2

A large part of the appeal of the Fibonacci sequence is the simplicity of the recurrence relation – it’s very clear how each term is found, and in fact a talented child would be able to compute many terms. But, calculating the n^th Fibonacci number is surprisingly challenging. In fact, the Fibonacci sequence can be found in some very deep mathematics. This combination of familiarity and genuine substance is the perfect formula for a famous piece of mathematics, and as such the Fibonacci numbers are a staple of maths popular culture in media and architecture. They even have their own popular culture wikipedia page!

But instead of focusing on the wonders of the Fibonacci numbers, throughout this series of articles, I would rather explore my favourite, much less famous sequence… the Catalan numbers! These can be calculated using the following recurrence relation:

C₀ = 1 and C_n+1 = C₀ * C_n + C₁ * C_n-1 + … + C_n-1 * C₁ + C_n * C₀   for n > 0

Using this, we can calculate the first few terms as 1, 1, 2, 5, 14 … (try this!). The reason this is my favourite sequence is two-fold: the symmetry of the recurrence relation and the fact that it uses all previous terms. There’s just something inviting about it that makes you wonder if there is a simplification or trick that would make calculating Cn easier… However, my initial attempts to simplify the recurrence relation led nowhere. Throughout the course of this series of articles, we shall explore the Catalan numbers further and find an alternative method of calculating them. See you for part II.