Proof by Induction

Proof by Induction

Mathematical Induction is a powerful proof technique used to prove statements about natural numbers (or integers in general) that hold for all values greater than or equal to a certain base case. It is a form of mathematical reasoning that establishes the truth of an infinite number of cases with a finite number of steps.

Proof by induction is especially useful for proving statements that are structured in a way that can be broken down into simpler cases, such as those involving sums, products, inequalities, and other recursively defined structures.

---

Steps in Mathematical Induction

The inductive proof is performed in two main steps:

1. Base Case:

   • First, you prove that the statement is true for the smallest possible value, typically $n = 0$ or $n = 1$. This step is necessary because induction builds on the assumption that the statement holds for smaller cases.

2. Inductive Step:

   • Next, you assume that the statement is true for some arbitrary integer $n = k$, known as the inductive hypothesis. Then, you use this assumption to prove that the statement is true for $n = k + 1$.

If both steps are successfully proven, it implies that the statement holds for all natural numbers starting from the base case.

---

Structure of a Proof by Induction

1. Base Case

Prove that the statement holds for the first value of $n$ (e.g., $n = 1$ or $n = 0$).

2. Inductive Hypothesis

Assume that the statement is true for some integer $n = k$. This is your inductive hypothesis.

3. Inductive Step

Prove that if the statement holds for $n = k$, then it must also hold for $n = k + 1$. This is the critical step where the inductive hypothesis is used to establish the truth for the next case.

4. Conclusion

Since the statement is true for the base case, and assuming that it holds for an arbitrary $k$, you have shown it must also hold for $k + 1$. By the principle of induction, the statement is true for all $n \geq 1$.

---

Example of Proof by Induction

Example 1: Prove that the sum of the first $n$ natural numbers is given by the formula:

$$S_n = 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$$

Step 1: Base Case

• We need to prove that the formula is true for $n = 1$.

$$S_1 = 1$$

The formula gives:

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

Since both sides are equal, the base case holds true.

Step 2: Inductive Hypothesis

• Assume that the formula is true for some arbitrary $n = k$. This means we assume that:

$$S_k = 1 + 2 + 3 + \dots + k = \frac{k(k+1)}{2}$$

is true.

Step 3: Inductive Step

• We need to prove that the formula holds for $n = k + 1$. That is, we need to prove:

$$S_{k+1} = 1 + 2 + 3 + \dots + k + (k+1) = \frac{(k+1)(k+2)}{2}$$

Starting with the sum $S_{k+1}$, we have:

$$S_{k+1} = S_k + (k+1)$$

By the inductive hypothesis, we know that $S_k = \frac{k(k+1)}{2}$. So:

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

Factor out $(k+1)$:

$$S_{k+1} = (k+1) \left( \frac{k}{2} + 1 \right)$$

Simplify the expression inside the parentheses:

$$S_{k+1} = (k+1) \left( \frac{k + 2}{2} \right)$$

Now, this simplifies to:

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

Thus, the formula holds for $n = k + 1$.

Step 4: Conclusion Since the base case holds true, and we have shown that if the formula holds for $n = k$, it must also hold for $n = k + 1$, we conclude that the formula is true for all $n \geq 1$ by the principle of mathematical induction.

---

Example 2: Prove that $2^n \geq n^2$ for all $n \geq 5$.

Step 1: Base Case

• Prove that the statement holds for $n = 5$.

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

Since $32 \geq 25$, the base case holds true.

Step 2: Inductive Hypothesis

• Assume that the statement is true for $n = k$, i.e., $2^k \geq k^2$.

Step 3: Inductive Step

• We need to prove that $2^{k+1} \geq (k+1)^2$. Start with the left-hand side:

$$2^{k+1} = 2 \cdot 2^k$$

Using the inductive hypothesis, we know that $2^k \geq k^2$, so:

$$2^{k+1} \geq 2 \cdot k^2$$

Now, we need to show that $2 \cdot k^2 \geq (k+1)^2$. Expanding both sides:

$$2k^2 \geq k^2 + 2k + 1$$

Simplifying:

$$k^2 \geq 2k + 1$$

For $k \geq 5$, the inequality $k^2 \geq 2k + 1$ holds, so the inductive step is true.

Step 4: Conclusion Since the base case holds and we have shown that the statement holds for $n = k$ implies it holds for $n = k + 1$, we conclude that $2^n \geq n^2$ for all $n \geq 5$ by mathematical induction.

---

Key Concepts in Mathematical Induction

1. Base Case: The first step where you prove the statement for the initial value (usually $n = 1$ or $n = 0$).

2. Inductive Hypothesis: The assumption that the statement holds for some arbitrary value $n = k$.

3. Inductive Step: The critical part of the proof where you show that if the statement is true for $n = k$, then it must also be true for $n = k + 1$.

4. Conclusion: By proving the base case and the inductive step, the principle of induction allows you to conclude that the statement is true for all integers greater than or equal to the base case.

---

When to Use Induction

Mathematical induction is particularly useful for:

• Proving statements about sums, sequences, or series.
• Establishing properties of recursively defined functions or algorithms.
• Proving inequalities involving natural numbers.

---

Conclusion

Proof by induction is a crucial technique in mathematics that allows us to prove statements about an infinite number of cases by showing that a base case holds and that, if the statement holds for an arbitrary case, it must also hold for the next case. By systematically applying the base case and inductive step, we can prove statements about all natural numbers or integers in a given range.