Evaluating Limits of Recursive Sequences

# Evaluating Limits of Recursive Sequences

Recall that one way to represent a sequence is by a recursive formula. For example, the Fibonacci sequence $\{ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... \}$ is defined recursively with $f_1 = 1$, $f_2 = 1$ and $f_n = f_{n-1} + f_{n-2}$ for all natural numbers $n ≥ 3$. We are now going to look at taking the limit of these sequences.

## Example 1

Evaluate the limit of the sequence defined by $a_1 = 1$ and $a_{n+1} = \sqrt{6 + a_n}$.

To evaluate this limit, we will do shorthand induction to first show that the sequence $\{ a_n \}$ is increasing and bounded above.

First we note that $a_1 = 1$, $a_2 = \sqrt{6 + a_1} = \sqrt{7}$, and $a_3 = \sqrt{6 + a_2} = \sqrt{6 + \sqrt{7}}$. In each case, our sequence appears to be increasing, and we will prove this with mathematical induction. Our base case $a_1 < a_2$ is already shown above. Suppose that $a_k < a_{k+1}$. We want to show that $a_{k+1} < a_{k+2}$. We get that $a_{k+2} = \sqrt{6 + a_{k+1}} > \sqrt{6 + a_k} = a_{k+1}$, and so $\{ a_n \}$ is increasing.

Now we need to show that $\{ a_n \}$ is bounded. We assume that $\{ a_n \}$ is bounded above by $3$ since $a_1 = 1 < 3$. Now suppose that $a_k < 3$. We want to show that $a_{k+1} < 3$. So we have that $a_{k+1} = \sqrt{6 + a_k} < \sqrt{6 + 3} = 3$. Therefore $a_n < 3$.

Now recall that since $f(x) = \sqrt{6 + x}$ is a continuous function, we have that:

(1)
\begin{align} L = \lim_{n \to \infty} a_{n+1} = \lim_{n \to \infty} \sqrt{6 + a_n} = \sqrt{6 + \lim_{n \to \infty} a_n} = \sqrt{6 + L} \end{align}

Therefore we need to solve the equation $L = \sqrt{6 + L}$ or rather $L^2 = 6 + L$ which has a solution when $L = 3$ and $L = -2$. We choose $L = 3$ since our limit can't be negative since $\{ a_n \}$ is ultimately increasing.

## Example 2

Evaluate the limit $\lim_{n \to \infty} \frac{f_{n+1}}{f_n}$ defined by the Fibonacci sequence $f_1 = 1$, $f_2 = 1$, and $f_n = f_{n-1} + f_{n-2}$ for $n ≥ 3$.

We first must our sequence $\{ a_n \} = \frac{f_{n+1}}{f_n}$represents by the quotient of two successive Fibonacci numbers. Evaluating a few terms we get $a_1 = 1$, $a_2 = 2$, $a_3 = \frac{3}{2}$, and $a_4 = \frac{5}{3}$. We suspect that $\{ a_n \}$ converges and is bounded between $1$ and $2$, that is $1 ≤ a_n ≤ 2$ for every $n = 1, 2, ...$. We will show this to be true. Clearly $1 ≤ a_1 ≤ 2$. Now suppose that $1 ≤ a_k = \frac{f_{k+1}}{f_k} ≤ 2$ for some $k$. We want to show that $1 ≤ a_{k+1} ≤ 2$. Well $a_{k+1} = \frac{f_{k+2}}{f_{k+1}} = \frac{f_{k+1} + f_k}{f_{k+1}} = 1 + \frac{f_k}{f_{k+1}}$. But $1 ≤ a_k ≤ 2$ which implies that $1 ≤ \frac{f_{k+1}}{f_k} ≤ 2$ which implies that $1 ≥ \frac{f_k}{f_{n+k}} ≥ \frac{1}{2}$. Therefore $1 ≤ a_{k+1} ≤ 2$, so $1 ≤ a_n ≤ 2$ for all $n = 1, 2, ...$.

So then:

(2)
\begin{align} \quad L = \lim_{n \to \infty} a_n = \lim_{n \to \infty} \frac{f_{n+1}}{f_n} = \lim_{n \to \infty} \frac{f_{n} + f_{n-1}}{f_n} = 1 + \lim_{n \to \infty} \frac{f_{n-1}}{f_n} = 1 + \frac{1}{L} \end{align}

Therefore we must solve the equation $L = 1 + \frac{1}{L}$ or rather $0 = L^2 - L - 1$. Using the quadratic formula we get that $L = \frac{1 \pm \sqrt{1 - 4(1)(-1)}}{2} = \frac{1 \pm \sqrt{5}}{2}$. So we have two solutions for $L$ but since $1 ≤ a_n ≤ 2$ for all $n = 1, 2, ...$ we get that $L = \frac{1 + \sqrt{5}}{2} = \phi$. This limit is especially important since it is the golden ratio.