$Project Greater Ed Logo$

Intro to Recurrence Relations

Discrete Mathematics Intro to Recurrence Relations

What is a Recurrence Relation?

Recall that one way we can describe a sequence, aside from simply listing its values in set notation, is by using a closed formula that generates each element of the sequence, based entirely on where you are in the sequence. For instance, we can define a sequence $S=\{a_n\}_{n=1}^\infty$ by letting $a_n=\frac{n}{(n+1)^2}$ for all $n\geq 1$. So, when you plug in $n=1,2,3,…$ into this rule to get the first, second, third, etc. entries of the sequence, you’ll notice that

$$S=\{a_n\}=\left\{\frac{1}{4},\frac{2}{9},\frac{3}{16},\frac{4}{25},…\right\}.$$

Another way we can define a sequence using a sort of formula is by defining a recurrence relation (defined explicitly below), which is, in a sense, a rule that generates each element of a sequence based on the values of previous elements in the sequence.

Take a look at the famous Fibonacci Sequence,

Note that the sequence starts with a pair of $1$’s, called initial conditions. From there, we generate the $3$rd element of the sequence by adding together the first two elements. We get the $4$th element by adding together the $2$nd and $3$rd elements. All subsequent elements can be computed by adding together the previous two elements.

This rule is represented by the following equations:

$$\begin{align}a_1&=1\\a_2&=1\\a_n&=a_{n-1}+a_{n-2}\end{align}$$

(Note that the terms $a_{n-1}$ and $a_{n-2}$ represent the previous element, and two elements ago, respectively. So, for instance, if $n=10$ then $a_n=a_{10}=a_{9}+a_{8}=a_{n-1}+a_{n-2}$.)

This sort of situation, where a sequence is generated by using previous terms and initial values, is common in math and in nature. We give sequences (or structures) with this sort of property a special name.

Recurrence Relation

A Recurrence Relation for a sequence $\{a_n\}_{n=1}^\infty$ is a formula for $a_n$ that is written in terms of $a_{n-1},a_{n-2},a_{n-3},…,a_{n-k}$ for some fixed $k\in \mathbb{Z}$ where $k< n$. The initial conditions of this relation are values assigned to the first $k$ terms of the sequence $a_1,a_2,a_3,…,a_k$.
When a sequence is defined by a set of initial conditions and a recurrence relation, we can say that the sequence is recursively defined.

So, in the Fibonacci Sequence example above, the recurrence relation is $a_n=a_{n-1}+a_{n-2}$. The initial conditions are $a_1=1$ and $a_2=1$. Every element of this sequence can be generated from these three equations.

Generating Sequences from Recurrence Relations

Let’s look at how the Fibonacci Sequence is generated from its initial conditions and recurrence relation rule, entry by entry. Below we write out the first 6 entries of the sequence.

$$\begin{align}a_1&=1\\a_2&=1\\a_3&=a_2+a_1=1+1=2\\a_4&=a_3+a_2=2+1=3\\a_5&=a_4+a_3=3+2=5\\a_6&=a_5+a_4=5+3=8\\\vdots&\ \ \ \ \ \ \vdots\end{align}$$

Any sequence defined by a recurrence relation can be written out using a similar approach.

The first two elements of the sequence are given to us by the initial conditions $a_1=3$ and $a_2=2$. The rest are generated by the recurrence relation $a_n=a_{n-1}+3\cdot a_{n-2}$ as follows:

$$\begin{align}a_3&=a_2+3\cdot a_1=2+3\cdot 3=11\\a_4&=a_3+3\cdot a_2=11+3\cdot 2=17\\a_5&=a_4+3\cdot a_3=17+3\cdot 11=50\\a_6&=a_5+3\cdot a_4=50+3\cdot 17=101\end{align}$$

The above recurrence relation is an example of a homogeneous recurrence relation, or a recurrence relation with constant coefficients in front of the $a_{n-1},a_{n-2}, a_{n-3},$ etc. terms.

