2
$\begingroup$

Define the sequence $x_1=1$ and for all $n\geq 1$ $x_{n+1}=1+\frac{n}{x_n}$

Does it follow that $x_n$ is an increasing sequence?

This is not a homework, I found the exercise to prove $\sqrt{n}\leq x_n \leq \sqrt{n}+1$ on a textbook. By curiosity, I was playing around with my computer to see the behavior of this sequence, which seems to increase very slow.

Further more, the condition $x_{n+1}\geq x_{n}$ would imply the stronger relation than given in the book, which is $x_n \leq \frac{1+\sqrt{1+4n}}{2}$.

Using this, one can show that for $k>2$ $\lfloor x_n \rfloor = k$ is satisfied for exactly $2k$ times values of $n$.

  • 0
    A comment regarding on how you said the sequence increases very slowly: you can prove that the sequence grows as the square root of n.2015-05-13

1 Answers 1

3

We show by induction that $ x_n\le x_{n+1}\le\Bigl(1+\frac1n\Bigr)x_n\qquad\forall n\ge1. $ It clearly holds for $n=1$. Assuming it holds for $n\ge1$, we must show $ x_{n+1}\le x_{n+2}\le\Bigl(1+\frac1{n+1}\Bigr)x_{n+1}, $ which is equivalent to $ 1+\frac{n}{x_n}\le1+\frac{n+1}{x_{n+1}}\le\Bigl(1+\frac1{n+1}\Bigr)x_{n+1}.\tag1 $ From the induction hypothesis $ \frac{n+1}{x_{n+1}}\ge\frac{n+1}{(1+1/n)x_n}=\frac{n}{x_n}, $ proving the first inequality in (1). Now $ 1+\frac{n+1}{x_{n+1}}=1+\frac{(n+1)x_n}{n+x_n}. $ Since $x_n>1$ and $x_n\le x_{n+1}$ by induction hypothesis, $ 1+\frac{(n+1)x_n}{n+x_n}\le1+x_{n+1}<\Bigl(1+\frac1{n+1}\Bigr)x_{n+1}. $

This proves the second inequality in (1).

  • 1
    Sometimes, to make an induction argument work, you must impose an hypothesis stronger than what in principle you want to prove. This is one of those cases. That something like this was needed is suggested by the the fact that in $x_{n+1}=1+n/x_n$, the $x_n$ is in the denominator. To get $x_{n+1}\le\text{ something}$ you need $x_n\ge\text{ something}$.2012-02-23