Is the Sequence Defined by x_n+1 = x_n/2 + 1 Bounded Above by 2?

[cragar]

Homework Statement

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

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.

 

[Fredrik]

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

 

[dirk_mec1]

You can show it by using induction.

 

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

 

[Curious3141]

Homework Statement

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

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.

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?

 

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

 

[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

 

[Fredrik]

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

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

 

[cragar]

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