Solving Recurrence Relations

Section 4.2 Solving Recurrence Relations

Subsection Motivation, or, why do I care?

Let’s imagine that we wanted to find the 10,000th term of the sequence ${ a_n = a_{n-2} }$ with ${ a_0 =1, a_1 = 3 }\text{.}$ The sequence is very simple: ${ \{1, 3, 1, 3, 1, 3, \dots\} }\text{.}$

It turns out that the solution to this recurrence is $a_n = 2+(-1)^{n+1}\text{.}$ We can directly compute the value, and it takes Sage about 150 microseconds to give us the answer:

But if we wanted to actually have the computer find the 10,000th value via the recursive definition, Sage (computing via Python) can’t even do it:

Explicit solutions are better when we want to be able to actually determine specific values of a recurrence.

Subsection Solving recurrence relations

Example 4.2.1.

The Towers of Hanoi is a puzzle with the goal of moving all disks from one peg to another peg. The puzzle has the following rules:

Place all the disks on the first peg in order of size with the largest on bottom.
Move one disk at a time to any other peg. A move is valid only if a smaller disk is placed on top a larger one.

The Animation of the Towers of Hanoi puzzle by André Karwath. There are three pegs and in this picture four disks. The animation proceeds to show moving the top disk to the far right peg. The next disk to the middle peg, then the smallest disk to the second peg... and so on until we have moved all disks to the third peg.

Let $H_n$ denote the number of moves to solve the puzzle with $n$ disks. Our goal is to find a solution to the sequence $\{H_n\}\text{.}$

What is the recurrence relation that describes $H_n$ in terms of previous values?
Solve the recurrence relation.
The story accompanying the puzzle says that monks are currently solving the puzzle with 64 golden disks, and that the world will end when they finally solve the puzzle. Should we be concerned? Why or why not?

Video / Answer.

Example 4.2.2.

Recall that a bit string is a string containing only 0’s and 1’s. How many bit strings of length $n$ do not contain three consecutive 0’s?

Video / Answer.

In this video I miscounted the number of bitstrings of length 4. I said $a_4 = 15$ but if you actually count the number of bitstrings, there’s only $a_4 = 13\text{.}$ Oops!😅

Note that our solution to the recurrence,

\begin{equation*} a_n = a_{n-1} + a_{n-2} + a_{n-3} \end{equation*}

with $a_1 = 2, a_2 = 4,$ and $a_3 = 7$ is still correct, and matches:

\begin{equation*} a_4 = 7 + 4 +2 = 13\text{,} \end{equation*}

which is what I should have found.

Example 4.2.3.

A vending machine dispensing books of stamps accepts $1 coins, $1 bills, and 5 bills. Find a recurrence relation for the number of ways to deposit $n$ dollars in the vending machine, where the order in which the bills are deposited matters.

Video / Answer.

Subsection Solving particularly nice recurrence relations

Definition 4.2.4. Linear, Homogeneous Recurrence Relations of Degree k.

A linear homogeneous recurrence relation of degree $k$ with constant coefficients is a recurrence relation of the form

\begin{equation*} a_n = c_1 a_{n-1} + c_2a_{n-2} + \dots + c_k a_{n-k} \end{equation*}

where $c_1, c_2, \dots , c_k$ are real numbers with $c_k \not=0\text{.}$

Example 4.2.5.

The Fibonacci sequence: $F_n = F_{n-1} + F_{n-2}$ is linear, and its coefficients are 1 and 1. The degree is 2.
$D_n = 2D_{n-1} + D_{n-5}$ is linear, and it coefficients are 2, 0, 0, 0, 1. Its degree is 5.

For the purposes of this learning the concept, we will restrict ourselves to degree two recurrences. This means the characteristic equations are quadratic and can be easily solved. The same process would apply if the characteristic equation were of higher degree - it’s just that solving those equations isn’t straightforward and takes away from focusing on the new material.

Now let’s play with how we can actually solve this type of recurrence. Let’s pretend that $a_n = r^n$ is a solution to the (degree two) recurrence relation $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ for some variable $r\text{.}$

Let’s plug it in to the recurrence and simplify:

\begin{align*} \displaystyle a_n &= c_1 a_{n-1} + c_2a_{n-2} \\ \displaystyle r^n &= c_1 r^{n-1} + c_2r^{n-2} \\ \text{ Divide both sides by } r^{n-2}\\ \displaystyle r^2 &= c_1 r + c_2\\ \displaystyle r^2 - c_1 r - c_2 &= 0 \end{align*}

This equation, $r^2 - c_1 r - c_2 = 0\text{,}$ is a quadratic equation in the variable $r\text{,}$ and we’ll give it a special name.

Definition 4.2.6. Characteristic Equation.

We call the equation $\displaystyle r^2 - c_1 r - c_2= 0$ the characteristic equation of the recurrence relation. The solutions to this equation are the characteristic roots.

Theorem 4.2.7.

Let $c_1$ and $c_2$ be real numbers. Suppose that the characteristic equation

\begin{equation*} r^2 - c_1 r - c_2 = 0 \end{equation*}

has two distinct roots $r_1$ and $r_2\text{.}$ Then the sequence $\{a_n\}$ is a solution to the recurrence relation

\begin{equation*} a_n = c_1 a_{n-1} + c_2 a_{n-2} \end{equation*}

if, and only if

\begin{equation*} a_n = \alpha_1 r_1^n + \alpha_2 r_2^n \end{equation*}

for $n = 0, 1, 2, \dots$ and $\alpha_1$ and $\alpha_2$ are constants.

Example 4.2.8.

Solve $a_n = a_{n-1} + 2a_{n-2}$ where $a_0=2$ and $a_1=7\text{.}$

Video / Answer.

Solution.

After using the characteristic root method, we find the answer is $a_n = 3\cdot 2^{n} + (-1)^{n+1}\text{.}$ We can confirm our answer by comparing this explicit solution with the recursive version using Python!

Theorem 4.2.9.

Let $c_1$ and $c_2$ be real numbers. Suppose that the characteristic equation

\begin{equation*} r^2 - c_1 r - c_2 = 0 \end{equation*}

has one and only one root $r_1\text{.}$ Then the sequence $\{a_n\}$ is a solution to the recurrence relation

\begin{equation*} a_n = c_1 a_{n-1} + c_2 a_{n-2} \end{equation*}

if, and only if

\begin{equation*} a_n = \alpha_1 r_1^n + \alpha_2 n r_1^n \end{equation*}

for $n = 0, 1, 2, \dots$ and $\alpha_1$ and $\alpha_2$ are constants.

Note the small differences between these statements. It is significant with respect to how you solve the sequence.

Example 4.2.10.

Solve $a_n = 4a_{n-1} - 4a_{n-2}$ where $a_0=6$ and $a_1=8\text{.}$

Video / Answer.

Example 4.2.11.

Find an explicit formula for the Fibonacci numbers, $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0$ and $F_1 = 1\text{.}$

Video / Answer.

Example 4.2.12.

Solve $a_n = 7a_{n-1} - 12a_{n-2}$ with $a_0 = 12$ and $a_1 = 48$

Video / Answer.

Subsection Computer Corner

This computer corner isn’t about a particular connection to computer science but rather just helping explain some of the Python functions I’ve used above as we checked our answers. You can use this to check your own answers! We’ll walk through, changing one piece of code at a time as we build up our building blocks.

In Python, you define a function ⁵ by writing def functionName(x): where x is the input variable and the colon is not optional. Everything inside the function must be indented!

Here’s an example function that squares whatever is input.

The map function ⁶ takes two inputs, the first is a function and the second is a list. map applies the function to each and every input in the list. It does this lazily, though, meaning that if you just call map(square, [1,2,3,4]), you’ll be returned a promise that Python will actually do the computation in the future. Here’s what I mean:

... Python returns map object at somememoryaddress because it refers to a map that hasn’t actually been computed. If we want to actually find the value, we will explicitly ask Python to return a list of values. Wrap map into a list function call.

    print(list(map(square, [1,2,3,4])))

Next, instead of typing [1, 2, 3, 4], we can use range(1, 5) to return the same list. range(a,b) returns all integers $a \le x \lt b\text{.}$ Change the code above, replacing the typed-out list with a range:

    print(list(map(square, range(1, 5))))

There’s one more feature we need. If we want to write an arbitrary power (such as $x^2$ or even $2^x$), we use the pow function ⁷. For example, $x^2$ is pow(x,2), which $2^x$ is pow(2,x). Try rewriting our square function to use it in place of x*x.

