## 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.

**Tags:**mathematical induction proof by induction mathematical proofs examples step-by-step properties