Solving Recurrences

From rule to formula

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• A recurrence defines terms from earlier terms. A closed form gives them directly.
• Guess from the first few terms, then prove by induction.
• $a_n = 3a_{n-1} - 2$, $a_0 = 4$ gives $a_n = 3^{n+1} + 1$.

Steps

1. Closed forms
2. Use the formula
3. Check the guess
4. A million moves
5. Fit the closed form
6. Your own closed form