Proof that a recursive sequence converges

  • #1
1,456
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.
 

Answers and Replies

  • #2
MathematicalPhysicist
Gold Member
4,300
205
Seems ok, btw you can actually solve this recursive equation by iteration, and see that it's decreasing explicitly.
 
  • #3
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728

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.
 
  • #4
1,456
44
One question. In showing that the sequence decreases, why didn't I have to use the inductive hypothesis?
 
  • #5
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
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.
 
  • #6
pasmith
Homework Helper
1,827
488
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.
 

Related Threads on Proof that a recursive sequence converges

Replies
4
Views
434
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
5
Views
9K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
3
Views
318
  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
1
Views
1K
Replies
4
Views
1K
Replies
3
Views
3K
Replies
6
Views
1K
Top