Recurrence Relations Reference

Recurrence Relations

A recurrence defines each term from earlier terms; initial values make the rule determine one specific sequence.

Solved Examples

Jump directly to a worked example by type.

Idea	Meaning	Use or Check
Recurrence relation	An equation for a term in terms of one or more earlier terms.	The starting values are part of the definition.
First-order recurrence	Uses the previous term to define the next.	Repeated substitution can reveal an explicit pattern.
Linear recurrence	Earlier terms appear only to the first power and are not multiplied together.	Constant-coefficient examples often have predictable growth.
Fibonacci sequence	Each term after the first two is the sum of the previous two.	Two initial terms are needed.

Arithmetic Recurrence

$$a_0=c,\quad a_n=a_{n-1}+d$$

Geometric Recurrence

$$a_0=c,\quad a_n=ra_{n-1}$$

Fibonacci Recurrence

$$F_0=0,\quad F_1=1,\quad F_n=F_{n-1}+F_{n-2}$$

A recurrence is recursive notation, not automatically a closed formula. Check the initial values and index convention before listing terms.

Given $a_0=4$ and $a_n=a_{n-1}+3$, find $a_5$ and an explicit formula.

Solution Steps

$$4,7,10,13,16,19$$ $$a_n=4+3n$$ $$a_5=4+3(5)=19$$

Use $F_0=0$, $F_1=1$, and $F_n=F_{n-1}+F_{n-2}$ to find $F_6$.

Solution Steps

$$F_0=0,\ F_1=1,\ F_2=1,\ F_3=2,\ F_4=3,\ F_5=5,\ F_6=8$$ $$F_6=8$$

Given $a_0=3$ and $a_n=2a_{n-1}$, find the first four terms and an explicit formula.

Solution Steps

List terms by doubling.
After $n$ steps, the initial value has been multiplied by 2 a total of $n$ times.

$$3,6,12,24,\ldots$$ $$a_n=3\cdot2^n$$