Proof that a recursive sequence converges

5 replies · 3K views · last reply
Mr Davis 97
Messages
1,461
Reaction score
44

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.
 
Seems ok, btw you can actually solve this recursive equation by iteration, and see that it's decreasing explicitly.
 
Mr Davis 97 said:

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.
 
One question. In showing that the sequence decreases, why didn't I have to use the inductive hypothesis?
 
Mr Davis 97 said:
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.
 
For [itex]n \geq 1[/itex], it follows from [tex] \frac34 \leq 1 - \frac{1}{4n^2} < 1[/tex] that [tex] 0 < |t_{n+1}| = \left|1 - \frac{1}{4n^2}\right||t_n| < |t_n|[/tex] and so [itex]|t_n|[/itex] is strictly decreasing. Since each [itex]t_n[/itex] is by construction a product of strictly positive reals we can immediately remove the absolute value signs.