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:
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:
For example, this recurrence relation:
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:
We perform the following algebraic manipulations:
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:
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:
We can determine the constants 𝛼 and 𝛽 by plugging in the following initial conditions into the equation above.
Leading to two equations which can be solved for 𝛼 and 𝛽
Solving this system of equations to determine 𝛼 and 𝛽 yields:
Leading to the final closed-form equation for the Fibonacci sequence:
Remember:
Instructions
Given the following recurrence relation:
Derive the characteristic equation.
Check the hint for the answer and hit Run when you’re ready to move on to the next checkpoint.
Find the roots, r_1
and r_2
, of the characteristic equation to obtain the general solution.
You should have an equation that looks like this:
Use initial conditions: a0 = 5, a1 = 16, to solve for 𝛼 and 𝛽 yielding the closed-form solution.
Implement the closed-form solution in the Python function closed_form()
. This function should only be one line that begins with return
!