Proof Strategies-I

Welcome, everyone! Today, we're diving into proof strategies which are critical for understanding discrete mathematics. Why do you think we need different proof strategies?

Because some statements are too complex to prove directly, right?

Exactly! Different situations require different approaches. Let’s start with the direct proof method. Can someone summarize what a direct proof is?

It starts with assuming the premise is true and then showing that the conclusion must be true too.

That's right! Remember, in direct proofs, we usually work with universally quantified implications. A good mnemonic to remember this process is 'P leads to Q'—think of it as a direct path to the truth. Now, who can give an example of a direct proof?

Maybe proving that if n is an odd integer, then n² is also odd?

Perfect! Let’s unwrap that example. Assuming n is odd, we represent it as 'n = 2k + 1'. Can anyone compute n² from there?

If we square that, we get (2k + 1)² = 4k² + 4k + 1, which is of the form 2m + 1, meaning n² is odd!

Excellent! So, the direct proof method confirms that our assumption holds true for all odd integers.

Now, let’s move to indirect proofs, starting with proof by contrapositive. Does anyone know what that entails?

Is it about proving 'if not Q, then not P' instead of directly proving 'if P, then Q'?

Exactly! This is useful when the direct approach is too complicated. Let’s analyze our favorite example: proving 'if 3n + 2 is odd, then n is odd'. How can we formulate this in contrapositive?

The contrapositive would be: 'If n is even, then 3n + 2 must also be even.'

Exactly correct! Now, if n is even, how do we express n?

We can write it as n = 2k for some integer k.

And what does that lead to for 3n + 2?

Substituting gives us 3(2k) + 2 = 6k + 2, which is even!

Well done! This confirms the contrapositive and shows that our original statement is indeed true.

Next up is vacuous proof. Who can explain the essence of this proof type?

It shows that an implication is true if the premise is false, right?

Correct! For an implication of the form 'if P, then Q', if P is false, the whole statement is true. Let’s test this with a simple example. What if we check P(0) where P(n) states 'if n > 1, then n² > n'?

For P(0), since 0 is not greater than 1, the premise is false. So, the whole statement is true regardless of n² > n.

Well articulated! This demonstrates that even if Q happens to be false, P(0) is still vacuously true.

Lastly, let’s tackle proof by contradiction. Can anyone give a brief description?

We assume P is true and Q is false, and if this leads to a contradiction, then the original implication must be true?

Exactly! Let’s take our earlier example about 'if 3n + 2 is odd, then n is odd.' What happens if we assume P is true and Q is false?

That means we believe 3n + 2 is odd, and n is not odd, which means n is even.

Good! If we say n is even, what form does n take?

n can be expressed as 2k for some integer k.

Now, what does that yield for 3n + 2?

That gives us 3(2k) + 2 which simplifies to 6k + 2, showing it’s even!

Excellent! This contradiction illustrates that our assumption about n being even must be incorrect, proving that if 3n + 2 is odd, then n is indeed odd.