This example is to illustrate that we can have a recurrence relation depending on only one of the sequence’s previous values. Also, notice that the sequence starts at $n=0$ with $a_0$, nothing wrong with starting at an index other than $n=1$. Generating the first five elements, we get

$$\begin{align} a_0&=1000\\a_1&=a_0\cdot (1.10)=1000\cdot (1.10)=1100\\a_2&=a_1\cdot (1.10)=1100\cdot(1.10)=1210\\a_3&=a_2\cdot (1.10)=1210\cdot (1.10)=1331\\a_4&=a_3\cdot (1.10)=1331\cdot (1.10)=1464.1\\a_5&=a_4\cdot (1.10)=1464.1\cdot (1.10)=1610.51\end{align}$$

To relate this to something of interest, if you start with $1000 and put it into an investment that increases by 10% every year, after year 1, you will have $1000\cdot(1.10)=a_1$. After year 2, building on what you made after year 1 and what you started with, you get $a_2=a_1\cdot (1.10)=1100\cdot(1.10)=1210$. So, $a_n$ corresponds precisely how much money you have after $n$ years. Thus, what we have above is a recurrence relation for compound interest.

(Somewhat Related Nerd Note: look at the digits of the numbers generated in the sequence above and compare to the rows of Pascal’s Triangle. Why does this relationship stop at $a_5$? Might be worth investigating for a small research project!)

The Importance of Initial Conditions

Let $A=\{a_n\}_{n=1}^\infty$ and $B=\{b_n\}_{n=1}^\infty$ be recursively defined as

$$A=\{a_n\}_{n=1}^\infty$$	$$B=\{b_n\}_{n=1}^\infty$$
$$\begin{align} a_1&=1\\a_2&=3\\a_n&=2\cdot a_{n-1}+a_{n-2}\end{align}$$	$$\begin{align}b_1&=2\\b_2&=4\\b_n&=2\cdot b_{n-1}+b_{n-2}\end{align}$$

Notice that both sequences $A$ and $B$ are generated by the exact same recurrence relation rule $a_n=2\cdot a_{n-1}+a_{n-2}$ (or $b_n=2\cdot b_{n-1}+b_{n-2}$ in the case of sequence $B$). Let’s see what each sequence’s elements look like, based on the above:

$a_n$	$b_n$
$$\begin{align} a_1&=1\\a_2&=3\\a_3&=2\cdot a_2+a_1=2\cdot 3+1=7\\a_4&=2\cdot a_3+a_2=2\cdot 7+3=17\\a_5&=2\cdot a_4+a_3=2\cdot 17+7=41\\a_6&=2\cdot a_5+a_4=2\cdot 41+17=99\\\vdots&=\ \ \vdots\end{align}$$	$$\begin{align} b_1&=2\\b_2&=4\\a_3&=2\cdot b_2+b_1=2\cdot 4+2=10\\b_4&=2\cdot b_3+b_2=2\cdot 10+4=24\\b_5&=2\cdot b_4+b_3=2\cdot 24+10=58\\b_6&=2\cdot b_5+b_4=2\cdot 58+24=140\\\vdots&=\ \ \vdots\end{align}$$

So we have $A=\{1,3,7,17,41,99,…\}$ and $B=\{2,4,10,24,58,140,…\}$; two very different sequences… even though the exact same rule is used to generate each element!

This is because the initial conditions for the sequences were different.

Remember that recursively defined sequences are built/generated by using the sequence’s previous entries, starting with the initial conditions, according to some rule. If we change the initial conditions but keep the rule the same, you will (likely) end up with two very different looking sequences. Its like having two runners start running due north at 8 miles per hour, but one runner starts in New York City, and the other starts in Berlin. They’re running at the same speed and in the same direction, but both will have very different journeys/views throughout their run.

In future lessons, we will show how to verify that two sequences, while apparently different, are generated by the same recurrence relation.

