We have seen that it is often easier to find recursive definitions than closed formulas. Lucky for us, there are a few techniques for converting recursive definitions to closed formulas. Doing so is called solving a recurrence relation. Recall that the recurrence relation is a recursive definition without the initial conditions. For example, the recurrence relation for the Fibonacci sequence is \(F_n = F_{n-1} + F_{n-2}\text{.}\) (This, together with the initial conditions \(F_0 = 0\) and \(F_1 = 1\) give the entire recursive definition for the sequence.)
in-context