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^{n}* 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 ^{n}* 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*is also polynomial, and so on.

^{(p)}_{n}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!