Learn

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 ck‘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 (a0 and a1) 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, c0 = c1 = 1 and all other ck terms are zero. In plain English, the Fibonacci formula is a linear recurrence relation because an 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 dependant 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 an. The two ways to do this are to climb one step up from step an-1 or climb two steps up from step an-2

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 a1 = 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!

### Instructions

1.

There are three types of boxes. Boxes of types A and B have length one, and a box of type C has length two. How many ways are there to fill a space of length n with any combination of the three boxes?

Check the hint for the answer and press Run when you’re ready to move on to the next checkpoint.

2.

Notice the recurrence relation has a dependence on an-1 and on an-2; therefore two boundary conditions are needed. Can you determine what those boundary conditions are?

Check the hint for the answer and press Run when you’re ready to move on to the next checkpoint.

3.

Complete the Python function boxes() to recursively compute the number of ways to arrange the boxes.

4.

Optimize the previous boxes() function by using dynamic programming.