• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Strong Induction

  • Thread starter Punkyc7
  • Start date
420
0
Let the number x[itex]_{n}[/itex] be defined as follows x[itex]_{1}[/itex] = 1 and x[itex]_{2}[/itex] =2 and x[itex]_{n+2}[/itex]=[itex]\frac{1}{2}[/itex](x[itex]_{n+1}[/itex] +[itex]_{n}[/itex]) for all n [itex]\epsilon[/itex] N. Use the principle of strong induction to show that 1[itex]\leq[/itex]x[itex]_{n}[/itex] [itex]\leq[/itex]2 for all n [itex]\epsilon[/itex] 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[itex]_{n+3}[/itex]=[itex]\frac{1}{2}[/itex](x[itex]_{n+2}[/itex] +x[itex]_{n+1}[/itex]). Since

x[itex]_{n+3}[/itex]=[itex]\frac{1}{2}[/itex](x[itex]_{n+2}[/itex] +x[itex]_{n+1}[/itex])= [itex]\frac{1}{2}[/itex](x[itex]_{n+1}[/itex] +x[itex]_{n}[/itex]). Since its true for [itex]\frac{1}{2}[/itex](x[itex]_{n+1}[/itex] +x[itex]_{n}[/itex]) by our induction hypothesis its true for for n+1.
 
Last edited:
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

[tex]x_{n+3} = \frac{1}{2} (x_{n+2} + x_{n+1})[/tex]

which is correct, but your next equality doesn't follow. Based on your inductive hypothesis, however, what do you know about [itex]x_{n+2}[/itex] and [itex]x_{n+1}[/itex]?
 
420
0
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[itex]_{n+3}[/itex] is either [itex]\leq[/itex]2 or [itex]\geq[/itex] 1 because x[itex]_{n+1}[/itex] and [itex]_{n+2}[/itex] are both either [itex]\leq[/itex]2 or [itex]\geq[/itex] 1

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

SammyS

Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,095
881
You seem to be uncertain of precisely what the proposition (or property) is here.
 
No I think he's got it, but he's having some trouble with formatting properly with tex. He's setting [itex]P(n) = [1 \le x_{n+2} \le 2][/itex], 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 [itex]x_{k}[/itex] for all [itex]k \in {1,2,...,n}[/itex].
By definition,
[tex]x_{n+1} = \frac{1}{2} (x_{n} + x_{n-1})[/tex]
and by our hypothesis

[itex]1 \le x_{n} \le 2[/itex] and [itex]1 \le x_{n-1} \le 2[/itex].

I don't want to totally give it away, so write your own continuation first before reading the rest.
[tex]2 \le x_n + x_{n-1} \le 4[/tex]
[tex]1 \le \frac{1}{2} (x_n + x_{n-1}) \le 2[/tex]
[tex]1 \le x_{n+1} \le 2[/tex]
 
420
0
I understand what you did for the most part but how did you know to do x[itex]_{n+1}[/itex] instead of what was x[itex]_{n+2}[/itex] that was given?
 
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 [itex]1 \le x_{k} \le 2[/itex].

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.
 
420
0
so x[itex]_{n+2}[/itex] is there just to confuse us
 
No, it shouldn't confuse you... I think you should think about what both statements mean (not just what the algebraic notation looks like).

[tex]x_{n+2} = \frac {1}{2}(x_{n+1} + x_{n}) \qquad \forall n \in {1, 2, ...}[/tex]

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.
 

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top