# Strong Induction

1. Sep 22, 2011

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

Last edited: Sep 22, 2011
2. Sep 22, 2011

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

3. Sep 22, 2011

### 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

4. Sep 22, 2011

### SammyS

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

5. Sep 22, 2011

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

6. Sep 22, 2011

### 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?

7. Sep 23, 2011

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

8. Sep 23, 2011

### Punkyc7

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

9. Sep 24, 2011

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