Writing Proofs

Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step), Concrete Mathematics, by Ronald Graham, Donald Knuth, and Oren Patashnik.

Direct Proof.

Typically we use it to prove mathematical statements of the form, if P then Q.

1. It takes an original statement P, which we assume to hold true.
2. We use this original statement P to show directly that another mathematical statement Q is also true.
3. We use what we know about P, i.e., unpack it with definitions and facts or results (aka. lemmas and theorems) that we already know about P.
4. Basically, we get equivalent statements about P, perform some mathematical calculations, logical reasoning, computations, and analytical thinking.
5. Finally, we repack or rewrite Q.

Example. If n is an odd integer, then n² is also an odd integer.

Proof:

Assume that n is an odd integer. Then, by definition ∃k ∈ ℤ: n = 2k + 1.

n² = (2k + 1)² = 4k² + 4k + 1 = 2(k² + 2k) + 1 which is also an odd number ∎

Example. The sum of two odd integers is even.

Proof:

Let n, m be odd numbers. The, by definition ∃s, t: n = 2s + 1, m = 2t + 1.

n + m = [Substitution] 2s +1 + 2t +1 = 2(s +t +1) which is an even number ∎

Contrapositive

Proof by contrapositive is exchanging the hypothesis and conclusion of a conditional statement and negating both hypothesis and conclusion. It relies on the fact that a conditional statement P → Q is logically equivalent to ~Q → ~P.

A conditional statement is true if and only if its contrapositive is true, P → Q ↭ ~Q → ~P.

Example. Let a, b ∈ ℤ. If n does not divide ab (n ɫ ab), then n does no divide a (n ɫ a) and n does not divide b (n ɫ b).

Proof. We are going to prove the contrapositive statement. If n does divide a (n | a) or (Notice that the logical operator “and” is replaced with “or”) n divide b (n | b), then n divides ab (n | ab).

If n divide a (n | a) ⇒ ∃c ∈ ℤ: a = nc ⇒ ab = (nc)b ⇒ ab = n(cb) ⇒ n | ab. If n divides b is absolutely identical ∎ or Mutatis mutandis a and b meaning “with things changed that should be changed” is used in place of words like analogously and similarly, and expresses that an argument can be applied to a new situation when some work but no imagination is demanded of the reader.

Example. If n² is odd, then n is odd.

Proof.

Proof by contrapositive. If n is even, then n² is even.

If n is even ⇒ ∃k: n = 2k ⇒ n² = 4k² = 2(2k²) ⇒ n² is even ∎

Proof by contradiction or reductio ad impossibile

It is a form of proof that establishes the truth or validity of a proposition or statement by showing that assuming the proposition to be false leads to a contradiction.

If the proposition to be proved is P. We assume the statement P to be false (¬P) and show that this leads to a contradiction, then it is concluded that P is in fact true.

Example: $\sqrt{2}$ is irrational.

Suppose $\sqrt{2}$ is rational ⇒ ∃a, b: $\sqrt{2} = \frac{a}{b}$. Without loss of generality, we can assume that a and b have no factors in common, i.e., the fraction is in its simplest or lowest form.

$\sqrt{2} = \frac{a}{b}$ ⇒ 2 = a²/b² ⇒ 2b² = a² ⇒ [Odd number times odd number is always odd] a itself is even, ∃k: a = 2k.

2 = a²/b² ⇒ 2 = 4k²/b² ⇒ 2b² = 4k² ⇒ b² = 2k² ⇒ b² is even ⇒ b is even. This is a contradiction because in order for a/b to be in its simplest form, both numerator and denominator cannot be even, one or both must be odd. Otherwise, we could simply a/b by 2 ⊥

Example: There are an infinite amount of prime numbers.

Proof.

Suppose that the number of prime numbers is finite ⇒ ∃n ∈ ℕ, there are only n prime numbers, say p₁, p₂, ···, p_n.

Consider the following number, P = p₁p₂···p_n + 1. It is clear that no prime p₁, p₂, ···, p_n divides this number (p_i | P ⇒ p_i|P and p_i| (P-1) ⇒ p_i = 1 that is not prime ⊥) ⇒ Since P > p_i ∀i, then P is a new prime number ⊥

Mathematical induction

Principle of induction. It is a way of proving that P(n) is true for every natural number (or more generally for all natural numbers greater than a fixed element “a”). Let P(n) be a family of statements indexed by the natural numbers. Suppose that:

• (i) P(0) holds true. This is the Base case and…
• (ii) for any n, if the statement holds for n, i.e., P(n) is true, then it holds for n +1, that is, P(n + 1) is also true. This is the Inductive case.

Then P(n) is true for all natural numbers n. Proof by induction is analogous to the toppling of dominoes. If dominoes are stacked in such a way (sufficiently close) that if the nth domino falls, it will push the (n + 1)th domino over, then for every domino to fall we only need to topple the first one.

Problem: Prove that for any integer n ≥ 0, 0 + 1 + 2 + 3 + ··· + n = $\sum_{k=0}^n$ k = ⁿ⁽ⁿ⁺¹⁾⁄2.

