Mathematical Reasoning: Writing and Proof (PreTeXt Edition)

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:

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={\displaystyle \frac{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,\dots ,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,\dots ,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}={\displaystyle \frac{1}{2}}{b}_n\text{.}$

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

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{.}$

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,\dots$ 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