Let $k>1$ and define a sequence $\left\{a_{n}\right\}$ by $a_{1}=1$ and $$a_{n+1}=\frac{k\left(1+a_{n}\right) }{\left(k+a_{n}\right)}$$ (a) Show that $\left\{a_{n}\right\}$ is monotonic increasing.

Assume $a_n \geq a_{n-1}$. Then,

$$a_{n+1} = \frac{k(1+a_n)}{k+a_n} \geq \frac{k(1+a_{n-1})}{k+a_n}....$$

But I get hung up on the $a_n$ in the denominator. I cannot replace it with $a_{n-1}$ since $a_n \geq a_{n-1}$. Is there a trick to get around this?


Turn the question of whether $(a_n)$ is monotone increasing into an inequality purely in terms of a single term $a_n$. In particular, $$a_n \le a_{n+1} = \frac{k(1 + a_n)}{k + a_n}.$$ Simplifying, making the temporary assumption that $k + a_n > 0$, $$a_n(k + a_n) \le k(1 + a_n) \iff a_n^2 - k \le 0 \iff a_n \in [-\sqrt{k}, \sqrt{k}].$$ Addressing this assumption, it is extremely easy to show $a_n > 0$ for all $n$ by induction, hence $k + a_n > k > 1 > 0$. Thus, you really just need to show $a_n \le \sqrt{k}$.

You can now show this by induction. In fact, you can bundle the positivity proof in as well. That is, you can show that $0 \le a_n \le \sqrt{k}$ for all $n$ by induction.

Let's begin. Since $k \ge 1$, note that $0 \le 1 \le \sqrt{k}$, hence $0 \le a_1 \le \sqrt{k}$.

Now, assume $0 \le a_n \le \sqrt{k}$. Then, \begin{align*} a_{n+1} &= \frac{k(1 + a_n)}{k + a_n} \\ &= \frac{k + k^2 + ka_n - k^2}{k + a_n} \\ &= \frac{k(k + a_n)}{k + a_n} + \frac{k - k^2}{k + a_n} \\ &= k - \frac{k^2 - k}{k + a_n}. \end{align*} Note that $k^2 - k > 0$, hence $x \mapsto k - \frac{k^2 - k}{k + x} = \frac{k(1 + x)}{k + x}$ is increasing for $x > -k$. So, since $-k < 0 \le a_n \le \sqrt{k}$, we have $$\frac{k(1 + 0)}{k + 0} \le \frac{k(1 + a_n)}{k + a_n} \le \frac{k(1 + \sqrt{k})}{k + \sqrt{k}} \implies 1 \le a_{n+1} \le \sqrt{k},$$ as required.

  • 1
    $\begingroup$ It's worth noting that I've written this up somewhat backwards. When writing up a proof, start by proving $0 \le a_n \le sqrt{k}$ (or more neatly, $1 \le a_n \le \sqrt{k}$) by induction. Then show $(a_n)$ is increasing. I've written it backwards because this was the way I figured it out: by looking for what I needed to be true in order for $(a_n)$ to be increasing, then proving it. $\endgroup$ – Theo Bendit Oct 14 '19 at 2:57
  • $\begingroup$ It is not clear to me why you need to show $0\leq a_n\leq \sqrt{k}$ $\endgroup$ – Jac Frall Oct 14 '19 at 3:02
  • $\begingroup$ It also seems that there would be a way to directly show that $a_n \geq a_{n-1}$ but I guess not $\endgroup$ – Jac Frall Oct 14 '19 at 3:03
  • $\begingroup$ YiFan's description helped explain the reasoning. I understand now! Thanks! $\endgroup$ – Jac Frall Oct 14 '19 at 3:07
  • 1
    $\begingroup$ @JacFrall I guess you only need $-k < a_n \le \sqrt{k}$. We need the upper bound to get $a_n^2 - k^2 \le 0$, which implies $a_n \le a_{n+1}$, under the additional assumption that $a_n + k > 0$ (hence the lower bound). I don't think there is a more direct way of doing this. Think about it this way: changing the initial value could easily make the sequence decrease instead (e.g. if $a_1 > \sqrt{k}$), so the position of the sequence points relative to $\sqrt{k}$ is important! $\endgroup$ – Theo Bendit Oct 14 '19 at 3:07

A possible way is to investigate the derivative of the function underlying the recursion and then use MVT together with induction:

  • $\boxed{f(x)} = k\frac{1+x}{k+x}= \frac{k+x + (k-1)x}{k+x}= 1 + (k-1)\frac{x}{k+x} = \boxed{1+ (k-1)\left(1 - \frac{k}{k+x} \right)}$
  • Note that $f(x) \geq 1$ for $x \geq 0$.
  • $f'(x)= \frac{k(k-1)}{(k+x)^2} >0$ for $k>1$
  • The induction start gives $$a_2 = \frac{2k}{k+1} = 1+\frac{k-1}{k+1}>1 = a_1$$
  • The induction step uses the MVT and the positivity of $f'$: $$a_{n+1}-a_n \stackrel{a_{n-1}< \xi_n < a_n}{=} \underbrace{f'(\xi_n)}_{>0}(a_n - a_{n-1}) > 0$$

So, the sequence is strictly increasing.


In general, to show that a sequence defined by the recurrence $a_{n+1}=f(a_n)$ is monotonically increasing, what you want to do is to show $a_{n+1}>a_n$, which converts to $f(a_n)>a_n$. Then you consider this inequality with the explicit $f$ given to you, and solve the inequality for the range of $a_n$ for which the inequality is true. If, in fact, your $a_n$ are guaranteed to lie in the range so that the inequality always holds, then you're done with the proof.

In this case, what you want to be doing is to show $$\frac{k(1+a_n)}{k+a_n}\geq a_n\iff k(1+a_n)(k+a_n)\geq a_n(k+a_n)^2 $$ which factorises easily by taking out the $(k+a_n)$ term, after which the problem essentially becomes one of finding the range of solutions to a cubic inequality, which I assume you know how to do. The details are well-explained in Theo Bendit's answer, of course.


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.