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 a_n = rⁿ 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 rⁿ 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!