# Homework Help: Proof about a sequence.

1. Jan 23, 2012

### cragar

1. The problem statement, all variables and given/known data
Show that the sequence $(x_1,x_2,x_3,....)$
defined by; Let $x_1=1$ for each $n \in \mathbb{N}$
$x_{n+1}= \frac{x_n}{2}+1$
$x_2=\frac{3}{2}$
Show that this sequence is bounded above by 2; that is prove that $x_n\leq2$ for all $n\in\mathbb{N}$
3. The attempt at a solution
This seems weird to me because it doesn't seem like it would be bounded above by 2, I could find some x that was bigger that 2. unless I don't understand the question.

2. Jan 23, 2012

### Fredrik

Staff Emeritus
The statement that it's bounded from above by 2 means precisely that all terms in the sequence are ≤2. If you can find a term that's >2, then you have proved that it's not bounded from above by 2.

I suggest that you try to determine what the consequences would be if there's an integer N≥2 such that $x_N>2$.

Last edited: Jan 23, 2012
3. Jan 23, 2012

### dirk_mec1

You can show it by using induction.

4. Jan 23, 2012

### cragar

okay I should have looked at it closer, it does look like it will stay below 2. so should I try to manipulate it into a form that will work and then use induction. thanks for the replies by the way.

5. Jan 23, 2012

### Curious3141

You can arrive at a nice contradiction by "going backward".

Suppose there was some k (k > 1) such that $x_k = 2 + \epsilon$, where $\epsilon \geq 0$.

Calculate $x_{k-1}, x_{k-2}$ (observe that they're increasing as you're going backward) and derive the general term $x_{k-r}$. Prove this by induction (really easy).

Now set $r = k-1$. What do you get?

6. Jan 23, 2012

### Curious3141

Even more easily, using the same approach I detailed you can prove the "forward" case by induction. If you show that $x_k < 2 \Rightarrow x_{k+1} < 2$, you're done.

7. Jan 23, 2012

### cragar

can I do this. $x_1=1$ so 1 is less than 2 so the base case is confirmed.
now $2(x_{n+1}-1)=x_n\leq2$
then say that $2(x_{n+1}-1)\leq2$
the divide both sides by 2 and then add the 1 so now we have
$x_{n+1}\leq2$
so does this work, kinda seems recursive

8. Jan 23, 2012

### Fredrik

Staff Emeritus
This is a good way to do it. Since you have found one solution, I don't mind telling you another. This is what I had in mind before:

For all n such that $x_n>2$, we have $\frac{x_{n-1}}{2}+1<2$, which implies that $x_{n-1}>2$. So if one term is >2, every one that came before it is too. This contradicts $x_1\leq 2$.

9. Jan 23, 2012

### cragar

interesting idea fredrik, thanks to everyone who made a post.