Learn

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:

$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:

$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!