Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
No, it is not. $x_2 = 1 + 2/1 = 3 > 2 = 1 + 3/3 = x_3$ –  Levon Haykazyan Feb 23 '12 at 11:07
1  
@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

1 Answer 1

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|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
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}$. –  Julián Aguirre Feb 23 '12 at 15:10

Your Answer

 
discard

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.