Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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