Slow increasing sequence $x_{n+1}=1+\frac{n}{x_n}$

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

-
No, it is not. $x_2 = 1 + 2/1 = 3 > 2 = 1 + 3/3 = x_3$ – Levon Haykazyan Feb 23 '12 at 11:07
@LevonHaykazyan: $x_2 = 1+1/1 = 2$ - there is $n$ and not $n+1$ in the numerator – Ilya Feb 23 '12 at 11:26
@Ilya Sorry, my bad – Levon Haykazyan Feb 23 '12 at 19:15
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. – Assaultous2 May 13 '15 at 8:51

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}.$$
Thanks Prof Aguirre.. can you tell me the motivation behind $x_{n+1} \leq \left(1+\frac{1}{n}\right)x_n$?, that is nice :) – Ajat Adriansyah Feb 23 '12 at 14:32
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}$. – Julián Aguirre Feb 23 '12 at 15:10