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\leqx_{n} \leq2 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 \leq2 or \geq 1 because x_{n+1} and _{n+2} are both either \leq2 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.