Linear Recurrences

By Ryan Ng

A linear recurrence is a relationship between the terms of a sequence. For example, if we write an as the kth term of our sequence, then we could have:

For any linear recurrence of this form, where every single term in the equation is a term of the sequence (i.e. every term is a some an term multiplied by a constant), a_n is a geometric series. To see this, we can substitute a_n = t^n for some constant t:

Since t^n is a sequence that certainly isn’t zero, the quadratic must be zero, so we have solutions t = 2 or t = 3.

We could also have something more complicated. Something like this:

Here, we can substitute a_k = Ak^2 + Bk + C, where A, B, C are constants. You can try it out—we get the solution

But above, we also had two solutions that made this recurrence equal to zero. Since adding zero doesn’t change anything, we can add those to our solution.

Applying this to math questions

Example 1: Try to find a formula for the nth Fibonacci number, knowing that F_n = F_n-1 + F_n-2

Example 2: How many ways can you fill a 2 × n grid with 2 × 1 tiles?

This is a relatively simple but pretty cool problem that can be solved with linear recurrences.

We can start with a 2 × 2 grid. There are two ways to fill it with 2 × 1 tiles: both vertically side by side, or both horizontally on top of each other. To extend this grid to the right, we have two options. The first is to put one vertical tile, where we would have a 2 × 3 grid. The second is to add a horizontal tile. This wouldn’t be a rectangular grid, but you have only one option afterwards—to put another tile below that added horizontal tile.

We can see a pattern here: we can build a 2 × n grid on top of a 2 × n-1 grid by adding one vertical tile. We can also build a 2 × n grid on top of a 2 × n-2 grid by adding two horizontal tiles.

Note that we can’t use two vertical tiles for the 2 × n-2 grid (bottom arrangement), because that would be the same as the above case and we would be counting the combination twice.

With this, let’s define a sequence b, where b_k is the number of ways to fill a 2 × k grid with 2 × 1 tiles. Using the above rules, we see that for any k, we can see it as either adding one tile to the k - 1 case, or adding two tiles to the k - 2 case. So to get the number of combinations, we can add these two cases together. 

There is one way to add one tile to the 2 × k-1 grid and one way to add one tile to the 2 × k-2 grid. Of course, the gray parts (the tiles that existed before adding) can be freely arranged, so we can just add up b_k-1 and b_k-2 to get b_k — the number of ways to arrange the 2 × k grid. 

b_k = b_k-1 + b_k-2