Show that a recursive sequence converges

  • #1
1,462
44

Homework Statement


Let ##x,y## be positive numbers. Let ##a_0 = y## and let ##a_n = \frac{(x/a_{n-1})+a_{n-1}}{2}##. Prove that ##(a_n)## is a decreasing sequence with limit ##\sqrt{x}##.

Homework Equations




The Attempt at a Solution


I'm confused about the initial condition being an arbitrary positive real number. This is because it says to prove that ##(a_n)## is a decreasing sequence, but what if ##0<y< \sqrt{x}##? Then ##(a_n)## can't be decreasing...
 

Answers and Replies

  • #2
.Scott
Homework Helper
2,677
985
You are right.
It should be a "converging" sequence.
Or perhaps they should exempt ##a_0## from the sequence.
 
  • #3
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,556
767
What you can show is ##a_n \ge \sqrt x## for ##n\ge 1## regardless whether or not ##a_0 = y < \sqrt x##, and that ##a_{n+1}\le a_n## for ##n\ge 1##.
 
  • #4
1,462
44
What you can show is ##a_n \ge \sqrt x## for ##n\ge 1## regardless whether or not ##a_0 = y < \sqrt x##, and that ##a_{n+1}\le a_n## for ##n\ge 1##.
Here is my argument:

(1) WTS: ##\forall n \ge 1##, ##a_n \ge \sqrt{x}##.

Note that it is true that ##(x - y^2)^2 \ge 0##. This implies that ##x^2-2xy^2+y^4 \ge 0 \implies x^2 + y^4 \ge 2y^2x \implies x+y^2 \ge 2y\sqrt{x} \implies \frac{\frac{x}{y} + y}{2} \ge \sqrt{x} \implies a_1 \ge \sqrt{x}##. So the base case is satisfied. Now, suppose that for some ##k \in \mathbb{N}## we have that ##a_k \ge \sqrt{x}##. Then ##a_{k+1} = \frac{\frac{x}{a_k} + a_k}{2} \ge \frac{\frac{x}{\sqrt{x}} + \sqrt{x}}{2} = \sqrt{x}##. This completes the induction.

(2) WTS: ##\forall n \ge 1##, ##a_n \ge a_{n+1}##. We see that ##a_{n+1} = \frac{\frac{x}{a_n}+a_n}{2} \le \frac{\frac{a^2_n}{a_n}+a_n}{2} = a_n##.

So we see that ##(a_n)## is bounded below and is decreasing, so by the MCT it has a limit, L. Then ##L = \frac{\frac{x}{L}+L}{2} \implies L = \sqrt{x}##.
 
  • #5
Stephen Tashi
Science Advisor
7,576
1,466
Let ##a_0 = y##
What is the convention used by your text materials for the first index of a sequence? Is it 1? - or 0? - can it be either?

A nice legality could be that ##a_0## is defined as a member of a set, but it is not a member of the sequence if the text materials insist the first index of a sequence must be 1.
 

Related Threads on Show that a recursive sequence converges

Replies
5
Views
765
Replies
6
Views
1K
  • Last Post
Replies
5
Views
9K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
3
Views
355
  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
9
Views
647
  • Last Post
Replies
1
Views
1K
Top