Strong Induction: Show 1\leq x_{n} \leq2 for all n \epsilon N

[Punkyc7]

Let the number x$_{n}$ be defined as follows x$_{1}$ = 1 and x$_{2}$ =2 and x$_{n+2}$=$\frac{1}{2}$(x$_{n+1}$ +$_{n}$) for all n $\epsilon$ N. Use the principle of strong induction to show that 1$\leq$x$_{n}$ $\leq$2 for all n $\epsilon$ N

I have never done strong induction before so is this right?
Pf/

so P(1) is obvious

Assume true for P(1)...P(n). WTS true for P(n+1).

So P(n+1)= x$_{n+3}$=$\frac{1}{2}$(x$_{n+2}$ +x$_{n+1}$). Since

x$_{n+3}$=$\frac{1}{2}$(x$_{n+2}$ +x$_{n+1}$)= $\frac{1}{2}$(x$_{n+1}$ +x$_{n}$). Since its true for $\frac{1}{2}$(x$_{n+1}$ +x$_{n}$) by our induction hypothesis its true for for n+1.

 

[process91]

The text formatting at the beginning is all sorts of messed up, but I think I get the problem.

There's still a problem with your inductive step. You have

$$x_{n+3} = \frac{1}{2} (x_{n+2} + x_{n+1})$$

which is correct, but your next equality doesn't follow. Based on your inductive hypothesis, however, what do you know about $x_{n+2}$ and $x_{n+1}$?

 

[Punkyc7]

Sorry about the confusion I got lost with all the formatting

they are at least 1 and at most 2.

So would you say by our hypothesis x$_{n+3}$ is either $\leq$2 or $\geq$ 1 because x$_{n+1}$ and $_{n+2}$ are both either $\leq$2 or $\geq$ 1

and at most (2+2)/2 =2 and at least 2/2=1

 

[SammyS]

You seem to be uncertain of precisely what the proposition (or property) is here.

 

[process91]

No I think he's got it, but he's having some trouble with formatting properly with tex. He's setting $P(n) = [1 \le x_{n+2} \le 2]$, which is a little awkward for me but it works.

I like to do inequality things pretty formally, so here's how I would do it:

Assume it holds for $x_{k}$ for all $k \in {1,2,...,n}$.
By definition,
$$x_{n+1} = \frac{1}{2} (x_{n} + x_{n-1})$$
and by our hypothesis

$1 \le x_{n} \le 2$ and $1 \le x_{n-1} \le 2$.

I don't want to totally give it away, so write your own continuation first before reading the rest.

Spoiler

$$2 \le x_n + x_{n-1} \le 4$$
$$1 \le \frac{1}{2} (x_n + x_{n-1}) \le 2$$
$$1 \le x_{n+1} \le 2$$

 

[Punkyc7]

I understand what you did for the most part but how did you know to do x$_{n+1}$ instead of what was x$_{n+2}$ that was given?

 

[process91]

When you're making a statement involving n in your induction, it is not explicitly the same n as from earlier in the recursive definition. This statement, which starts the introduction:

Assume, for all k in {1, 2, ... ,n}, for some n, that we have that $1 \le x_{k} \le 2$.

says that it holds for some arbitrary n. This "resets" the use of n from earlier in the recursive definition. If you are more comfortable, you could swtich one of them to "m" instead.

 

[Punkyc7]

so x$_{n+2}$ is there just to confuse us

 

[process91]

No, it shouldn't confuse you... I think you should think about what both statements mean (not just what the algebraic notation looks like).

$$x_{n+2} = \frac {1}{2}(x_{n+1} + x_{n}) \qquad \forall n \in {1, 2, ...}$$

This means that, after the first two, each value of x is equal to half the sum of two before it. That's it. n just serves as a placeholder so that we can write that statement algebraically.

When working with any inductive statement, we want something to be true "for some arbitrary n", and then we want to show that the fact that it is true for this n necessarily implies that it is true for n+1.

In the context of our proof, this means that we need to show that the knowledge that all x in the sequence before some arbitrary place are greater than / equal to 1 and less than / equal to 2 necessarily implies that the next x in the sequence is also greater than / equal to 1 and less than / equal to 2. n just serves as a placeholder so that we can reference this place in the sequence again later.