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 n2 is also an odd integer.

Proof:

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

n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(k2 + 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 n2 is odd, then n is odd.

Proof.

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

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

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 = a2/b2 ⇒ 2b2 = a2 ⇒ [Odd number times odd number is always odd] a itself is even, ∃k: a = 2k.

2 = a2/b2 ⇒ 2 = 4k2/b2 ⇒ 2b2 = 4k2 ⇒ b2 = 2k2 ⇒ b2 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 p1, p2, ···, pn.

Consider the following number, P = p1p2···pn + 1. It is clear that no prime p1, p2, ···, pn divides this number (pi | P ⇒ pi|P and pi| (P-1) ⇒ pi = 1 that is not prime ⊥) ⇒ Since P > pi ∀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 = n(n+1)2.

Proof. Let P(n) denote the statement that the proposition $\sum_{k=0}^n$ k = n(n+1)2 holds for that particular n.

(i) P(0) is true because 0 = 0 (0 + 1)2 = 02

(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] n(n+1)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 n2.

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

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

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

QED (quod erat demonstrandum, “Which was to be demonstrated”) is written to indicate the end of a proof. Modern textbooks often use the graphical symbol ∎ instead.
• Prove 10n+1 + 3·10n + 5 is divisible by 9 for all n ∈ ℕ.

(i) P(0), 101 + 3·100 + 5 = 18 is divisible by 9.

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

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

(i) P(0) and P(1) hold true because 20 = 1 > 0 and 21 = 2 > 1.

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

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

(1) P(1), i.e., 6 divides 81 - 21 = 6. This is certainly true.

(2) Let’s assume that P(n) is true. 8n+1 - 2n+1 = 8·8n - 2·2n = 6·8n + 2·8n - 2·2n = 6·8n + 2·(8n - 2n). Therefore, 6 divides 8n - 2n -P(n) holds. Inductive case-, and 6 certainly divides 6·8n, 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 an recursively as follows: a0 = 1, a1 = 3, an = 2·an-1 - an-2 ∀n ≥ 2. Prove that an = 2·n + 1, ∀n ≥ 0

Proof.

1. Base cases. n = 0, a0 = 1 = 2·0 +1. a1 = 3 = 2·1 + 1.

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

Bitcoin donation