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.
Typically we use it to prove mathematical statements of the form, if P then Q.
Example. If n is an odd integer, then n^{2} is also an odd integer.
Proof:
Assume that n is an odd integer. Then, by definition ∃k ∈ ℤ: n = 2k + 1.
n^{2} = (2k + 1)^{2} = 4k^{2} + 4k + 1 = 2(k^{2} + 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 ∎
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^{2} is odd, then n is odd.
Proof.
Proof by contrapositive. If n is even, then n^{2} is even.
If n is even ⇒ ∃k: n = 2k ⇒ n^{2} = 4k^{2} = 2(2k^{2}) ⇒ n^{2} 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 = a^{2}/b^{2} ⇒ 2b^{2} = a^{2} ⇒ [Odd number times odd number is always odd] a itself is even, ∃k: a = 2k.
2 = a^{2}/b^{2} ⇒ 2 = 4k^{2}/b^{2} ⇒ 2b^{2} = 4k^{2} ⇒ b^{2} = 2k^{2} ⇒ b^{2} 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_{1}, p_{2}, ···, p_{n}.
Consider the following number, P = p_{1}p_{2}···p_{n} + 1. It is clear that no prime p_{1}, p_{2}, ···, 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 ⊥
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:
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} = ^{0}⁄_{2}
(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 ∎
(i) P(1), i.e., 1 = 1^{2}. This is certainly true.
(ii) Let’s assume that P(n) is true, i.e., 1 + 3 + 5 + 7 + … + (2n - 1) = n^{2}.
P(n+1) = 1 + 3 + 5 + 7 + … + (2n - 1) + (2n + 1) = [P(n) holds. Inductive case] n^{2} + (2n + 1) = (n + 1)^{2}, and thus P(n+1) is true, QED.
(i) P(0), 10^{1} + 3·10^{0} + 5 = 18 is divisible by 9.
(ii) Let’s assume that P(n) is true, i.e., 10^{n+1} + 3·10^{n} + 5 = 9m ⇒ 10^{n+2} + 3·10^{n+1} + 5 = 10(10^{n+1} + 3·10^{n}) + 5 = 10(9m -5) + 5 = 90m -50 + 5 = 90m -45 = 9(10m -5), therefore 10^{n+2} + 3·10^{n+1} + 5 is divisible by 9.
(i) P(0) and P(1) hold true because 2^{0} = 1 > 0 and 2^{1} = 2 > 1.
(ii) Let’s assume that P(n) is true n > 1 ⇒ 2^{n+1} = 2·2^{n} > 2·n = n + n > n + 1∎
(1) P(1), i.e., 6 divides 8^{1} - 2^{1} = 6. This is certainly true.
(2) Let’s assume that P(n) is true. 8^{n+1} - 2^{n+1} = 8·8^{n} - 2·2^{n} = 6·8^{n} + 2·8^{n} - 2·2^{n} = 6·8^{n} + 2·(8^{n} - 2^{n}). Therefore, 6 divides 8^{n} - 2^{n} -P(n) holds. Inductive case-, and 6 certainly divides 6·8^{n}, 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
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.’
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.
Example. Given n ∈ ℕ, define a_{n} recursively as follows: a_{0} = 1, a_{1} = 3, a_{n} = 2·a_{n-1} - a_{n-2} ∀n ≥ 2. Prove that a_{n} = 2·n + 1, ∀n ≥ 0
Proof.
Base cases. n = 0, a_{0} = 1 = 2·0 +1. a_{1} = 3 = 2·1 + 1.
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∎