Week 2, Lecture 6: Recursive Sequences and Divergence to Infinity

🎯 Rigorous Proof of Convergence via Error Contraction

Let's define our Error at step $n$ (the absolute distance to the target) as $\text{Error}_n = |a_n - \sqrt{2}|$.

We want to prove that taking a step in our recursive machine forces this error to shrink significantly.

Step 1: Calculate the Error for the next step ($n+1$)

Step 2: Find a common denominator to combine the terms

Step 3: Factor out the previous Error ($|a_n - \sqrt{2}|$)

(By factoring out $(1 - \sqrt{2})$ from the numerator, we can separate our previous error from the rest of the garbage)

(If the algebra in the numerator seems to jump too fast, here is the exact breakdown of how we separate the previous error from the rest of the terms)

• Group the terms: Rearrange the numerator to group the $a_n$ terms together and the constants together: $a_n - \sqrt{2}a_n + 2 - \sqrt{2}$.
• Factor the groups: Pull $a_n$ out of the first pair, and pull $\sqrt{2}$ out of the second pair (remembering that $2 = \sqrt{2} \cdot \sqrt{2}$):
  $$a_n(1 - \sqrt{2}) + \sqrt{2}(\sqrt{2} - 1)$$
• Match the factors: To make the pieces in the parentheses match, rewrite $\sqrt{2}(\sqrt{2} - 1)$ as $-\sqrt{2}(1 - \sqrt{2})$. Now factor $(1 - \sqrt{2})$ out of the entire numerator:
  $$(1 - \sqrt{2})(a_n - \sqrt{2})$$
• Separate the absolute values: The absolute value of a product is the product of the absolute values. Since $|1 - \sqrt{2}| = \sqrt{2} - 1$ and $|a_n + 1| = a_n + 1$, we are left with:

Step 4: Prove the Shrinkage

We now have this relationship: $\text{Error}_{n+1} = \left(\frac{\sqrt{2} - 1}{a_n + 1}\right) \cdot \text{Error}_n$.

Look at the fraction multiplying our old error. We know $\sqrt{2} - 1 \approx 0.414$. We also know our sequence terms $a_n$ are always at least $1$, making the denominator $(a_n + 1)$ at least $2$.

Therefore, the fraction $\frac{0.414}{\text{at least } 2}$ is safely smaller than $\frac{1}{2}$. We have successfully proven that our error gets chopped by more than half every single step:

Because multiplying by a fraction less than $1$ repeatedly drives a number to zero (e.g., $\left(\frac{1}{2}\right)^n \to 0$), the Squeeze Theorem forces our Error sequence to exactly $0$. The sequence has no choice but to converge exactly to $\sqrt{2}$. $\blacksquare$

🎯 Worked Example: The Nested Radical

Let's define a sequence by $x_1 = \sqrt{2}$, and $x_{n+1} = \sqrt{2 + x_n}$. What is its limit?

(Scratchpad math: If we assume a limit $L$ exists, $L = \sqrt{2+L}$, which squares to $L^2 - L - 2 = 0$. Factoring gives $(L-2)(L+1)=0$. Since our terms are positive, the limit must be 2. Now we know 2 is the ceiling we need to prove!)

Step 1: Prove Boundedness (Show it never passes 2)

• Base Case: For $n=1$, $x_1 = \sqrt{2} \approx 1.414$, which is strictly less than $2$.
• Inductive Assumption: Assume that for some step $k$, $x_k < 2$.
• Inductive Step: We must prove $x_{k+1} < 2$.
  $$x_{k+1} = \sqrt{2 + x_k}$$
  Because we assumed $x_k < 2$, we can replace $x_k$ with 2 to create a strict inequality:
  $$x_{k+1} < \sqrt{2 + 2} = \sqrt{4} = 2$$
  By induction, the sequence is bounded above by 2 forever.

Step 2: Prove Monotonicity (Show it is always increasing)

• Base Case: $x_2 = \sqrt{2 + \sqrt{2}} \approx 1.84$. This is greater than $x_1$ ($1.414$). So, $x_2 > x_1$.
• Inductive Assumption: Assume that at step $k$, the sequence increased: $x_{k} > x_{k-1}$.
• Inductive Step: We must prove it increases at the next step: $x_{k+1} > x_k$.
  $$x_{k+1} = \sqrt{2 + x_k}$$
  Because we assumed $x_k > x_{k-1}$, we can swap them out to maintain the inequality:
  $$x_{k+1} > \sqrt{2 + x_{k-1}}$$
  But notice that $\sqrt{2 + x_{k-1}}$ is exactly the definition of $x_k$. Therefore, $x_{k+1} > x_k$. By induction, it is strictly increasing.

Step 3: Invoke the MCT

Because the sequence is strictly increasing (Step 2) and securely trapped below a ceiling of 2 (Step 1), the Monotone Convergence Theorem formally guarantees that a finite limit $\lim x_n = L$ exists.

Step 4: Solve Algebraically

Because Step 3 gave us mathematical permission, we can now take the limit of the formula $x_{n+1} = \sqrt{2 + x_n}$. Every term becomes $L$:

Factoring gives $(L-2)(L+1) = 0$. Since our sequence consists entirely of positive square roots, the limit cannot be $-1$. The limit is exactly $2$. $\blacksquare$

🎯 Worked Example: Proving $\lim_{n\to\infty} \sqrt{n} = \infty$

Just like the $\epsilon\text{-}N$ proofs from earlier, $M\text{-}N$ proofs follow a predictable game: the challenger hands you an arbitrary threshold $M$, and you must use algebra to find the exact step $N$ where the sequence permanently breaks past it.

Step 1: The Challenge

Let $M > 0$ be an arbitrary, massively large threshold given to us.

Step 2: The Algebraic Scratch-Work

We want our sequence to break the threshold. So, we set up the inequality $a_n > M$ and solve for $n$:

Step 3: The Formal Choice

Based on our scratch-work, we choose our cutoff index $N$ to be any natural number greater than $M^2$.

Step 4: The Proof

If we take any step $n > N$, it immediately follows that $n > M^2$. Taking the square root of both sides of that inequality, we get exactly what we needed to show:

Because we proved the sequence eventually exceeds any arbitrary threshold $M$, we have formally proven that $\lim_{n\to\infty} \sqrt{n} = \infty$. $\blacksquare$

🎯 Theorem: Geometric Sequences Diverge Faster Than Linear Ones

Let $a_n = c r^n$ be a geometric sequence with $r > 1$ and $c > 0$. Let $b_n = \alpha n + \beta$ be a linear sequence ($\alpha > 0$). We will prove that $\frac{a_n}{b_n} \to \infty$ by focusing on the core engine of the sequences: we will prove $\frac{r^n}{n} \to \infty$.

Step 1: The Binomial Expansion

Write $r = 1 + \epsilon$ for some $\epsilon > 0$. By the Binomial Formula, expanding $(1 + \epsilon)^n$ gives us a sum of positive terms:

Because every term is positive, if we chop off everything after the first three terms, the right side becomes strictly smaller. This gives us a guaranteed floor:

Step 2: Divide by the Linear Engine ($n$)

Our goal is to analyze the ratio $\frac{r^n}{n}$, so let's divide our entire inequality by $n$:

Step 3: Evaluate the Limit

Let's look at what happens to the right side of our inequality as $n \to \infty$:

• The $\frac{1}{n}$ term shrinks to $0$.
• The $\epsilon$ term is just a constant.
• The $\frac{n-1}{2}\epsilon^2$ term has an $n$ in the numerator, meaning it grows without bound (to $\infty$).

Because the right side of our inequality explodes to infinity, the left side ($\frac{r^n}{n}$) is physically pushed to infinity as well. Because the geometric sequence contains an $n^2$ engine hidden inside its expansion, it completely overpowers and dominates any linear polynomial. $\blacksquare$