Direct proof, contrapositive and contradiction

Most theorems have the shape "if \( P \) then \( Q \)". A direct proof assumes \( P \) and reasons forward, one justified step at a time, until it reaches \( Q \). To show that the sum of two odd integers is even, write them as \( 2a + 1 \) and \( 2b + 1 \): their sum is \( 2(a + b + 1) \), which is even. Unpacking definitions into algebra like this is where most direct proofs start.

A proof by contrapositive proves \( \lnot Q \Rightarrow \lnot P \) instead. The two statements are logically equivalent, as the example's truth table shows, so proving one proves the other. It helps when \( \lnot Q \) gives you something concrete to work with. To prove "if \( n^2 \) is even then \( n \) is even", the direct route starts from \( n^2 = 2k \) and gets stuck taking a square root. The contrapositive starts from \( n = 2k + 1 \) and computes \( n^2 = 2(2k^2 + 2k) + 1 \), which is odd. Do not confuse the contrapositive with the converse \( Q \Rightarrow P \), which is a different statement and may be false.

A proof by contradiction assumes the statement is false and derives something impossible. To show \( \sqrt 2 \) is irrational, suppose \( \sqrt 2 = a/b \) in lowest terms. Then \( a^2 = 2b^2 \), so \( a^2 \) is even, so \( a \) is even (the contrapositive result above), say \( a = 2c \). Then \( 4c^2 = 2b^2 \) gives \( b^2 = 2c^2 \), so \( b \) is even too, and \( a/b \) was not in lowest terms after all. Euclid's proof that there are infinitely many primes has the same shape: given any finite list of primes, their product plus one has a prime factor that is not on the list.

Picture it: a direct proof is a road from \( P \) to \( Q \). The contrapositive is the same road driven backwards from "not \( Q \)" to "not \( P \)". A contradiction proof is a map of every road leaving "not the theorem", showing that each one ends at a cliff.

Think it: try direct proof first. Use the contrapositive when the conclusion is a negative or an "is not" statement, or when its negation is easier to write down. Use contradiction for statements like irrationality or infinitude, whose natural negation hands you a finite list or a fraction to work with. And state clearly at the start which method you are using, so a reader knows what is being assumed.