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.

Please provide any hints.

  • $\begingroup$ is this $$a_{k+1}=\frac{1}{2}\left(a_k+\frac{k}{a_k}\right)$$? $\endgroup$ – Dr. Sonnhard Graubner Sep 6 '17 at 16:07
  • $\begingroup$ No. See the pic from the book. It's problem 7 imgur.com/zujzuYA $\endgroup$ – Rahul Sep 6 '17 at 16:14
  • $\begingroup$ $k$ is supposed to be an integer ? $\endgroup$ – Gabriel Romon Sep 6 '17 at 16:22
  • $\begingroup$ @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 $\endgroup$ – Rahul Sep 6 '17 at 16:49
  • $\begingroup$ @Rahul: Can you tell us which book (author, title, edition)? $\endgroup$ – 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$

  • $\begingroup$ 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$". $\endgroup$ – quasi Sep 6 '17 at 23:30
  • $\begingroup$ @quasi I explained it in the main text. $\endgroup$ – Andreas Sep 7 '17 at 14:27
  • $\begingroup$ 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$. $\endgroup$ – quasi Sep 7 '17 at 15:07
  • $\begingroup$ @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. $\endgroup$ – Andreas Sep 7 '17 at 16:09
  • $\begingroup$ Thanks @Andreas. $\endgroup$ – Rahul Sep 8 '17 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.