Exercise · ZW-RECURRENCE-RELATION-008 · ★★☆ Intermediate
The sequence with \(a_0=1,\ a_1=3\) and \(a_n=2a_{n-1}-a_{n-2}\) satisfies which formula?
Choose one option.
Show answer
- B. \(a_n=1+2n\)
Explanation
The terms are \(1,3,5,7,\dots\), that is \(1+2n\). \(3^n\) fails at \(a_2=9\ne5\); \(n^2+n+1\) gives 7 at \(n=2\); \(2^n+1\) gives \(a_0=2\).
Review the concept: Recurrence relation
A recurrence relation is an equation that expresses each term \(a_n\) of a sequence in terms of the previous \(k\) terms; with initial values, it determines the whole sequence.
\[a_n=f(a_{n-1},a_{n-2},\dots,a_{n-k})\]
More practice problems: recurrence relation
- ZW-RECURRENCE-RELATION-001 Let a_0=2 and a_n=3a_n-1-1 for n≥1. What is a_4?
- ZW-RECURRENCE-RELATION-002 Let a_0=a_1=1 and a_n=a_n-1+a_n-2. What is a_6?
- ZW-RECURRENCE-RELATION-003 Let a_0=1 and a_n=a_n-1+2n. What is a_5?
- ZW-RECURRENCE-RELATION-004 If a_0=3 and a_n=2a_n-1, which is a formula for a_n?
- ZW-RECURRENCE-RELATION-005 In the Tower of Hanoi, the minimum number of moves satisfies T_n=2T_n-1+1 with T_0=0. What is T_6?
- ZW-RECURRENCE-RELATION-006 How many initial values are needed to determine a sequence with a_n=a_n-1+a_n-2?
- ZW-RECURRENCE-RELATION-007 Let a_n be the number of binary strings of length n with no two consecutive zeros. It satisfies a_n…
- ZW-RECURRENCE-RELATION-009 With n lines in general position, the number of regions of the plane satisfies R_n=R_n-1+n and R_0=…