Free sample   Proof by mathematical induction examples

## Proof by Mathematical Induction Examples

Question

Task: What are some examples of mathematical proofs using induction?

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.

NEXT SAMPLE