In this lesson, we will explore linear recurrence relations. A linear recurrence relation is a recurrence relation that comes in the form:

$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}$

Where c_k‘s are constant coefficients.

The Fibonacci sequence is the classic example of a linear recurrence relation as it is written mathematically like so:

$a_n = a_{n-1} + a_{n-2}$

This requires two initial values to be specified (a₀ and a₁) in order to compute the remaining values. These are known as the initial conditions or boundary conditions (the terms can be used interchangeably).

For the Fibonacci sequence, c₀ = c₁ = 1 and all other c_k terms are zero. In plain English, the Fibonacci formula is a linear recurrence relation because a_n is a linear combination of previous values.

Recurrence formulas are often used to count the number of ways to do n things. For example, how many ways are there for a person to climb a staircase of n steps if they are allowed to climb one or two steps at a time? Since recurrence relations are dependent on values that have been previously computed, it would be helpful to try to figure out how to solve the problem in reverse. Consider the ways a person can arrive at step a_n. The two ways to do this are to climb one step up from step a_n-1 which we can reach in a_n-1 different ways, or climb two steps up from step a_n-2 which we can reach in a_n-2 different ways.

Therefore this can be expressed as:

$a_n = a_{n-1} + a_{n-2}$

Yes, this is the Fibonacci sequence again!

Now we need the boundary conditions. To find the first boundary condition, we consider that there is only one way to climb one stair, therefore a₁ = 1. To find the second, we first note that any attempt to climb a negative amount of stairs is impossible, meaning there are zero ways to do this. Mathematically, this is written like so:

$a_{n}  = 0, \ if \ n < 0$

This identity is utilized to find the second boundary condition.

$a_{1} = a_{0} + a_{-1} = 1$

Therefore:

$a_{0} = 1$

This boundary condition implies the number of ways to climb a staircase of zero steps is one. Although it is counterintuitive, it is mathematically correct!