Understanding Mathematical Induction: Proving Implications and When to Use It

[anonymity]

Hello,

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 $\Sigma$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 =|

 

[micromass]

The implication in this case is

$$P(k)~\Rightarrow~P(k+1)$$

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...

 

[anonymity]

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)

=|

 

[micromass]

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)

=|

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).

 

[anonymity]

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 a lot 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 don't see how it is LOGICALLY justified

 

[micromass]

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"

Well, if you want to drag truth tables into this, then we can:

$$\begin{array}{ccc} P(k) & P(k+1) & P(k)\Rightarrow P(k+1)\\ F & F & T\\ F & T & T\\ T & F & F\\ T & T & T \end{array}$$

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.

 

[anonymity]

Okay that makes an incredible amount of sense...

thanks ><