Direct Proof and Proof by Contrapositive

Main idea

A direct proof starts from what you're given and walks forward, one justified step at a time, until it reaches what you want. When the starting point gives you nothing to grab onto, prove the contrapositive instead: it's the same statement, just approached from the other end.

Even and odd

{\htmlData{sym=0}{n}} \text{ even} \iff {\htmlData{sym=0}{n}} = 2{\htmlData{sym=1}{k}}, \qquad {\htmlData{sym=0}{n}} \text{ odd} \iff {\htmlData{sym=0}{n}} = 2{\htmlData{sym=1}{k}} + 1 \qquad ({\htmlData{sym=1}{k}} \in \mathbb{Z})

What the symbols mean

$n$
An integer
The number the statement is about.
$k$
A witness
Another integer that shows n has the right form.

Explanation

A direct proof is simply an argument that starts from what you're told and walks forward, one step at a time, to what you want to show, where every step is something nobody could argue with. It's called "direct" because it goes straight from the hypothesis to the conclusion, with no detours or tricks. This is how you convince someone (or yourself) that a statement is true for every case, not just the ones you tried. The definitions above look formal, but they just say $n = 2k$ (an even number is two times some whole number $k$ ) and $n = 2k + 1$ (an odd number is one more than that). That little trick of naming the $k$ is most of the work in this lesson.

In the logic unit you saw that a theorem usually has the shape "if $P$ , then $Q$ ." Now you get to prove them. To prove "if $P$ , then $Q$ " directly:

Assume $P$ is true.
Unpack the definitions in $P$ into equations you can work with.
Reason, one justified step at a time, until you reach $Q$ .

For example, to prove that the sum of two odd numbers is even, write them as $2a + 1$ and $2b + 1$ . Notice the two different letters: the numbers needn't be the same, so they each get their own. Their sum is $2a + 2b + 2 = 2(a + b + 1)$ , which is $2$ times an integer: even.

Sometimes the hypothesis gives you nothing to work with. "If $n^2$ is even, then $n$ is even" is hard to attack directly, because knowing $n^2 = 2k$ doesn't easily tell you about $n$ . So what can we do? Remember that the contrapositive always means the same thing as the original. Here it's "if $n$ is odd, then $n^2$ is odd," and that one is easy, since you can write $n = 2k + 1$ and square it. Proving the contrapositive proves the original.

A good proof states what is assumed, names every variable, and justifies each step.

A common mistake. It's tempting to think that checking a bunch of examples proves a statement, because if it worked for 1, 3, 5, 7 and 99, surely it always works. It doesn't prove anything: a statement about all integers needs an argument that works for every one of them at once, and there are famous patterns that hold for millions of cases before they break.

See it

This is a direct proof you can see. Take an odd number n = 2k + 1 and draw its square: it splits into four k × (k + 1) rectangles around one unit square, so n² = 4k(k + 1) + 1. Notice that one of k and k + 1 is always even, so each rectangle has an even area and the four together make a multiple of 8. Every odd square is 1 more than a multiple of 8 (for k = 3, 49 = 48 + 1).

Worked examples

Example 1

Prove: if $n$ is odd, then $n^2$ is odd.

1
Assume $n$ is odd, so by definition $n = 2k + 1$ for some integer $k$ .

Example 2

Prove: if $n^2$ is even, then $n$ is even.

1
Knowing $n^2 = 2k$ doesn't lead anywhere directly, so prove the contrapositive: if $n$ is not even (odd), then $n^2$ is not even (odd).

Practice

Type your answer and check it. Solve them all to complete the lesson.

Problem 1+5 XP

If $n = 2k + 1$ , then $n^2 = 2m + 1$ with $m = 2k^2 + 2k$ . What is $m$ when $k = 3$ ?

Problem 2+5 XP

To prove "if $n^2$ is odd, then $n$ is odd" by contrapositive, what do you assume?

Problem 3+5 XP

Prove that the sum of two even integers is even.

Problem 4+5 XP

A hashing routine relies on a fact: the square of any odd number leaves remainder 1 when divided by 8. Check it for 2025: what is the remainder when $2025^2$ is divided by 8?

Problem 5+5 XP

What is the converse of "if $n$ is even, then $n^2$ is even," and is it true?

Challenge problem+25 XP

The hardest one here. Get it, and you've got this lesson.

Find the largest integer that divides $n^3 - n$ for every integer $n$ .

Where it's used

Correctness arguments for algorithms and the machine-checked proofs used to verify chips and operating systems are built from exactly these step-by-step deductions.

Boolean Algebra and Logic Gates Proof by Contradiction