Formalizing Proofs for Mathematical Induction

---

---

Mathematical Inductions are one of the fundamental methods for proving statements or conjectures about natural numbers and sequences.

In this chapter, we will see the process of proving mathematical inductions, understand their structure and essentials through detailed examples.

Understanding Mathematical Induction

The concept of "Induction" is often used while trying to prove a statement that applies to all natural numbers or for numbers beyond a certain threshold.

Inductive proofs have two main parts −

• The base case, where the statement is verified for an initial value (like n = 1 or n = 28)
• The inductive step, where we consider that the statement holds for an arbitrary case n = k and show it must also hold for n = k + 1.

Let us understand these two steps in detail −

• Base Case − We start the proof at the base case. In this state, we set goal to prove the statement is true for a particular starting point (e.g., the smallest number or a minimum threshold).
• Inductive Step − Here we apply the "if-then" logic of the proof. We assume the statement is true for an arbitrary number k and then use this assumption to prove it for k + 1 as well.

When both parts are formed, we conclude that the statement is true for all numbers above the base case with the principle of induction.

Structure of an Inductive Proof

Let us understand the formal structure of an inductive proof, including how each part of the proof is built.

• State the Proposition − Define the proposition P(n) that we want to prove.
• Base Case − Show that P(n) is true for the initial case. And typically n = 1 or the starting point specified in the problem.
• Inductive Hypothesis − Assume P(k) holds for some arbitrary k ≥ 1.
• Prove P(k + 1) − Using P(k), it demonstrate that P(k + 1) must also be true.
• Conclusion − Finally conclude that by the principle of induction, the statement holds for all n ≥ the starting point.

Let us see these steps through examples for a better understanding.

Example 1: Sum of the First n Natural Numbers

One of the classic examples of mathematical induction is that proving the formula for the sum of the first n natural numbers −

$$\mathrm{1 \:+\: 2 \:+\: 3 \:+\: \cdots \:+\: n \:=\: \frac{n(n \:+\: 1)}{2}}$$

Step-by-Step Proof

Define the Statement − Consider P(n) be the statement 1 + 2 + 3 + + n = n(n + 1)/2.

Base Case − For n = 1,

$$\mathrm{1 \:=\: \frac{1(1 \:+\: 1)}{2} \:=\: 1}$$

So, P(1) holds true.

Inductive Hypothesis − Next assume P(k) is true for some k ≥ 1; that is,

$$\mathrm{1 \:+\: 2 \:+\: 3 \:+\: \cdots \:+\: k \:=\: \frac{k(k \:+\: 1)}{2}}$$

Inductive Step − We need to show that P(k + 1) holds, so it means −

$$\mathrm{1 \:+\: 2 \:+\: 3 \:+\: \cdots \:+\: k \:+\: (k\:+\:1) \:=\: \frac{(k\:+\:1)(k\:+\:2)}{2}}$$

Start by adding (k + 1) to both sides of the inductive hypothesis −

$$\mathrm{(1 \:+\: 2 \:+\: 3 \:+\: \cdots \:+\: k) \:+\: (k \:+\: 1) \:=\: \frac{k(k \:+\: 1)}{2} \:+\: (k \:+\: 1)}$$

It will be (k + 1) from the right side −

$$\mathrm{\frac{k(k\:+\:1)\:+\: 2(k\:+\:1)}{2} \:=\: \frac{(k\:+\:1)(k\:+\:2)}{2}}$$

This proves P(k + 1) holds true.

Conclusion − So by induction, the formula is valid for all n ≥ 1.

Example 2: Multiple of 5 in Powers of 6

Let us use induction to show that 6ⁿ − 1 is always a multiple of 5 for all natural numbers n.

Statement Definition − Consider P(n) be the statement that 6ⁿ − 1 is a multiple of 5.

Base Case − For n = 1,

$$\mathrm{6^{1} \:-\: 1 \:=\: 5}$$

which is a multiple of 5. Thus, P(1) is true.

Inductive Hypothesis − Assume P(k) holds for some k ≥ 1; so that, 6^k − 1 is a multiple of 5. This means 6^k−1 = 5m for some integer mmm.

Inductive Step − We need to show that P(k + 1) holds, i.e., 6^k+1 is a multiple of 5. So proceed as follows −

$$\mathrm{6^{k + 1}\:-\:1 \:=\: 6 \:\cdot\: 6^{k} \:-\: 1 \:=\: (5m \:+\: 1) \:\cdot\: 6 \:-\: 1 \:=\: 5(6m) \:+\: 5}$$

From here we can get 6^k+1 − 1 = 5 × (6m + 1), which is clearly a multiple of 5.

Conclusion − By induction, 6ⁿ − 1 is a multiple of 5 for all n ∈ N.

Example 3: Inequality Using Induction

Another useful area for induction is proving inequalities. For example, consider we want to prove that n² < 2ⁿ for all integers n ≥ 5.

Define the Statement − Let us consider P(n) represent the statement n² < 2ⁿ.

Base Case − For n = 5,

$$\mathrm{5^{2} \:=\: 2^{5} \quad \text{and} \quad 2^{5} \:=\: 32}$$

So, 2⁵ < 32 and P(5) is true.

Inductive Hypothesis − Assume P(k) is true for some k ≥ 5, this means k² < 2^k.

Inductive Step − Show that P(k + 1) holds, or

$$\mathrm{(k \:+\: 1)^2 \:\lt\: 2^{k \:+\: 1}}$$

Expanding the left side −

$$\mathrm{(k \:+\: 1)^2 \:=\: k^2 \:+\: 2k \:+\: 1}$$

Using the inductive hypothesis, k² < 2^k, so

$$\mathrm{(k \:+\: 1)^2 \:\lt\: 2^{k} \:+\: 2k \:+\: 1}$$

If we observe that carefully, for k ≥ 5, 2^k ≥ 2k+1, we get

$$\mathrm{(k \:+\: 1)^2 \:\lt\: 2 \:\times\: 2^{k} \:=\: 2^{k \:+\: 1}}$$

Thus, P(k + 1) is true.

Conclusion − By the induction, n² < 2ⁿ holds for all integers n ≥ 5.

Why are Mathematical Inductions Used?

Mathematical inductions show us how to establish that a pattern continues indefinitely. It simplifies proof structure and helps verify statements involving sequences, for natural numbers without needing to check each number individually. This is known as the "domino effect". It is used for proving statements which is what makes induction so powerful.

Conclusion

In this chapter, we touched upon the concept of proofing by mathematical induction. Starting with the basic principles of the base case and inductive step, we explained in detail how to set up an inductive proof with clear examples.

Through proofs on sums, multiples, and inequalities, we demonstrated how induction offers a structured way to confirm patterns across an infinite set of cases.

Whether checking formulas or verifying properties of sequences, mathematical inductions are used to understand complex relationships by relying on a foundational pattern.