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: Mathematical Induction

  1. Sep 9, 2011 #1

    I have a question about inductive reasoning...

    Earlier this week my intro proofs class went over the logical structure of induction, and an example.

    The example was a proof of [itex]\Sigma[/itex]i = n*(n + 1)/2

    My main issue is the assumption that "p(k)" is true. What if it's not? I asked this in class, and my professor said it didnt matter because we are proving an implication (this made perfect sense). However, this leads to the next issue...how do you know that you're proving an implication? How can you tell when you're dealing with an implication and when not? What's the implication for this example...?

    edit: it's not that I don't understand how to use it, I do. I just wrote two assigned proofs using induction. I just want to understand why it works and when it works =|
    Last edited: Sep 9, 2011
  2. jcsd
  3. Sep 9, 2011 #2
    The implication in this case is


    That is: IF P(k) holds, THEN P(k+1) holds.

    You know that it's an implication because that's what induction is about. You don't prove P(n) directly, but you prove it through the implication. So if you're using induction, then you're proving an implication...
  4. Sep 9, 2011 #3
    but in the actual proof, how do you know that P(k) "IMPLIES" p(k + 1), aside from the fact that (hopefully) the answer via assumption and the given formula coincide (in the basic summation example)

  5. Sep 9, 2011 #4
    You know that P(k) IMPLIES P(k+1) because that is what you prove.

    You start by assuming P(k) true, and you prove P(k+1) to be true. So you have proven that P(k) IMPLIES P(k+1).
  6. Sep 9, 2011 #5
    It's just sort of weird thinking of the implication out of its dry logical context... I don't see how that proves the implication in the logical form (ie if i drew it out on a truth table).

    edit: after reading my post, I think a good replacement for "dry" would be "un-applied"

    edit 2.0: I mean, if I don't think about it, it makes alot of sense. You start with p(k), and use that to find p(k + 1)... so there is definitely a connection (it would seem to imply). But I certainly dont see how it is LOGICALLY justified
    Last edited: Sep 9, 2011
  7. Sep 9, 2011 #6
    Well, if you want to drag truth tables into this, then we can:

    P(k) & P(k+1) & P(k)\Rightarrow P(k+1)\\
    F & F & T\\
    F & T & T\\
    T & F & F\\
    T & T & T

    We want to prove that the implication is true. But from the truth table, we see that the only way that the implication can ever be false is if P(k) is T and if P(k+1) is F. So we assume P(k) is T, and we prove that P(k+1) is also T. This proves that the third row of the truth table cannot occur. So the implication is true.
  8. Sep 9, 2011 #7
    Okay that makes an incredible amount of sense...

    thanks ><
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook