Proof that a recursive sequence converges

[Mr Davis 97]

Homework Statement

Prove that $\displaystyle t_{n+1} = (1 - \frac{1}{4n^2}) t_n$ where $t_1=1$ converges.

Homework Equations

The Attempt at a Solution

First, we must prove that the sequence is bounded below. We will prove that it is bounded below by 0. $t_1 = 1 \ge 0$, so the base case holds. Now, suppose that $t_k \ge 0$. Then $t_{k+1} = (1 - \frac{1}{4k^2}) t_k \ge (1 - \frac{1}{4k^2}) (0) = 0$. So the induction is complete, and the sequence is bounded below by 0.

Now we must show that the sequence is decreasing. $t_2 = 15/16 \le 1 = t_1$, so the base case holds. Now, suppose that $t_{k+1} \le t_k$. Then $t_{k+2} = (1 - \frac{1}{4(k+1)^2})t_{k+1} \le t_{k+1}$. So the induction is complete, and the sequence is decreasing.

By the Monotone Convergence Theorem, the sequence converges.

 

[MathematicalPhysicist]

Seems ok, btw you can actually solve this recursive equation by iteration, and see that it's decreasing explicitly.

 

[Ray Vickson]

Homework Statement

Prove that $\displaystyle t_{n+1} = (1 - \frac{1}{4n^2}) t_n$ where $t_1=1$ converges.

Homework Equations

The Attempt at a Solution

First, we must prove that the sequence is bounded below. We will prove that it is bounded below by 0. $t_1 = 1 \ge 0$, so the base case holds. Now, suppose that $t_k \ge 0$. Then $t_{k+1} = (1 - \frac{1}{4k^2}) t_k \ge (1 - \frac{1}{4k^2}) (0) = 0$. So the induction is complete, and the sequence is bounded below by 0.

Now we must show that the sequence is decreasing. $t_2 = 15/16 \le 1 = t_1$, so the base case holds. Now, suppose that $t_{k+1} \le t_k$. Then $t_{k+2} = (1 - \frac{1}{4(k+1)^2})t_{k+1} \le t_{k+1}$. So the induction is complete, and the sequence is decreasing.

By the Monotone Convergence Theorem, the sequence converges.

Another, perhaps easier way is to note that
$$|t_{n+1}-t_n| = \frac{1}{4n^2} |t_n| \leq \frac{1}{4} |t_n|,$$
so we have (at least) geometrically fast convergence.

 

[Mr Davis 97]

One question. In showing that the sequence decreases, why didn't I have to use the inductive hypothesis?

 

[Ray Vickson]

One question. In showing that the sequence decreases, why didn't I have to use the inductive hypothesis?

$$ \frac{t_{n+1}}{t_n }= 1 - \frac{1}{4n^2} ,$$
so if you know that $t_n > 0$ then you have $0 < t_{n+1}/t_n < 1,$ hence a positive strictly decreasing sequence.

 

[pasmith]

For $n \geq 1$, it follows from $$\frac34 \leq 1 - \frac{1}{4n^2} < 1$$ that $$0 < |t_{n+1}| = \left|1 - \frac{1}{4n^2}\right||t_n| < |t_n|$$ and so $|t_n|$ is strictly decreasing. Since each $t_n$ is by construction a product of strictly positive reals we can immediately remove the absolute value signs.