Proof. Let P(n) denote the statement that the proposition $\sum_{k=0}^n$ k = ⁿ⁽ⁿ⁺¹⁾⁄2 holds for that particular n.

(i) P(0) is true because 0 = ^{0 (0 + 1)}⁄₂ = ⁰⁄₂

(ii) Next, we assume that P(n) holds or is true for n.

Then, $\sum_{k=0}^{n+1}$ k = $\sum_{k=0}^{n}$ k + (n + 1) = [P(n) holds. Inductive case] ⁿ⁽ⁿ⁺¹⁾⁄2 + (n + 1) = ^{n(n+1)+2(n+1)}⁄2 = ^(n+1)(n+2)⁄2, and thus P(n+1) is true ∎

• Prove that the sum of the first n odd numbers is equal to n².

(i) P(1), i.e., 1 = 1². This is certainly true.

(ii) Let’s assume that P(n) is true, i.e., 1 + 3 + 5 + 7 + … + (2n - 1) = n².

P(n+1) = 1 + 3 + 5 + 7 + … + (2n - 1) + (2n + 1) = [P(n) holds. Inductive case] n² + (2n + 1) = (n + 1)², and thus P(n+1) is true, QED.

• Prove 10ⁿ⁺¹ + 3·10ⁿ + 5 is divisible by 9 for all n ∈ ℕ.

(i) P(0), 10¹ + 3·10⁰ + 5 = 18 is divisible by 9.

(ii) Let’s assume that P(n) is true, i.e., 10ⁿ⁺¹ + 3·10ⁿ + 5 = 9m ⇒ 10ⁿ⁺² + 3·10ⁿ⁺¹ + 5 = 10(10ⁿ⁺¹ + 3·10ⁿ) + 5 = 10(9m -5) + 5 = 90m -50 + 5 = 90m -45 = 9(10m -5), therefore 10ⁿ⁺² + 3·10ⁿ⁺¹ + 5 is divisible by 9.

• Prove that 2ⁿ > n ∀n ∈ ℕ.

(i) P(0) and P(1) hold true because 2⁰ = 1 > 0 and 2¹ = 2 > 1.

(ii) Let’s assume that P(n) is true n > 1 ⇒ 2ⁿ⁺¹ = 2·2ⁿ > 2·n = n + n > n + 1∎

• Prove that 6 divides 8ⁿ - 2ⁿ for every positive integer n.

(1) P(1), i.e., 6 divides 8¹ - 2¹ = 6. This is certainly true.

(2) Let’s assume that P(n) is true. 8ⁿ⁺¹ - 2ⁿ⁺¹ = 8·8ⁿ - 2·2ⁿ = 6·8ⁿ + 2·8ⁿ - 2·2ⁿ = 6·8ⁿ + 2·(8ⁿ - 2ⁿ). Therefore, 6 divides 8ⁿ - 2ⁿ -P(n) holds. Inductive case-, and 6 certainly divides 6·8ⁿ, and thus P(n+1) is true, QED.

Strong Form of Induction. Let P(n) be a family of statements indexed by the natural numbers. Suppose that

• (i) P(0) is true and
• (ii) for any n, if P(0), P(1), . . . , P(n) are true then P(n + 1) is also true.

Then P(n) is true for all natural numbers n.

Proof.

Let Q(n) be the statement ‘P(k) is true for k = 0, 1, … n.’

1. Q(0) = P(0) is true.
2. For any n, if P(0), P(1), . . . , P(n) are true (aka if Q(n) is true), then P(n + 1) is also true, that is, P(0), P(1), . . . , P(n), P(n + 1) are true, and therefore, Q(n + 1) holds. Consequently, Q(n) is true for all n ∈ ℕ.

Proposition. Every natural number greater than 1 may be expressed as a product of one or more prime numbers.

Proof.

Let P(n) be the statement that n may be expressed as a product of prime numbers.

1. P(2) is true, since 2 is itself prime.
2. Let n > 2, n ∈ ℕ, and suppose P(m) holds for all m < n. If n is itself a prime, then P(n) is obviously true. Otherwise, n = s·t for some s, t ∈ ℕ with s, t < n. By our inductive hypothesis, s and t can be expressed as products of primes, and therefore n = s·t can also be expressed as a product of prime numbers. By the strong form of induction, P(n) holds for all natural numbers.

Example. Given n ∈ ℕ, define a_n recursively as follows: a₀ = 1, a₁ = 3, a_n = 2·a_n-1 - a_n-2 ∀n ≥ 2. Prove that a_n = 2·n + 1, ∀n ≥ 0

Proof.

1. Base cases. n = 0, a₀ = 1 = 2·0 +1. a₁ = 3 = 2·1 + 1.

2. Strong inductive hypothesis. Suppose a_n = 2·n + 1, for all 0 ≤ k ≤ n. a_n+1 = [By definition] 2·a_n -a_n-1 = [By Strong inductive hypothesis] = 2·(2·n + 1) - (2·(n-1) +1) = 4n +2 -(2n -1) = 2n + 3 = 2·(n + 1) + 1∎