(Solved): The contrapositive of a conditional statement is formed by negating both terms and reversing the d ...

The contrapositive of a conditional statement is formed by negating both terms and reversing the direction of inference. For example, if \( S \) is the statement "if I live in Boston then I live in Massachusetts", then the contrapositive of \( S \) is "if I don't live in Massachusetts, then I don't live in Boston". Any statement and its contrapositive are logically equivalent. Thus, if \( P \rightarrow Q \) is TRUE, then the contrapositive \( \neg Q \rightarrow \neg P \) is TRUE. And if \( P \rightarrow Q \) is FALSE, then \( \neg Q \rightarrow \neg P \) is FALSE. To prove the statement "if \( \mathrm{P} \), then Q", sometimes it is easier to prove the contrapositive statement "if not Q, then not \( \mathrm{P} \) ". And that is what you will do in this question. Using Proof by Contrapositive, prove each of the following statements. (a) Let \( n \) be a positive integer. If \( n^{2}+2 n+5 \) is an even number, then \( n \) is odd. (b) If there are 15 students in Discrete Structures, then at least three students were born on the same day of the week. (c) Prove the Generalized Pigeonhole Principle: if \( n k+1 \) pigeons fly into \( n \) pigeonholes, then at least one pigeonhole contains at least \( k+1 \) pigeons.