Now we can put it all together to check our solutions to recurrence relations. For example, in example Example 4.2.12, we found the solution was $a_n = 3\cdot 4^{n+1}\text{,}$ then we can build the function a(n) that returns the right-side:

We can compare that against the recursive version of the sequence by writing the recursive function (the function calls itself):

It worked! Hooray! If you have questions about it, please don’t hesitate to ask me.

Exercises Exercises

1.

Find a recurrence relation for the number of ways to give someone $n$ dollars if you have 1 dollar coins, 2 dollar coins, 2 dollar bills, and 4 dollar bills where the order in which the coins and bills are paid matters.

Solution.

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

2.

Solve the recurrence relation $a_n = a_{n-1} + 2^n$ with $a_0 = 5\text{.}$

Solution.

$a_n = 3 + 2^{n+1}\text{.}$ We should use telescoping or iteration here. For example, telescoping gives

\begin{align*} a_1 - a_0 \amp = 2^1\\ a_2 - a_1 \amp = 2^2\\ a_3 - a_2 \amp = 2^3\\ \vdots\amp \vdots \\ a_n - a_{n-1} \amp = 2^n \end{align*}

which “telescopes” to $a_n - a_0 = 2^{n+1} - 2\text{.}$ Substituting $a_0 = 5$ and solving for $a_n$ completes the solution.

3.

Show that $4^n$ is a solution to the recurrence relation $a_n = 3a_{n-1} + 4a_{n-2}\text{.}$

Solution.

We claim $a_n = 4^n$ works. Plug it in: $4^n = 3(4^{n-1}) + 4(4^{n-2})\text{.}$ This works - just simplify the right-hand side.

4.

Find the solution to the recurrence relation $a_n = 3a_{n-1} + 4a_{n-2}$ with initial terms $a_0 = 2$ and $a_1 = 3\text{.}$

Solution.

By the Characteristic Root Technique. $a_n = 4^n + (-1)^n\text{.}$

5.

Find the solution to the recurrence relation $a_n = 3a_{n-1} + 4a_{n-2}$ with initial terms $a_0 = 5$ and $a_1 = 8$ using the characteristic root method..

Solution.

$a_n = \frac{13}{5}(4)^n + \frac{12}{5}(-1)^n$

6.

While walking up stairs you notice that you have a habit of using 3 ways of taking one step and 4 ways of taking two steps at a time. Find a recurrence relation for the number of ways to go up $n$ steps. Solve the recurrence relation given the initial conditions of $a_0 = 1$ and $a_1 = 3$ using the characteristic root method.

Solution.

The recurrence is $a_n = 3a_{n-1} + 4a_{n-2}\text{.}$ The solution with the given initial conditions is $a_n = \frac{4^{n+1}}{5} + \frac{(-1)^n}{5}$

7.

Solve the recurrence $a_n = 3a_{n-1} + 40a_{n-2}$ where $a_0 = 5$ and $a_1 = 14$ using the characteristic root method.

Solution.

$a_n = 3(8)^n + 2(-5)^n$

8.

Solve the recurrence $a_n = 4a_{n-1} + 21a_{n-2}$ where $a_0 = 18$ and $a_1 = 366$ using the characteristic root method.

Solution.

$a_n = 42 (7)^n - 24(-3)^n$ you could write $a_n = 6(7)^{n+1} + 8(-3)^{n+1}$

https://www.w3schools.com/python/python_functions.asp

https://www.w3schools.com/python/ref_func_map.asp

https://www.w3schools.com/python/ref_func_pow.asp

Discrete Math for Shockers

Search Results:

Section 4.2 Solving Recurrence Relations

Subsection Motivation, or, why do I care?

Subsection Solving recurrence relations

Example 4.2.1.

Example 4.2.2.

Example 4.2.3.

Subsection Solving particularly nice recurrence relations

Definition 4.2.4. Linear, Homogeneous Recurrence Relations of Degree k.

Example 4.2.5.

Definition 4.2.6. Characteristic Equation.

Theorem 4.2.7.

Example 4.2.8.

Theorem 4.2.9.

Example 4.2.10.

Example 4.2.11.

Example 4.2.12.

Subsection Computer Corner

Exercises Exercises

1.

2.

3.

4.

5.

6.

7.

8.