Practice question · Multiple choice
A recurrence like a(n) = 3a(n−1) − 2 with a(0) = 3 defines the sequence completely, yet a closed form is usually preferred. Why bother deriving one?
Hints
- To get a(1000) from the recurrence, how many steps do you take?
- Ask which form tells you at a glance how fast the sequence grows.
Show the answer
A. Because a recurrence needs all preceding terms; a closed form does not.
Why
Both describe the same sequence; the difference is cost and visibility. A recurrence is a procedure, so a(1000) requires every preceding term. The second advantage matters more in algorithm analysis: the recurrence does not display its growth, and unfolding it makes the 3ⁿ visible, which is exactly what the Master Theorem provides without solving in full.
Practise Recurrence Relations
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.