Lesson 1.3: Proof by Mathematical Induction: Series and Divisibility

Introduction

Welcome to Lesson 1.3 of Foundation Further Mathematics! In this lesson, we will delve into the fascinating world of mathematical proofs, specifically focusing on proof by mathematical induction. By the end of this lesson, you, students, should be able to understand the four key stages of induction, why it works logically, and how to apply it in proving summation and divisibility results. 🤓

Learning Outcomes

By the end of this lesson, you should be able to:

• Understand the four stages of mathematical induction.
• Explain why induction is logically valid and identify what each stage establishes.
• Prove summation formulae, such as the sum of the first n cubes.
• Prove divisibility results, such as that $5^n - 1$ is divisible by 4.
• State and correctly apply the four stages of an inductive proof.

What is Mathematical Induction?

Mathematical induction is a technique used to prove that a given statement holds true for all natural numbers. It’s like building a strong tower, where you need a solid foundation to make sure it stands tall. Let's break down the process into four simple stages:

1. Base Case: Show that the statement holds true for the first natural number, usually $n=1$.
2. Inductive Hypothesis: Assume that the statement holds for some arbitrary natural number $k$.
3. Inductive Step: Demonstrate that if the statement is true for $k$, then it must also be true for $k+1$.
4. Conclusion: Conclude that since the base case is true and the inductive step holds, the statement must be true for all natural numbers.

Why Induction Works

Induction is a powerful method because it allows us to extend the truth of a statement from one number to the next, similar to a chain reaction! By proving that the base case is true, we lay the groundwork. The inductive step acts as a domino; if one domino falls (the statement being true for $k$), it causes the next domino to fall (the statement being true for $k+1$).

Examples of Proof by Induction

Let’s look at a couple of examples to solidify our understanding of this concept.

Example 1: Proving the Sum of the First n Cubes

We want to prove that the sum of the first $n$ cubes is equal to the square of the sum of the first $n$ natural numbers:

$$\sum_{i=1}^n i^3 = \left(\frac{n(n+1)}{2}

ight)^2$$

Step 1: Base Case

For $n = 1$:

$$\sum_{i=1}^1 i^3 = 1^3 = 1$$

And

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

$ight)^2 = \left(\frac{1 \cdot 2}{2}$

ight)^2 = 1$$

Both sides are equal, so the base case holds!

Step 2: Inductive Hypothesis

Assume the statement is true for some natural number $k$, that is,

$$\sum_{i=1}^k i^3 = \left(\frac{k(k+1)}{2}

ight)^2$$

Step 3: Inductive Step

We must show it holds for $k + 1$.

Thus, we consider:

$$\sum_{i=1}^{k+1} i^3 = \sum_{i=1}^k i^3 + (k + 1)^3$$

By substituting our inductive hypothesis:

$$\sum_{i=1}^{k+1} i^3 = \left(\frac{k(k+1)}{2}

ight)^2 + (k + 1)^3$$

Now, simplify this:

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

ight)^2 + $\frac{(k + 1)^3 \cdot 4}{4}$$$

$$= \frac{k^2(k + 1)^2 + 4(k + 1)^3}{4}$$

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

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

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

Thus,

$$\sum_{i=1}^{k+1} i^3 = \left(\frac{(k + 1)((k + 1) + 1)}{2}

ight)^2$$

This completes the inductive step.

Step 4: Conclusion

Since both the base case and inductive step hold, we conclude that the formula is true for all natural numbers!

Example 2: Proving Divisibility

Now, let’s prove that $5^n - 1$ is divisible by 4 for all natural numbers $n$.

Step 1: Base Case

For $n = 1$:

$$5^1 - 1 = 5 - 1 = 4$$

Since 4 is divisible by 4, the base case holds.

Step 2: Inductive Hypothesis

Assume the statement is true for some $k$, so $5^k - 1$ is divisible by 4. This means we can write:

$$5^k - 1 = 4m$$

for some integer $m$.

Step 3: Inductive Step

We want to show that $5^{k + 1} - 1$ is also divisible by 4.

$$5^{k + 1} - 1 = 5 \cdot 5^k - 1 = 5(5^k) - 1$$

Using our inductive hypothesis:

$$= 5(4m + 1) - 1 = 20m + 5 - 1 = 20m + 4$$

Clearly, $20m + 4$ is divisible by 4.

Step 4: Conclusion

Both the base case and inductive step hold, so $5^n - 1$ is divisible by 4 for all natural numbers $n$!

Conclusion

Mathematical induction is a fundamental concept that is widely used in various fields of mathematics. By understanding its four stages and practicing with examples, you will be well-equipped to tackle challenges in proof writing.

Study Notes

• Mathematical Induction Stages: Base case → Inductive hypothesis → Inductive step → Conclusion.
• Logical Validity: Each stage builds on the last, establishing truth for all natural numbers.
• Examples: Proving summation formulas and divisibility results.
• Importance: Induction is foundational for higher-level math concepts, including series, matrices, and more! 📚