Skip to main content

Beginning Activity Beginning Activity 1: Recursively Defined Sequences
A4US

In a proof by mathematical induction, we “start with a first step” and then prove that we can always go from one step to the next step. We can use this same idea to define a sequence as well. We can think of a sequence as an infinite list of numbers that are indexed by the natural numbers (or some infinite subset of \(\mathbb{N} \cup \left\{ 0 \right\}\)). We often write a sequence in the following form:

\begin{equation*} a_1, a_2, \ldots,a_n, \ldots\text{.} \end{equation*}

The number \(a_n\) is called the \(n^\text{ th }\) term of the sequence. One way to define a sequence is to give a specific formula for the \(n^\text{ th }\) term of the sequence such as \(a_n = \dfrac{1}{n}\text{.}\)

Another way to define a sequence is to give a specific definition of the first term (or the first few terms) and then state, in general terms, how to determine \(a_{n + 1}\) in terms of \(n\) and the first \(n\) terms \(a_1 ,a_2 , \ldots ,a_n\text{.}\) This process is known as definition by recursion and is also called a recursive definition. The specific definition of the first term is called the initial condition, and the general definition of \(a_{n + 1}\) in terms of \(n\) and the first \(n\) terms \(a_1 ,a_2 , \ldots ,a_n\) is called the recurrence relation. (When more than one term is defined explicitly, we say that these are the initial conditions.) For example, we can define a sequence recursively as follows:

\(b_1 = 16\text{,}\) and for each \(n \in \mathbb{N}\text{,}\) \(b_{n + 1} = \dfrac{1}{2}b_n\text{.}\)

Using \(n = 1\) and then \(n = 2\text{,}\) we then see that

\begin{align*} b_2 \amp = \frac{1}{2} b_1 \amp b_3 \amp = \frac{1}{2} b_2\\ \amp = \frac{1}{2} \cdot 16 \amp \amp = \frac{1}{2} \cdot 8\\ \amp = 8 \amp \amp = 4 \end{align*}

1.

Calculate \(b_4\) through \(b_{10}\text{.}\) What seems to be happening to the values of \(b_n\) as \(n\) gets larger?

2.

Define a sequence recursively as follows:

\(T_1 = 16\text{,}\) and for each \(n \in \mathbb{N}\text{,}\) \(T_{n + 1} = 16 + \dfrac{1}{2}T_n\text{.}\)
Then \(T_2 = 16 + \dfrac{1}{2} T_1 = 16 + 8 = 24\text{.}\) Calculate \(T_3\) through \(T_{10}\text{.}\) What seems to be happening to the values of \(T_n\) as \(n\) gets larger?

The sequences in Exercise 1 and Exercise 2 can be generalized as follows: Let \(a\) and \(r\) be real numbers. Define two sequences recursively as follows:

\(a_1 = a\text{,}\) and for each \(n \in \mathbb{N}\text{,}\) \(a_{n + 1} = r \cdot a_n\text{.}\)
\(S_1 = a\text{,}\) and for each \(n \in \mathbb{N}\text{,}\) \(S_{n + 1} = a + r \cdot S_n\text{.}\)

3.

Determine formulas (in terms of \(a\) and \(r\)) for \(a_2\) through \(a_6\text{.}\) What do you think \(a_n\) is equal to (in terms of \(a\text{,}\) \(r\text{,}\) and \(n\))?

4.

Determine formulas (in terms of \(a\) and \(r\)) for \(S_2\) through \(S_6\text{.}\) What do you think \(S_n\) is equal to (in terms of \(a\text{,}\) \(r\text{,}\) and \(n\))?

In Beginning Activity 1 in Section 4.2, for each natural number \(n\text{,}\) we defined \(n!\text{,}\) read \(n\) factorial, as the product of the first \(n\) natural numbers. We also defined \(0!\) to be equal to 1. Now recursively define a sequence of numbers \(a_0 ,a_1 ,a_2 , \ldots\) as follows:

\(a_0 = 1\text{,}\) and
for each nonnegative integer \(n\text{,}\) \(a_{n + 1} = \left( {n + 1} \right) \cdot a_n\text{.}\)

Using \(n=0\text{,}\) we see that this implies that \(a_1 =1 \cdot a_0 = 1 \cdot 1 = 1\text{.}\) Then using \(n = 1\text{,}\) we see that

\begin{equation*} a_2 = 2 a_1 = 2 \cdot 1 = 2\text{.} \end{equation*}

5.

Calculate \(a_3, a_4, a_5\text{,}\) and \(a_6\text{.}\)

6.

Do you think that it is possible to calculate \(a_{20}\) and \(a_{100}\text{?}\) Explain.

7.

Do you think it is possible to calculate \(a_n\) for any natural number \(n\text{?}\) Explain.

8.

Compare the values of \(a_0 ,a_1 ,a_2 ,a_3 ,a_4 ,a_5\text{,}\) and \(a_6\) with those of \(0!,1!,2!,3!,4!,5!\text{,}\) and \(6!\text{.}\) What do you observe? We will use mathematical induction to prove a result about this sequence in Exercise 1.