1. ## Recurrence relation

A sequence of real numbers $\displaystyle {U_n}$ satisfies the recurrence relation

$\displaystyle U_{n+1}=\frac{1}{2}U_n+1$ for all positive integer $\displaystyle n$.

a) Given that $\displaystyle {U_n}$ converges to $\displaystyle l$, find the value of $\displaystyle l$

b) If $\displaystyle U_n < l$, show that $\displaystyle U_n<U_{n+1}<l$

I was able to find that $\displaystyle l=2$ for part a.

For (b), what I have done is:

$\displaystyle 2U_{n+1}-2=U_n$

$\displaystyle 2U_{n+1}-2<2$

$\displaystyle U_{n+1}<0$

How do I continue? Or am I going in the wrong direction?

2. ## Re: Recurrence relation

Originally Posted by Punch
$\displaystyle 2U_{n+1}-2<2$

$\displaystyle U_{n+1}<0$
The last line should be $\displaystyle 2U_{n+1}<4$.

3. ## Re: Recurrence relation

The recurrence relation can be written as...

$\displaystyle \Delta_{n}=u_{n+1}-u_{n}= 1-\frac{u_{n}}{2}= f(u_{n})$ (1)

As explained in...

http://www.mathhelpforum.com/math-he...-i-188482.html

... has only one 'atrractive fixed point' in $\displaystyle x=2$ and because for all x is $\displaystyle |f(x)|\le |x_{0}-x|$ all initial value $\displaystyle u_{0}$ will produce a sequence monotonically convergent to 2...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

4. ## Re: Recurrence relation

Originally Posted by emakarov
The last line should be $\displaystyle 2U_{n+1}<4$.
Then $\displaystyle U_{n+1}<2$, how do I continue to show that $\displaystyle U_n<U_{n+1}<l$?

5. ## Re: Recurrence relation

$\displaystyle U_n<2\implies U_n+U_n<2+U_n\implies U_n<1+U_n/2=U_{n+1}$

6. ## Re: Recurrence relation

Originally Posted by emakarov
$\displaystyle U_n<2\implies U_n+U_n<2+U_n\implies U_n<1+U_n/2=U_{n+1}$
Thank you, how did you think of that?

7. ## Re: Recurrence relation

Good question. I just solved the inequality $\displaystyle U_n<U_n/2+1$ and found that it is equivalent to $\displaystyle U_n<2$, so in particular the latter implies the former.

I have a feeling that solving two inequalities to prove $\displaystyle U_{n+1}<2$ and $\displaystyle U_n<U_{n+1}$ is repeating some work, but to understand it better I probably need to read chisigma's tutorial...