$$\begin{align} a_1&=1\\ a_2&=2\\a_3&=8\\a_4&=28\\a_5&=100\\a_6&=356\end{align}$$

The sequence is generated as follows, according to the rule given:

$$\begin{align}a_1&=1\\a_2&=2\\a_3&=3\cdot a_2+2\cdot a_1=3\cdot 2+2\cdot 1=8\\a_4&=3\cdot a_3+2\cdot a_2=3\cdot 8+2\cdot 2=28\\a_5&=3\cdot a_4+2\cdot a_3=3\cdot 28+2\cdot 8=100\\a_6&=3\cdot a_5+2\cdot a_2=3\cdot 100+2\cdot 28=356\end{align}$$

$$\begin{align}a_0&=4.50\\a_1&=5.40\\a_2&=6.48\\a_3&=7.776\\a_4&=9.3312\end{align}$$

The sequence is generated as follows, according to the rule given:

$$\begin{align}a_0&=4.50\\a_1&=a_0\cdot (1.20)=4.50\cdot (1.20)=5.40\\a_2&=a_1\cdot (1.20)=5.40\cdot (1.20)=6.48\\a_3&=a_2\cdot (1.20)=6.48\cdot (1.20)=7.776\\a_4&=a_3\cdot (1.20)=7.776\cdot (1.20)=9.3312\end{align}$$

Note that this problem corresponds to the situation where, in your first year of college, you buy a $4.50 latte from your favorite coffee place on a credit card with an interest rate of 20% per year (meaning your debt grows by a factor of 1.20 per year). $a_0$ corresponds to the original price of your latte. $a_i$ corresponds to the amount you owe the bank after year $i$, assuming you don’t pay back any debt prior to that point. Specifically, $a_4$ corresponds to how much you have to pay back the bank for that latte after your 4th year of college.

$$\begin{align} a_1&=1\\a_2&=1\\a_3&=1\\a_4&=3\\a_5&=5\\a_6&=9\\a_7&=17\\a_8&=31\end{align}$$

The sequence is generated as follows, according to the rule given:

$$\begin{align}a_1&=1\\a_2&=1\\a_3&=1\\a_4&=a_3+a_2+a_1=1+1+1=3\\a_5&=a_4+a_3+a_2=3+1+1=5\\a_6&=a_5+a_4+a_3=5+3+1=9\\a_7&=a_6+a_5+a_4=9+5+3=17\\a_8&=a_7+a_6+a_5=17+9+5=31\end{align}$$

$$\begin{align}a_1&=1\\a_2&=2\\a_3&=2\\a_4&=\frac{1}{2}\\a_5&=\frac{1}{8}\end{align}$$

$$\begin{align}a_1&=1\\a_2&=2\\a_3&=\frac{a_2}{(a_1)^2}=\frac{2}{1}=2\\a_4&=\frac{a_3}{(a_2)^2}=\frac{2}{4}=\frac{1}{2}\\a_5&=\frac{a_4}{(a_3)^2}=\frac{\frac{1}{2}}{2^2}=\frac{1}{8}\end{align}$$

$$\begin{align}a_1&=1\\a_2&=3\\a_3&=6\\a_4&=10\\a_5&=15\\a_6&=21\end{align}$$

Note that the sequence is generated as follows:

$$\begin{align}a_1&=1\\a_2&=a_1+2=1+2=3\\a_3&=a_2+3=3+3=6\\a_4&=a_3+4=6+4=10\\a_5&=a_4+5=10+5=15\\a_6&=a_5+6=15+6=21\end{align}$$

Note that in the recurrence relation $a_n=a_{n-1}+n$ that we used to generate the above sequence entries, to deal with the $+n$ part, we are merely replacing that $n$ with the sequence index; e.g. if we are generating the $4$th element of the sequence, for instance, we are finding $a_n=a_4$ and so we replace the $n$ in the formula with a $4$, so we get $a_n=a_{n-1}+n=a_3+4=6+4=10$.

Previous Lesson

Back to Course

Next Lesson