1. Not finding help here? Sign up for a free 30min 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!

Translating a strong induction to test cases if valid or invalid? answers given

  1. Nov 15, 2006 #1
    Hello everyone.

    I"m trying to break down this problem, the answers are given I just want to make sure I'm understanding it right.

    [​IMG]



    OKay here is my reasoning:

    For the first one, which is invalid.

    they say For n >= 3, assume that P(k) is true for all k >=1 such that k <= n. So k <= 3. We will porve that P(n) is true.
    Assumes P(1), P(2), P(3)
    Is it invalid because P(3) wasn't proven true in the beginning, it ony said:
    P(1) and P(2) are true.


    For the 2nd, which is valid.
    For n >= 2, assume that P(k) is true for all k >= 1 such that k < = n, so
    k <= 2. We will prove that P(n+1) is true.
    Proves: P(1), P(2), and P(2+1) = P(3).
    Assumes P(1) and P(2) are true, which it is, from the first pargraph, so that must be valid.

    For the 3rd, which is also valid:
    For n > 3, assume that P(k-1) is true for all k >= 2 such that k < n. We will prove that P(n-1) is true.
    Proves P(1),P(2), P(3), and P(4)
    assumes P(1), P(2).

    So k = 2, 3, 4
    n > 4, so n = 4
    assumes P(k-1) so we have:
    assumes P(3), P(2), P(1)

    But what confusees me is, if its assuming P(1),P(2), and P(3), and P(4),
    the beginning paragraph didn't say P(3) and P(4) were true, so why is this valid?




    For the 4th one, which is invalid:
    FOr n > 3, assume that P(k) is true for all k >= 1 such that k < n. We will prove that P(n) is true.
    Prove: P(n), and n > 3, so it will prove P(4), P(5), P(6)
    assume P(k) is true for all k >=1 such that k < n.
    So, k = 1, 2, 3
    assume P(1), P(2), P(3),
    we are assuming P(3) but there is no proving of P(3) becuase the proving starts at P(4) is that why this is invalid?


    For the 5th one, which is invalid

    For n >=3, assume that P(K) is true for all k >= 0 such that k < n. We will prove that P(n) is true.

    n = 3, 4, 5...
    k = 0, 1, 2, 3, 4, 5...

    assumes: P(0),P(1),P(2),P(3)
    proves: P(3), P(4), P(5)

    is this invalid because again ur assuming P(3), when P(3) wasn't proven to be true in the beginning paragraph?


    For number 6, which is valid:
    For n >= 1, assume that P(k) is true for all k >=1 such that k <= 2n. We will prove that P(2n+1) and P(2n+2) are true.


    Proves n = 1: P(3) and P(4)
    assumes n = 1: P(1), P(2)

    Proes n = 2: P(5) and P(6)
    assumes n = 2: P(1),P(2),:(3),P(4)

    I see this is convering all the spots but for n = 1, why does it stop at P(2), and for n = 2, why does it stop at P(4)?


    Thanks!
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?



Similar Discussions: Translating a strong induction to test cases if valid or invalid? answers given
  1. Answer need checking! (Replies: 0)

Loading...