Recurrence Relations: Lesson

In the previous exercise, we learned how to obtain the closed-form solution for a recurrence relation whose characteristic equation had real and distinct roots. In this exercise, we will learn how to handle repeated roots. Consider the following characteristic equation:

```tex
\left (r-2 \right )^2\left ( r+3 \right ) = 0
```
Because the degree of this polynomial is three, we require three independent functions of the form *rn*.

Unfortunately, the root *r = 2* is repeated twice. We say this root has a *multiplicity* of two. When solving for the roots of a polynomial equation, online calculators such as [Wolfram Alpha](https://www.wolframalpha.com) will reveal the multiplicity of each root for you. You simply type in: roots: “polynomial equation goes here” and it will return the roots and their multiplicities.

For our previous equation, attempting to write a closed-form solution like this:

```tex
a_n = \alpha 2^n + \beta 2^n + \gamma (-3)^n
```
Would be invalid as the equation would reduce to only having two independent functions:

```tex
a_n =\left (\alpha + \beta \right ) 2^n + \gamma (-3)^n
```

To remedy this, we simply multiply the roots with multiplicity greater than one by increasing powers of *n*, starting with *n0 = 1*. Again, we state this without proof as the proof is complex and merits its own lesson.

For example, for the above equation we would have:

```tex
a_n = \alpha 2^n + \beta n 2^n + \gamma (-3)^n
```

As we did before, we plug in our initial conditions to find the coefficients for the closed-form solution.

The previous characteristic equation came from the following linear recurrence relation:
```tex
a_n = a_{n-1} + 8(a_{n-2}) - 12(a_{n-3})
```

If we use initial conditions of *a0 = 7*, *a1 = 10*, *a2 = 62*, we obtain the following closed-form solution:

```tex
a_n = 5(2^n) + 3n(2^n) + 2(-3)^n

```

Closed-Form Solution (Repeated Roots)

Until now, we have learned how to handle recurrence relations that are homogenous. In this exercise, we are going to take a look at recurrence relations that come in the form of:

```tex
a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k} + f(n)
```

Equations of this form are called *inhomogeneous* linear recurrence relations because of the *f(n)* term. Yes, they are still linear relations. Let’s take this equation as an example:

```tex
a_n = 3a_{n-1} + n^2
```
With initial condition:
```tex
a_0 = 1
```

Here *f(n) = n2*.

The first step in deriving a closed-form solution is to temporarily ignore the *f(n)* term, treat the relation as homogeneous, and find its solution. Using techniques from previous exercises, we obtain the following homogeneous solution:

```tex
a_{n}^{(h)} = \alpha 3^n
``` 
We use superscript *h* to denote this as the homogenous solution.

We now focus our attention on the *f(n)* term. Since *f(n)* is a polynomial of degree two, we can assume that *an* is proportional to *n2* so: 

```tex
a_n = An^2
```
However, before we proceed, we have to account for all powers of *n* less than two. Therefore our equation becomes:


```tex
a_n = An^2 + Bn + C
```
To find the coefficients *A*, *B*, and *C*, we plug in the equation for *an* into the recurrence relation. We get:

```tex
An^2 + Bn + C = 3(A(n-1)^2 + B(n-1) + C) + n^2
```
We can expand to get this:

```tex
An^2 + Bn + C = 3A(n^2 - 2n + 1) + 3B(n-1) + 3C + n^2
```

```tex
An^2 + Bn + C = 3An^2 - 6An + 3A + 3Bn - 3B + 3C + n^2
```

Grouping terms together:

```tex
An^2 + Bn + C = (3A+1)n^2 + (-6A+3B)n + (3A - 3B + 3C)
```
```tex
0 = (2A+1)n^2 + (-6A+2B)n + (3A - 3B + 2C)
```
This equation must be valid for all *n*. Since *A*, *B*, and *C* are constants, this is only possible if all terms inside the parentheses equal zero.

This yields the following three equations with three unknowns:

```tex
2A + 1 = 0
```
```tex
-6A+2B = 0
```
```tex
3A - 3B + 2C = 0
```
We can solve this system of equations to get:


```tex
A = -\frac{1}{2}
```
```tex
B = -\frac{3}{2}
```
```tex
C = -\frac{3}{2}
```
We now have what is called the *particular solution*, *an(p)*:

```tex
a_{n}^{(p)} = -\frac{1}{2} n^2 - \frac{3}{2} n - \frac{3}{2} 
```

The closed-form solution is the sum of the homogeneous solution and the particular solution:

```tex
a_n = a_{n}^{(h)} + a_{n}^{(p)}
```

```tex
a_n = \alpha 3^n - \frac{1}{2} n^2 - \frac{3}{2} n - \frac{3}{2}
```
Plugging in the initial condition (*a0 = 1*) we get:

```tex
1 = \alpha - \frac{3}{2}
```

```tex
\alpha = \frac{5}{2}
```
The final closed-form solution is:

```tex
a_n =\frac{5}{2}3^n - \frac{1}{2} n^2 - \frac{3}{2} n - \frac{3}{2}
```
This is the procedure for *f(n)* being a polynomial. If it were an exponential function or logarithmic, you start by assuming the particular solution is *an(p) = Af(n)* and continue to solve for the closed-form solution as we did before.

There exists a special case where *f(n)* is an exponential function of the form *rn* and its particular solution has a function that also exists in the homogenous solution; in this case, you would multiply by increasing powers of *n* just as you did for repeated roots to solve for the particular solution.

Solutions of Inhomogeneous Recurrence Relations

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

```tex
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:

```tex
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 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 *an*. The two ways to do this are to climb one step up from step *an-1* which we can reach in *an-1* different ways, or climb two steps up from step *an-2* which we can reach in *an-2* different ways.

Therefore this can be expressed as:

```tex
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:

```tex
a_{n} = 0, \ if \ n < 0
``` 
This identity is utilized to find the second boundary condition.

```tex
a_{1} = a_{0} + a_{-1} = 1
```
Therefore:

```tex
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!

Linear Recurrence

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 *nth* 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:

```tex
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:

```tex
a_n = a_{n-1} + a_{n-2} + f(n)
```
For example, this recurrence relation:

```tex
a_n = a_{n-1} + a_{n-2} + n^3
```
Is not homogeneous because of the *n3* 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 *an = rn*. We then plug it into the recurrence relation:

```tex
r^n = r^{n-1} + r^{n-2}
```
We perform the following algebraic manipulations:

```tex
r^n = \frac{r^n}{r} + \frac{r^n}{r^2}
``` 
```tex
1 = \frac{1}{r} + \frac{1}{r^2}
```
```tex
r^2 = r + 1
```
```tex
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:

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

```tex
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 *an* is a linear combination of *r1n* and *r2n* like so:

```tex
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.

```tex
a_0 = 0, \ a_1 = 1
``` 
Leading to two equations which can be solved for 𝛼 and 𝛽

```tex
\alpha + \beta = 0
```

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

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


```tex
\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:

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

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

Remember:

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

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

Closed-Form Solution

As you learned in your Data Structures and Algorithms course, a recursive function is a function that computes a value by making a call to itself. This implies that a recursive function uses previous values to compute new ones. To prevent an infinite loop, a recursive function terminates when a base case is reached.

The general template for a recursive function is:
* First, evaluate the base case(s) of the function. These serve as the termination point for the recursion.
* If the base cases are not reached, perform necessary operations and then call the function again.
* Return the computed value. 
 
The most common example of this is the Fibonacci sequence. It is written in Python as follows:

```py
def fib(n):
 if n < 2:
 return n
 k = fib(n - 1) + fib(n - 2)
 return k 		
# Alternatively, you can simply return fib(n - 1) + fib(n - 2) without assigning it to a variable
```

Review of Recursion

Recall, the recursive function for calculating the *nth* term of the Fibonacci sequence exhibits an algorithmic runtime complexity that is exponential; this means that as the input grows, the time to complete the function grows exponentially. Attempting to calculate the 20th Fibonacci number recursively would take an unreasonably long amount of time. In general, algorithms that exhibit such runtime complexity are best avoided if possible. The main reason for the inefficiency in the Fibonacci algorithm is the repeated computations of the same number. We can remedy this issue by saving any previously computed value in a data structure with preferably fast look-up and insertion time, thereby avoiding having to compute the same value again. The ideal data structures for this operation are an array or a hash table. This technique is called *memoization*. The general template for applying dynamic programming to optimize a recursive function is: 
1. Inspect the memo table (array or hash table) to determine if the recursive function has been called for some input *n*. If the memo table contains an entry for *n*, this means that the value for *n* has been previously computed so return that value as opposed to computing it again. If there is no entry for *n*, proceed to step two.
2. Compute the value recursively and store it in the memo table.
3. Return computed value.

The structure of the memo table needed for memoization is defined by the return type of the recursive function as well as the number and type of its input parameters. For example, the function to calculate the Fibonacci sequence accepts one number and returns one number, therefore the data structure needed to store the previously computed values should map one number to another number.

The template for an optimized recursive function in Python is:

```py
def recursive(a, b ,c, memo_table): 
 # Check memo_table first. Return value corresponding to the inputs given if it is in memo_table. If not, proceed
 # Compute value here. You will have to call “recursive(x, y, z, memo_table)” at some point
 # Store value in memo_table
 # Return computed value

memo = {} # memo_table containing previous values should be 3-dimensional because of recursive function input params
```

The most common data structure used for the `memo_table` in Python is a dictionary.

Review of Dynamic Programming

Great job! You’ve learned a lot about recurrence functions, their applications, and how to solve them. Here’s a brief summary of everything you learned.

A recurrence relation is a mathematical equation in which a number is computed by using previously computed values starting at the initial conditions.

A common application of recurrence relations is counting how many ways to do *n* things; i.e., the number of ways to climb *n* stairs.

In programming, a recurrence relation is known as a recursive function. Sometimes these functions are inefficient, so dynamic programming is used to optimize them.

Dynamic programming is a technique in which previously computed values are stored in a data structure such that if they are needed in future computations, the value can be retrieved as opposed to being computed again.

A homogeneous linear recurrence relation comes in the form:

```tex
a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}
```
By assuming *an = rn* and plugging it in, the characteristic equation of polynomial form is obtained. 

Finding the roots of this equation admits the independent functions that compose the closed-form solution.

If a root *r* exists that has a multiplicity greater than one, the corresponding function *rn* is multiplied by increasing powers of *n* to obtain the closed-form solution.

Most non-linear recurrence relations do not have a corresponding closed-form solution. 

An inhomogeneous linear recurrence relation comes in the form:

```tex
a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k} + f(n)
```

A closed-form solution to this relation is found by temporarily ignoring the *f(n)* term and solving for the resulting homogenous solution.

To resolve the *f(n)* term, we assume that *a(p)n* is an equation of the same form of *f(n)*; i.e., if *f(n)* is polynomial, *a(p)n* is also polynomial, and so on.

The solution that is obtained by assuming *a(p)n* is of the same form as *f(n)* is called the particular solution.

The final closed-form solution of an inhomogenous recurrence relation is the sum of the homogenous solution and the particular solution.

Well done!