Show that a recursive sequence converges

[Mr Davis 97]

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...

 

[.Scott]

You are right.
It should be a "converging" sequence.
Or perhaps they should exempt $a_0$ from the sequence.

 

[LCKurtz]

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$.

 

[Mr Davis 97]

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}$.

 

[Stephen Tashi]

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.