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.