Question

Discrete Math: Consider the following theorem: If p is even then p+1 is odd.

Can someone explain or show how do to these examples?

Write a proof by contraposition. (Assume ~q, show ~p)

Write a direct proof (Assume p, show ~p)

Write a proof by mathematical induction. (Show basis step, assume k^th step, show k+1 step)

Answer 1

Given: p -> q

p: p is even

q: p+1 is odd

Write a proof by contraposition. (Assume ~q, show ~p)

~q: p+1 is even

~p: p is odd

Proof

p + 1 = even

p + odd = even

odd + odd = even

So, p is odd

Write a direct proof (Assume p, show ~p)

p is even = 2a

p+1 = 2a + 1 = even + 1 = even + odd = odd

Write a proof by mathematical induction. (Show basis step, assume k^th step, show k+1 step)

Base case: p = 2

p + 1 = 2 + 1 = 3 = odd

Inductive Hypothesis: when p = 2k, assume that it works

p + 1 is odd

Inductive Step: Proving for p = 2k + 2

When p = 2k, p+1 is odd

Add 2 to above (p + 1) + 2 = odd + even = odd

HENCE PROVED