18. Sequences

d2. Limits of Recursive Sequences

There are two step to finding the limit of a sequence which is defined recursively:

1. Show the sequence has a limit.
   This is usually done using the Bounded, Monotonic Sequence Theorem and Mathematical Induction.
and
2. Assuming the sequence has a limit, find the limit.
   Since step 2 is easier, we often do that first. Further, the result from step 2 often helps in step 1.

Consider the sequence given by the recursion relation $a_{n+1}=3\sqrt{a_n}$ with the initial term $a_1=3$. Does the sequence have a limit? If so, find the limit.

The first $5$ terms are: $\begin{aligned} a_1&=3 \\ a_2&=3\sqrt{a_1}=3\sqrt{3}\approx 5.196 \\ a_3&=3\sqrt{a_2}=3\sqrt{3\sqrt{3}}\approx 6.838 \\ a_4&=3\sqrt{a_3}=3\sqrt{3\sqrt{3\sqrt{3}}}\approx 7.845 \\ a_5&=3\sqrt{a_4}=3\sqrt{3\sqrt{3\sqrt{3\sqrt{3}}}}\approx 8.402 \end{aligned}$ Before showing the limit exists, we want to get some idea what the limit might be. So we assume the limit exists and try to find it.

2.   Assume the sequence has a limit $L$. Then $\lim\limits_{n\to\infty}a_n=L$ and also $\lim\limits_{n\to\infty}a_{n+1}=L$ since $a_{n+1}$ is the same sequence as $a_n$ but starting from a different number. We apply $\lim\limits_{n\to\infty}$ to both sides of the recursion relation and use the limit laws: $\begin{aligned} a_{n+1} &=3\sqrt{a_n} \\ \lim_{n\to\infty}a_{n+1} &=3\sqrt{\lim_{n\to\infty}a_n} \\ L&=3\sqrt{L} \end{aligned}$ We can solve this for $L$ by squaring both sides: $\begin{aligned} L^2=9L \quad \Longrightarrow \quad L^2-9L=0 \quad \Longrightarrow\\ L(L-9)=0 \quad \Longrightarrow \quad L=0 \qquad \text{or} \quad 9 \end{aligned}$ This says that if a limit exists, it must be either $0$ or $9$. Looking at the first five terms, we expect the limit is $9$.

We now turn to showing the limit actually exists.

1.   To show the limit exists, we use the Bounded, Monotonic Sequence Theorem. Looking at the first five terms, we expect the sequence is increasing and bounded above by $9$. To prove each of these we will use mathematical induction:

Bounded above by $9$ We have $a_1=3\lt 9$. Suppose for some $k$ we have $a_k\lt 9$. Then $\sqrt{a_k}<3$ and $a_{k+1}=3\sqrt{a_k}<9$. By mathematical induction, $a_n<9$ for all $n$.

Increasing Notice the first five terms are increasing. Suppose for some $k$ we have $a_k < a_{k+1}$. Then $\sqrt{a_k} < \sqrt{a_{k+1}}$ and $3\sqrt{a_k} < 3\sqrt{a_{k+1}}$ which says $a_{k+1} < a_{k+2}$. By mathematical induction, the sequence is increasing.

Therefore: The sequence has a limit and the limit must be $9$.

Here are some exercises:

Exercises