Iterate a first-order recurrence

Iterating a first-order recurrence

A first-order recurrence generates a sequence by using the current term in a fixed rule. Start at V_0, then apply the rule once for each increase in the index

1. Start at the initial term Use V_0 as the starting value and treat its index as zero \(\displaystyle V_0=5\)
2. Identify the two roles In aV_n+b, a multiplies the current term and b is the fixed change added after multiplication \(\displaystyle V_{n+1}=2V_n-1\quad\Rightarrow\quad a=2,\ b=-1\)
3. Use the preceding term Each new term is calculated from the term immediately before it, not repeatedly from V_0. \(\displaystyle V_1=2(5)-1=9,\quad V_2=2(9)-1=17\)
4. Count applications from zero The index n records the number of rule applications after V_0. \(\displaystyle V_0\xrightarrow{1\text{ application}}V_1\xrightarrow{2\text{ applications}}V_2\)

Worked example

A sequence is indexed from zero. Find the term at index 3 by iterating the recurrence shown

1. \(\displaystyle V_1=2(3)+4=10\)Apply the rule once to the initial term to find V_1.
2. \(\displaystyle V_2=2(10)+4=24\)Use V_1 as the current input for the second transition
3. \(\displaystyle V_3=2(24)+4=52\)Use V_2 for the third transition, giving V_3=52.

Common mistakes

Difficulty levels

Questions about this topic

In this chapter