Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is it true for all n, Natural number?

  1. Mar 20, 2007 #1
    Hello all,

    Another quick question for the number theory gurus here:

    Let P(n) predicate, n Natural number. Suppose that P(n) satisfies that P(1) is true, and if k in N, P(k) is true, then P(k+2) is true. Is P(n) true for ALL n in N? Why?

    Thanks in advace guys!

  2. jcsd
  3. Mar 20, 2007 #2
    The principal of induction sezs that if its true for N, it's true for N+1, and we begin with a basis of 1 or zero, usually. This means once we have proved it true for 5, we can deduce that it is true for 6, and if true for 6, well.....

    So if its true for N+2 when its true for N....you can take it from there.
  4. Mar 20, 2007 #3
    I would say no. P(1) -> P(3) -> P(5) and so on. In other words, P(n) is true for all odd n.
  5. Mar 20, 2007 #4
    Interesting e(hoOn3... I was thinking something like that, other opinions?
  6. Mar 20, 2007 #5
    No. The answer is no.

    Well, depending on how N was constructed. You could construct N differently and then be able to say yes.
    Last edited: Mar 20, 2007
  7. Mar 20, 2007 #6
    If you say no, why no? N = Natural numbers,

    thanks for your reply!
  8. Mar 20, 2007 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    just construct a counter example. it is trivial. P(1), and hence P(3), P(5),.. are true, but P(2) etc can be completely arbitrary. Are you telling me you can't think of an obvious statement that is true for (something to do with) odd numbers but is false for even numbers?
  9. Mar 20, 2007 #8
    Glad there is edit here... its late, im not thinking straight.
    I didnt catch the counter example, sorry.
    Last edited: Mar 20, 2007
  10. Mar 20, 2007 #9
    I am not following you at all.

    Matt Grime pretty much gave you a counter example.
  11. Mar 20, 2007 #10
    Wrong. Matt didn't give a counter-example per say. He said that one may construct a statement P(n) that is true for odd n but false for even n.
  12. Mar 21, 2007 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I think I pretty much did give a counter example. At least if you take second to think what the words ODD and EVEN are doing there. Isn't there a really obvious property that ODD numbers have that EVEN ones don't? And can you show it by induction? Yes. It is a vacuous proof, but still a proof by induction nonetheless.
    Last edited: Mar 21, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook