Proof by Mathematical Induction Examples
Question
Task: What are some examples of mathematical proofs using induction?
Answer
Question: 01
Step 0: For all n ? 0, we want to show that remainder(n) = (n mod c).
Step 1: For any n ? 0, let P(n) be the property that remainder(n) = (n mod c). We want to show that P(n) is true for all n ? 0.
Step 2: As base cases, consider when n = 0, 1, ,…., (c-2). We will show that P(0), P(1), ……., P(c-2) are true:
For n = 0 :
Remainder (0) = 0, and 0 mod c = 0 . So, P(0) is true.
For n = 1:
Remainder (1) = 1, and 1 mod c = 1. So, P(1) is true.
Continue this process until n = (c-2).
Step 3: Let k ? c-1. For the induction hypothesis, suppose that P(i) is true for all 0 ?i ?k. That is, suppose that remainder(i) = (i mod c) for all 0 ?i ?k.
Step 4: Now, we prove that P(k+1) is true, using our induction assumptions that P(i) is true for all 0 ?i ?k. That is, we prove that remainder (k+1) = (k+1 mod c).
Step 5: The proof that P(k+1) is true (given that P(i) is true for all 0 ?i ?k is as follows:
left-hand side of P(k + 1) = remainder(k+1)
= remainder(k+1 - c) (by the algorithm)
= k+1 - c mod c (by induction hypothesis)
= k+1 mod c.
Step 6: The steps above have shown that for any k ?c-1, if P(i) is true for all 0 ?i ?k, then P(k+1) is also true. Combined with the base cases, which show that P(0), P(1),……., P(c-2) are true, we have shown that for all n ?0, P(n) is true, as desired.
Question: 02
Step 0: For all undirected graphs G = (V, E), we want to show that the number of simple paths of length c in a complete graph Kn is
Step 1: For any c ? 0, let P(c) be the property that the number of simple paths of length c in a complete graph Kn is . We want to show that P(c is true for all c ? 0.
Step 2: As a base case, consider when c = 0. We will show that P(0) is true: that is, the number of simple paths of length 0 in a complete graph Kn is . Fortunately, there is only one node in a simple path of length 0, and . = n. So, the base case is true.
Step 3: For the induction hypothesis, suppose (hypothetically) that P(k) is true for some fixed k ? 0. That is, suppose that the number of simple paths of length k in a complete graph Kn is .
Step 4: Now, we prove P(k+1), using the (hypothetical) induction assumption P(k) . That is, we prove that the number of simple paths of length k+1 in a complete graph Kn is .
Step 5: The proof that P(k+1) is true (given that P(k) is true) is as follows:
left-hand side of P(k + 1) = Number of simple paths of length (k + 1)
= Number of paths of length k × Number of ways to choose the next node
= . × (n - k)
= . (by algebra)
Step 6: The steps above have shown that for any k ? 0, if P(k) is true, then P(k+1) is also true. Combined with the base case, which shows that P(0) is true, we have shown that for all c ?0, P(c) is true, as desired.
Question: 03
Step 0: For all n ?3, we want to show that
Step 1: For any n ? 3, let P(n) be the property that . We want to show that P(n) is true for all n ? 3.
Step 2: As base cases, consider when n = 3 and n = 4. We will show that P(3) and P(4) are true:
For n = 3:
and. 1 = 4 . 1 + 2 . 1 = 6. So, P(3) is true.
For n = 4:
= 6 + 4 = 10, and . = 4 . 2 + 2 . 1 = 10 . So, P(4) is true.
Step 3: Let k ? 4. For the induction hypothesis, suppose that P(i) is true for all 3 ? i ? k. That is, suppose that for all 3 ? i ? k.
Step 4: Now, we prove P(k+1) is true, using our induction assumptions that P(i) is true for all all 3 ? i ? k. That is, we prove that .
Step 5: The proof that P(k+1) is true (given that P(i) is true for all 3 ? i ? k is as follows:
left-hand side of P(k + 1) =
= (by the recursive definition)
= +( ) (by induction hypothesis)
= +
= 4 (by the Fibonacci recurrence relation)
= right-hand side of P(k + 1).
Step 6: The steps above have shown that for any k ? 4, if P(i) is true for all 3 ? i ? k then P(k+1) is also true. Combined with the base cases, which show that P(3) and P(4) are true, we have shown that for all 3 ? i ? k, P(n) is true, as desired.
