2.2: Recurrence Relations

Exercise $87$

How is the number of subsets of an n-element set related to the number of subsets of an ($n − 1$)-element set? Prove that you are correct. (Hint).

Exercise $88$

Explain why it is that the number of bijections from an $n$-element set to an $n$-element set is equal to $n$ times the number of bijections from an ($n − 1$)-element subset to an ($n − 1$)-element set. What does this have to do with Problem 27?

We can summarize these observations as follows. If $s_{n}$ stands for the number of subsets of an $n$-element set, then

$$s_{n} = 2s_{n-1} \label{2.2.1}$$

and if $b_{n}$ stands for the number of bijections from an n-element set to an $n$-element set, then

$$b_{n} = nb_{n-1} \label{2.2.2}$$

Equations $\ref{2.2.1}$ and $\ref{2.2.2}$ are examples of recurrence equations or recurrence relations. A recurrence relation or simply a recurrence is an equation that expresses the $n^{\text{th}}$ term of a sequence $a_{n}$ in terms of values of $a_{i}$ for $i < n$. Thus Equations $\ref{2.2.1}$ and $\ref{2.2.2}$ are examples of recurrences.

2.2.1: Examples of Recurrence Relations

Other examples of recurrences are

$$a_{n} = a_{n}−1 + 7, \label{2.2.3}$$

$$a_{n} = 3a_{n}−1 + 2n, \label{2.2.4}$$

$$a_{n} = a_{n}−1 + 3a_{n}−2, \text{ and} \label{2.2.5}$$

$$a_{n} = a_{1}a_{n−1} + a2a_{n−2} + \dotsi + a_{n−1}a_{1}. \label{2.2.6}$$

A solution to a recurrence relation is a sequence that satisfies the recurrence relation. Thus a solution to Recurrence $\ref{2.2.1}$ is the sequence given by $s_{n} = 2^{n}$. Note that $s_{n} = 17 \cdot 2^{n}$ and $s_{n} = −13 \cdot 2^{n}$ are also solutions to Recurrence $\ref{2.2.1}$. What this shows is that a recurrence can have infinitely many solutions. In a given problem, there is generally one solution that is of interest to us. For example, if we are interested in the number of subsets of a set, then the solution to Recurrence $\ref{2.2.1}$ that we care about is $s_{n} = 2^{n}$. Notice this is the only solution we have mentioned that satisfies $s_{0} = 1$.

Exercise $89$

Show that there is only one solution to Recurrence $\ref{2.2.1}$ that satisfies $s_{0} = 1$.

Exercise $90$

A first-order recurrence relation is one which expresses an in terms of $a_{n−1}$ and other functions of $n$, but which does not include any of the terms $a_{i}$ for $i < n − 1$ in the equation.

1. Which of the recurrences $\ref{2.2.1}$ through $\ref{2.2.6}$ are first order recurrences?
2. Show that there is one and only one sequence $a_{n}$ that is defined for every nonnegative integer $n$, satisfies a given first order recurrence, and satisfies $a_{0} = a$ for some fixed constant $a$. (Hint).

Figure $\PageIndex{1}$: The Towers of Hanoi Puzzle (Copyright; author via source)

$\rightarrow$ Exercise $91$

The “Towers of Hanoi” puzzle has three rods rising from a rectangular base with $n$ rings of different sizes stacked in decreasing order of size on one rod. A legal move consists of moving a ring from one rod to another so that it does not land on top of a smaller ring. If $m_{n}$ is the number of moves required to move all the rings from the initial rod to another rod that you choose, give a recurrence for $m_{n}$. (Hint).

$\rightarrow$ Exercise $92$

We draw $n$ mutually intersecting circles in the plane so that each one crosses each other one exactly twice and no three intersect in the same point. (As examples, think of Venn diagrams with two or three mutually intersecting sets.) Find a recurrence for the number $r_{n}$ of regions into which the plane is divided by $n$ circles. (One circle divides the plane into two regions, the inside and the outside.) Find the number of regions with $n$ circles. For what values of $n$ can you draw a Venn diagram showing all the possible intersections of $n$ sets using circles to represent each of the sets? (Hint).

2.2.2: Arithmetic Series (optional)

Exercise $93$

