The Lumenary · Grades 9–12

Proof: direct, contrapositive, contradiction and induction

Name: ______________________

Date: ______________________

You will learn to

Write direct proofs and proofs by cases about integers
Prove a statement through its contrapositive, such as "if $n^2$ is even then $n$ is even"
Prove a statement by contradiction, such as Euclid's theorem that there are infinitely many primes
Prove statements about all natural numbers by ordinary and by strong induction, and explain why induction, strong induction and the well-ordering principle are equivalent
Find gaps, circular reasoning and unstated assumptions in a proposed proof

1.
You want to prove “if $n^2$ is odd, then $n$ is odd” by contrapositive. What do you assume at the start?
- A. $n$ is even
- B. $n^2$ is odd
- C. $n$ is odd
- D. $n^2$ is even
2.
Use Gauss's formula to compute $1 + 2 + 3 + \dots + 200$ .
3.
In the “all horses are the same colour” induction, where exactly does the argument break down?
- A.The base case: one horse need not have one colour.
- B.The inductive step from $n = 1$ to $n = 2$ : the two groups of size $1$ do not overlap.
- C.The inductive step only fails for large $n$ .
- D.Nothing is wrong; the induction principle itself is the problem.
4.
Let $N = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031$ . What does Euclid's argument guarantee about $N$ ?
- A.Every prime factor of $N$ is different from $2, 3, 5, 7, 11, 13$ .
- B. $N$ is prime.
- C. $N$ 's smallest prime factor is the next prime, $17$ .
- D.Nothing: the argument only works when the list contains every prime.
5.
With an unlimited supply of stamps worth $3$ and $7$ , what is the largest amount that cannot be made exactly?
6.
Which of these statements is proved most naturally by strong induction rather than ordinary induction?
- A.Every natural number $n \ge 2$ is a product of primes.
- B. $0 + 1 + \dots + n = n(n+1)/2$ .
- C. $1 + 3 + \dots + (2n - 1) = n^2$ .
- D. $2^n \ge n + 1$ for every natural number $n$ .
7.
“Let $a = b$ . Then $a^2 = ab$ , so $a^2 - b^2 = ab - b^2$ , so $(a+b)(a-b) = b(a-b)$ , so $a + b = b$ , so $2b = b$ , so $2 = 1$ .” Which step is invalid?
- A.From $(a+b)(a-b) = b(a-b)$ to $a + b = b$
- B.From $a = b$ to $a^2 = ab$
- C.From $a^2 - b^2 = ab - b^2$ to $(a+b)(a-b) = b(a-b)$
- D.From $2b = b$ to $2 = 1$
8.
A student proves: “if $n^2 + n + 1$ is even, then $(n+1)^2 + (n+1) + 1$ is even”, and concludes by induction that $n^2 + n + 1$ is even for all $n$ . Which statement is correct?
- A.The inductive step is valid, but the base case fails, and in fact $n^2 + n + 1$ is odd for every $n$ .
- B.The proof is correct.
- C.The inductive step is wrong algebra.
- D.The claim is true from $n = 1$ onwards; only $n = 0$ fails.
9.
Which Lean proposition expresses the principle of ordinary induction for the natural numbers?
- A.∀ P : ℕ → Prop, P 0 → (∀ n, P n → P (n + 1)) → ∀ n, P n
- B.∀ P : ℕ → Prop, (∀ n, P n → P (n + 1)) → ∀ n, P n
- C.∀ P : ℕ → Prop, P 0 → ∀ n, P n
- D.∀ P : ℕ → Prop, (∀ n, P n) → P 0 ∧ ∀ n, P n → P (n + 1)
10.
Write is_prime(n) and first_failure(claim, limit), which returns the least n with 0 <= n <= limit for which claim(n) is false, or None if there is none. Use them to find the first n for which $n^2 + n + 41$ is not prime. Why does your search not prove anything about the values beyond limit?
Computational — Practice

Answer key — Proof: direct, contrapositive, contradiction and induction

1.
The contrapositive of “ $n^2$ odd $\Rightarrow$ $n$ odd” is “ $n$ even $\Rightarrow$ $n^2$ even”. So assume $n = 2k$ ; then $n^2 = 2(2k^2)$ is even, which completes the proof.
2.
$1 + 2 + \dots + 200 = \dfrac{200 \cdot 201}{2} = 100 \cdot 201 = 20100$ . (Pairing: $100$ pairs $1 + 200, 2 + 199, \dots$ each summing to $201$ .)
3.
From $n = 1$ to $n = 2$ : removing one horse and then the other gives two groups of size $1$ that have no horse in common, so nothing forces the two colours to agree. Every other step is valid, but a chain of dominoes with one gap knocks nothing over beyond it.
4.
If one of the listed primes divided $N$ , it would divide $N - 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = 1$ , which is impossible. So every prime factor of $N$ is new. $N$ itself need not be prime: $30031 = 59 \cdot 509$ .
5.
Makeable: $3, 6, 7, 9, 10, 12, 13, 14, 15, 16, \dots$ Not makeable: $1, 2, 4, 5, 8, 11$ . Since $12, 13, 14$ can all be made, strong induction (add a $3$ to the amount three below) shows every amount from $12$ on can be made. So the answer is $11$ . (In general, for coprime $a, b$ it is $ab - a - b$ .)
6.
For “every $n \ge 2$ is a product of primes”: if $n$ is prime we are done; otherwise $n = ab$ with $1 < a, b < n$ , and we need the statement for both $a$ and $b$ — smaller numbers, but not necessarily $n - 1$ . Strong induction provides exactly this. The other three only need the previous case.
7.
The step from $(a+b)(a-b) = b(a-b)$ to $a + b = b$ cancels the factor $a - b$ , i.e. divides by $a - b = 0$ . Cancelling is valid only for non-zero factors. (The last step also divides, by $b$ , so it too needs $b \ne 0$ .)
8.
The inductive step is correct, since $(n+1)^2 + (n+1) + 1 = (n^2 + n + 1) + 2(n + 1)$ . But there is no base case: $n^2 + n + 1$ is $1, 3, 7, \dots$ In fact $n^2 + n = n(n + 1)$ is a product of consecutive integers, hence even, so $n^2 + n + 1$ is always odd. The Lean module proves both false_step_holds and never_even.
9.
Ordinary induction is ∀ P : ℕ → Prop, P 0 → (∀ n, P n → P (n + 1)) → ∀ n, P n: from the base case P 0 and the inductive step, conclude P n for all n. Without the base case the principle would “prove” False.

10.

def is_prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True

def first_failure(claim, limit):
    for n in range(limit + 1):
        if not claim(n):
            return n
    return None

The first failure is $n = 40$ : $40^2 + 40 + 41 = 41^2$ . A search up to limit finds counterexamples but can never prove a claim for all $n$ ; for n * (n + 1) being even, the proof by cases (Theorem 3) is what covers every $n$ .