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 _{0}* and

*a*) in order to compute the remaining values. These are known as the

_{1}*initial conditions*or

*boundary conditions*(the terms can be used interchangeably).

For the Fibonacci sequence, *c _{0} = c_{1} = 1* and all other

*c*terms are zero. In plain English, the Fibonacci formula is a linear recurrence relation because

_{k}*a*is a linear combination of previous values.

_{n}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*which we can reach in

_{n-1}*a*different ways, or climb two steps up from step

_{n-1}*a*which we can reach in

_{n-2}*a*different ways.

_{n-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 *a _{1} = 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 *a _{n-1}* and on

*a*; therefore two boundary conditions are needed. Can you determine what those boundary conditions are?

_{n-2}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.