A child puts away two dollars from her allowance each week. If she starts with twenty dollars, give a recurrence for the amount $a_n$ of money she has after $n$ weeks and find out how much money she has at the end of $n$ weeks.

Exercise $94$

A sequence that satisfies a recurrence of the form $a_{n} = a_{n−1} + c$ is called an arithmetic progression. Find a formula in terms of the initial value $a_{0}$ and the common difference $c$ for the term an in an arithmetic progression and prove you are right.

Exercise $95$

A person who is earning $$50,000$ per year gets a raise of $$3000$ a year for $n$ years in a row. Find a recurrence for the amount $a_n$ of money the person earns over $n+1$ years. What is the total amount of money that the person earns over a period of $n + 1$ years? (In $n + 1$ years, there are $n$ raises.)

Exercise $96$

An arithmetic series is a sequence $s_{n}$ equal to the sum of the terms $a_{0}$ through $a_n$ of an arithmetic progression. Find a recurrence for the sum $s_{n}$ of an arithmetic progression with initial value $a_{0}$ and common difference $c$ (using the language of Problem 94). Find a formula for general term $s_n$ of $a_n$ arithmetic series.

2.2.3: First Order Linear Recurrences

Recurrences such as those in Equations $\ref{2.2.1}$ through $\ref{2.2.5}$ are called linear recurrences, as are the recurrences of Problems 91 and 92. A linear recurrence is one in which an is expressed as a sum of functions of $n$ times values of (some of the terms) $a_{i}$ for $i < n$ plus (perhaps) another function (called the driving function) of $n$. A linear equation is called homogeneous if the driving function is zero (or, in other words, there is no driving function). It is called a constant coefficient linear recurrence if the functions that are multiplied by the $a_i$ terms are all constants (but the driving function need not be constant).

Exercise $97$

Classify the recurrences in Equations $\ref{2.2.1}$ through $\ref{2.2.5}$ and Problems 91 and 92 according to whether or not they are constant coefficient, and whether or not they are homogeneous.

$\bullet$ Exercise $98$

As you can see from Problem 97 some interesting sequences satisfy first order linear recurrences, including many that have constant coefficients, have constant driving term, or are homogeneous. Find a formula in terms of $b, d, a_{0}$ and $n$ for the general term an of a sequence that satisfies a constant coefficient first order linear recurrence $a_{n} = ba_{n−1} + d$ and prove you are correct. If your formula involves a summation, try to replace the summation by a more compact expression. (Hint).

2.2.4: Geometric Series

A sequence that satisfies a recurrence of the form $a_{n} = ba_{n−1}$ is called a geometric progression. Thus the sequence satisfying Equation $\ref{2.2.1}$, the recurrence for the number of subsets of an $n$-element set, is an example of a geometric progression. From your solution to Problem 98, a geometric progression has the form $a_{n} = a_{0}b^{n}$. In your solution to Problem 98 you may have had to deal with the sum of a geometric progression in just slightly different notation, namely $\sum^{n-1}_{i=0} db^{i}$. A sum of this form is called a (finite) geometric series.

Exercise $99$

Do this problem only if your final answer (so far) to Problem 98 contained the sum $\sum^{n-1}_{i=0} db^{i}$.

1. Expand $(1 − x)(1 + x)$. Expand $(1 − x)(1 + x + x^{2})$. Expand $(1 − x)(1 + x + x^{2} + x^{3})$.
2. What do you expect $(1 − b)\sum^{n-1}_{i=0} db^{i}$ to be? What formula for $\sum^{n-1}_{i=0} db^{i}$ does this give you? Prove that you are correct.

In Problem 98 and perhaps 99 you proved an important theorem. While the theorem does not have a name, the formula it states is called the sum of a finite geometric series.

Theorem $\PageIndex{1}$

If $b \neq 1$ and $a_{n} = ba_{n−1} + d$, then $a_{n} = a_{0}b^{n} + d\dfrac{1-b^{n}}{1-b}$, then $a_{n} = a_{0} + nd$.

Corollary $\PageIndex{1}$

If $b \neq 1$, then $\sum^{n-1}_{i=0}b^{i} = \dfrac{1-b^{n}}{1-b}$. If $b = 1$, $\sum^{n-1}_{i=0}b^{i} = n$.