1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Strong Induction

  1. Sep 22, 2011 #1
    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?

    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: Sep 22, 2011
  2. jcsd
  3. Sep 22, 2011 #2
    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]?
  4. Sep 22, 2011 #3
    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
  5. Sep 22, 2011 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    You seem to be uncertain of precisely what the proposition (or property) is here.
  6. Sep 22, 2011 #5
    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]
  7. Sep 22, 2011 #6
    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?
  8. Sep 23, 2011 #7
    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.
  9. Sep 23, 2011 #8
    so x[itex]_{n+2}[/itex] is there just to confuse us
  10. Sep 24, 2011 #9
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook