# Convergence of recursive sequence $a_{n+1} =\frac{ 1}{k} \left(a_{n} + \frac{k}{a_{n}}\right)$

Let $$a_{n+1} = \frac{1}{k} \left(a_{n} + \frac{k}{a_n}\right) ; k>1, a_1>0$$ The problem is to show that it converges.

Attempt: The sequence is not monotone but it has a lower bound. It seems that odd terms subsequence and even term subsequence are monotonic sequences (I wrote some basic code to make this observation) though I am not able to prove it analytically. I also know that if odd subsequence and even subsequence converge to same limit then the sequence also converges. So, that tells me that I am on the right track.

• is this $$a_{k+1}=\frac{1}{2}\left(a_k+\frac{k}{a_k}\right)$$? – Dr. Sonnhard Graubner Sep 6 '17 at 16:07
• No. See the pic from the book. It's problem 7 imgur.com/zujzuYA – Rahul Sep 6 '17 at 16:14
• $k$ is supposed to be an integer ? – Gabriel Romon Sep 6 '17 at 16:22
• @LeGrandDODOM no. But I don't think it matters. If 0<k<1 then the sequence is monotone. So that's why it assumes k to be greater than 1 – Rahul Sep 6 '17 at 16:49
• @Rahul: Can you tell us which book (author, title, edition)? – quasi Sep 6 '17 at 19:10

If it converges, one can solve immediately for $a_\infty = \frac{\sqrt k}{\sqrt{k-1}}$.

So define $b_n = a_n \frac{\sqrt{k-1}}{\sqrt k}$. This gives the recursion

$b_{n+1} = \frac{1}{k} \left(b_{n} + \frac{{k-1}}{b_{n}}\right)$

which, if convergent, gives $b_\infty = 1$.

We will show that a lower bound and an upper bound both converge to $b_\infty = 1$ from an arbitrary starting point. Hence $b_\infty = 1$ is a unique fixed point and convergence is global.

Let's begin with a lower bound.

Using $1/x = 1/(1 + x-1) \ge 1 - (x-1) = 2 -x$ we have

$b_{n+1} = \frac{1}{k} \left(b_{n} + \frac{{k-1}}{b_{n}}\right) \ge \frac{1}{k} \left(b_{n} + {{(k-1)}}{(2-b_{n})}\right) = \frac{1}{k} \left(b_{n} (2-k) + {(2k-2)}\right)$

and the RHS establishes a lower bound $b^-_n \le b_n$ given by the recursion $b^-_{n+1} = \frac{1}{k} \left(b^-_{n} (2-k) + {(2k-2)}\right)$. We can inspect this recursion to see if and where the lower bound converges to.

According to Banach's contraction theorem for iterating fixed points in the form $x_{n+1} = f(x_n)$ convergence is guaranteed if the absolute value of the derivative is less than 1, i.e. $|f'(x)| < 1$, for some interval of $x$ containing the fixed point. Here, for $b^-_n$ in particular, $f(x_n)$ is a line equation and convergence is global if the absolute slope is less than 1.

Since the absolute slope $|2-k|/k$ is always $< 1$ for $k > 1$, iterating the lower bound $b^-_n$ converges, and solving $b^- = \frac{1}{k} \left(b^- (2-k) + {(2k-2)}\right)$ results in the lower bound limit $b^-_\infty= 1$. So the lower bound converges to the actual value that the original series should attain (if convergent), which proves convergence from below.

Now for the upper bound.

Suppose $b_1 <1$. Then $b_2 >1$. So let us suppose w.l.o.g. that we start with some $b_1 >1$.

Then we have that

$b_{n+1} = \frac{1}{k} \left(b_{n} + \frac{{k-1}}{b_{n}}\right) < \frac{1}{k} \left(b_{n} +{{k-1}}\right)$

provided that $b_{n} > 1$. This is certainly true for $n=1$, and we would like to keep it that way.

So we have an upper bound $b^+_n$ given by the recursion

$b^+_{n+1} = \frac{1}{k} \left(b^+_{n} + {{k-1}}\right)$.

Clearly, if $b^+_{n} > 1$, so is $b^+_{n+1} > 1$, so our condition $b^+_{n} > 1$ holds for all $n$, starting with $b^+_{1} > 1$, and we can work with that upper bound.

Now apply again the contraction theorem. Convergence is globally established since the slope is $\frac{1}{k} <1$, and the fixed point can immediately by computed as $b^+_\infty= 1$.

Hence upper and lower bound converge globally to the same value $b_\infty= 1$, which establishes that the original series also converges, from any starting point, to $b_\infty= 1$. $\quad \Box$

• Can you explain "the RHS establishes a lower bound"? Also, what is the definition of the symbol $b^-_n$? Note: I follow the logic up to that sentence (so I have no issue with the inequality established on the previous line). And I have no problem with "the absolute slope $|2-k|/k$ is always $<1$". – quasi Sep 6 '17 at 23:30
• @quasi I explained it in the main text. – Andreas Sep 7 '17 at 14:27
• Shouldn't the relevant function $f$ be $$f(x)=\frac{1}{k}\left(x + \frac{{k-1}}{x}\right)$$ ??  It has the unique fixed point $x=1$. – quasi Sep 7 '17 at 15:07
• @quasi IF it converges to the fixed point, the fixed point will be 1. But you must prove that iterations converge. I couldn't do that. What I proved is that a lower bound converges to the same fixed point. What remains to be done is to prove that an upper bound converges as well to the same fixed point. – Andreas Sep 7 '17 at 16:09
• Thanks @Andreas. – Rahul Sep 8 '17 at 13:37