Discrete Math › Section E · Sequences › Topic E.4
Exponential sequences and solving recurrences
A recurrence tells you how to step from one term to the next; solving it means finding a closed formula that jumps straight to any term. This topic sums geometric sequences and then solves the recurrences that come up most often, from Fibonacci to divide-and-conquer algorithms.
In this topic
- Why solve a recurrence?
- Summing a geometric sequence
- Worked example: a geometric sum
- Unrolling a recurrence
- The characteristic root technique
- Worked example: two distinct roots
- The Fibonacci numbers in closed form
- Worked example: a repeated root
- Recurrences with an added constant
- Divide-and-conquer recurrences
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…