Computing the first few terms of any recurrence relation is fairly easy to do by hand; however, finding larger terms is impractical. It would be nice if we had some mathematical function in which we simply plug in a number, and it returns the *n ^{th}* term in a sequence. Fortunately, for linear recurrence relations, such a mathematical function does exist! This is known as a

*closed-form*solution to a recurrence relation. We will explore a technique that allows us to derive such a solution for any linear recurrence relation.

As an example, we will derive the closed-form solution for the classic Fibonacci sequence.

We start with the recurrence relation, which in this case is:

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

Before we proceed, we should note that the recurrence relation for the Fibonacci sequence is known as a *homogenous* relation because there is no explicit dependence on *n*; the equation doesn’t look like this:

`$a_n = a_{n-1} + a_{n-2} + f(n)$`

For example, this recurrence relation:

`$a_n = a_{n-1} + a_{n-2} + n^3$`

Is not homogeneous because of the *n ^{3}* term.

To solve a homogeneous linear recurrence relation, we essentially guess the form of the closed-form solution and we assign proper coefficients to make our function work. Any guess of a mathematical function that satisfies the recurrence relation is acceptable; however, power functions work particularly well for this case so we start by assuming that *a _{n} = r^{n}*. We then plug it into the recurrence relation:

`$r^n = r^{n-1} + r^{n-2}$`

We perform the following algebraic manipulations:

`$r^n = \frac{r^n}{r} + \frac{r^n}{r^2}$`

`$1 = \frac{1}{r} + \frac{1}{r^2}$`

`$r^2 = r + 1$`

`$r^2 - r - 1 = 0$`

The equation above is known as the *characteristic equation* of the recurrence relation.

In this exercise, we will focus on handling roots that are real and distinct. In later exercises, we will discuss other scenarios. The roots of the characteristic equation for the Fibonacci recurrence relation (solved using the quadratic formula) are:

`$r_1 = \frac{1}{2}\left ( 1 + \sqrt{5} \right )$`

`$r_2 = \frac{1}{2}\left ( 1 - \sqrt{5} \right )$`

Since we have two choices for *r* and the Fibonacci sequence is a linear relation, the final solution for *a _{n}* is a linear combination of

*r*and

_{1}^{n}*r*like so:

_{2}^{n}`$a_n = \alpha r_{1} ^n + \beta r_{2}^n$`

We can determine the constants 𝛼 and 𝛽 by plugging in the following initial conditions into the equation above.

`$a_0 = 0, \ a_1 = 1$`

Leading to two equations which can be solved for 𝛼 and 𝛽

`$\alpha + \beta = 0$`

`$\alpha r_1 + \beta r_2 = 1$`

Solving this system of equations to determine 𝛼 and 𝛽 yields:

`$\alpha= \frac{1}{r_1 - r_2}, \ \beta = - \frac{1}{r_1 - r_2}$`

Leading to the final closed-form equation for the Fibonacci sequence:

`$a_n= \frac{r_{1}^n}{r_1 - r_2} - \frac{r_{2}^n}{r_1 - r_2}$`

`$a_n= \frac{r_{1}^n - r_{2}^n}{r_1 - r_2}$`

Remember:

`$r_1 = \frac{1}{2}\left ( 1 + \sqrt{5} \right )$`

`$r_2 = \frac{1}{2}\left ( 1 - \sqrt{5} \right )$`

### Instructions

**1.**

Given the following recurrence relation:

`$a_n = 7a_{n-1} - 10a_{n-2}$`

Derive the characteristic equation.

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

**2.**

Find the roots, `r_1`

and `r_2`

, of the characteristic equation to obtain the general solution.

**3.**

You should have an equation that looks like this:

`$a_n = \alpha r_{1}^n + \beta r_{2}^n$`

Use initial conditions: *a _{0} = 5*,

*a*, to solve for 𝛼 and 𝛽 yielding the closed-form solution.

_{1}= 16Implement the closed-form solution in the Python function `closed_form()`

. This function should only be one line that begins with `return`

!