I will only discuss linear recurrences.
A linear recurrence is a sequence defined by initial terms and a recurrence of the form where all the 's are constants. To solve a recurrence, we find a closed-form expression for that does not rely on previous terms.
For a very simple example, consider the recurrence relation We can easily see that the solution is for all natural numbers .
Geometric series (or combinations, as we will see) are usually the solutions to recurrences. Now, let us say we have a recurrence and a solution .
Plugging in, we get Since , we can divide by . Moving the terms over, we get which is a polynomial in , so the solution satisfies the recurrence only if is a root of this polynomial. This polynomial is called the characteristic polynomial of the recurrence.
Also, note that if two geometric series satisfy a recurrence, the sum of them also satisfies the recurrence. Then, we can find the following method for solving recurrences.
Find the characteristic polynomial.
Find the roots of the characteristic polynomial.
Assuming no multiple roots, the closed-form expression will look like for some constant 's.
Use the initial values to find the values of the 's.
Let us try an example:
The sequence is defined by , , and for all . Find a closed-form expression for .
The characteristic polynomial is found by letting the lowest indexed term in the recurrence be , and replacing all 's with . In this case, Factoring the characteristic polynomial, we get roots of and . Thus, the closed-form expression looks like Plugging in , Plugging in , Solving, we get and , and the closed-form expression is This can be verified by plugging it into the recurrence.
Click here for more on this topic. Thanks for reading!