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: Using second Principle of Mathematical Induction Proof

  1. Sep 1, 2012 #1
    1. The problem statement, all variables and given/known data
    Let F: N->N be defined by f(1)=1 and f(2)=2 and f(n+2)=1/2(f(n+1)+f(n))

    Use Theorem 1.3 to prove that 1<=f(n)<=2 for all n in N

    2. Relevant equations

    For each n in N let P(n) be a statement about the positive integer n. If a) P(1) is true, and b) for k>1, P(k) is true whenever P(j) is true for all positive integers j<k, then P(n) is true for all n in N.

    3. The attempt at a solution
    I honestly don't really know how to even start this one. I have a hard time understanding what the theorem is even saying, so I don't know how to apply it.
  2. jcsd
  3. Sep 1, 2012 #2


    User Avatar
    Science Advisor

    Let' s see. Let's first parse the statement:

    P(n) is the statement 1<=f(n)<=2 , so, e.g., P(3) is the statement 1<=P(3)<=2 ,


    You're asked to show that if for any general number k>1 , it follows that

    1<= f(n) <= 2 for all n in {1,2,...,k-1} , i.e., for any pos. integer you select,

    you have that (and your job is to show that for any k you do have this) :

    1) 1<=f(1)<=2
    2) 1<=f(1)<=2
    k-1) 1<= f(k-1)<=2

    Then, you can conclude that ,for any number , say',s', that :

    1<=f(s) <=2 .
  4. Sep 1, 2012 #3
    I'm having trouble with how I am supposed to prove it without knowing the f(n) that is being used. Is there some part of the theorem that I'm missing that would help me with that aspect of this proof?
  5. Sep 1, 2012 #4


    User Avatar
    Science Advisor

    True that you don't know f(n), but you know some properties of it (recursively-

    defined),from the first line in your original post.
  6. Sep 1, 2012 #5


    User Avatar
    Science Advisor

    Sorry if I was too abstruse.

    Try maybe showing it for some specific numbers n, and see how to generalize it

    for any j.
  7. Sep 1, 2012 #6


    User Avatar
    Science Advisor

    So f(1)= 1 which is between 1 and 2 (inclusive). f(2)= 2 which is between 1 and 2 (inclusive). f(3)= f(1+ 2)= (1/2)(f(2)+ f(1))= (1/2)(2+1)= 3/2 which is between 1 and 2.
    f(4)= (1/2)(f(3)+ f(2))= (1/2)(3/2+ 2)= (1/2)(7/2)= 7/4= 1 and 3/4 which is between 1 and 2.
    f(5)= (1/2)(f(4)+ f(3))= (1/2) (7/4+ 3/2)= (1/2)(13/4)= 13/8= 1 and 5/8 which is between 1 and 2.

    That's what it is saying!

  8. Sep 2, 2012 #7
    So in the case, what would I consider k and j? Would i let n=k to finish this proof?
  9. Sep 2, 2012 #8


    User Avatar
    Science Advisor

    What do you mean by that's what it is saying? Are you referring to my post?
  10. Sep 2, 2012 #9


    User Avatar
    Science Advisor

  11. Sep 2, 2012 #10
    I'm sorry, but I still don't really understand what it is saying. I've read it several times and really am having a hard time. We didn't go over any examples of anything like this in class.
  12. Sep 4, 2012 #11


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The problem defines a sequence f(1), f(2),... and is asking you to prove that all the terms of that sequence is in the interval [1,2]. So you need to prove the infinitely many statements:
    f(1) is in [1,2]
    f(2) is in [1,2]
    The theorem that you included under "relevant equations" is telling you that you can do that by proving only two statements. This saves you an infinite amount of time. That's the whole point of induction. If we call the statements above P(1), P(2), and so on, the two statements you have to prove are:

    P(1) is true.
    For all positive integers n, if P(k) is true for all integers k<n, then P(n) is true.

    I'm sure you will have no problems with the first of these statements. The proof of the second statement would typically start with "Let n be an arbitrary positive integer such that P(k) is true for all positive integers k<n." To complete the proof, you just need to show that P(n) is true.
    Last edited: Sep 4, 2012
  13. Sep 5, 2012 #12
    Thank you. That makes a lot more sense now.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook