Introduction To Mathematical Induction

 

What is Mathematical Induction?

Think of mathematical induction like knocking over a row of standing dominoes. Instead of knocking each one down individually, you only need to ensure two things:

1. The first domino falls.


2. If any given domino falls, it will inevitably knock over the next one.

In mathematics, this is a powerful technique used to prove that a statement, formula, or property is true for all positive integers (n = 1, 2, 3, ...).

A formal proof by induction consists of two essential steps:

• The Base Case: Prove that the statement holds true for the very first value, usually n = 1.


• The Inductive Step: Prove that if the statement holds true for an arbitrary integer k (this assumption is called the Inductive Hypothesis), then it must also be true for the next integer k + 1.

---

Two Classic Examples

Example 1: Sum of the First n Positive Integers

We want to prove the formula: 1 + 2 + 3 + ... + n = [n(n + 1)] / 2

• Base Case (n = 1): Left Side = 1. Right Side = [1(1 + 1)] / 2 = 2 / 2 = 1. Both sides match, so the base case holds.


• Inductive Step: Assume it works for n = k, meaning: 1 + 2 + ... + k = [k(k + 1)] / 2. Now, we must prove it works for n = k + 1. Add (k + 1) to both sides of our assumption, factor it out, and it simplifies perfectly to: [(k + 1)(k + 2)] / 2. The proof is complete.

Example 2: Divisibility

We want to prove that (n³ - n) is always divisible by 3 for any positive integer n.

• Base Case (n = 1): 1³ - 1 = 0. Since 0 is divisible by 3 (0 = 3 x 0), the base case holds.


• Inductive Step: Assume (k³ - k) is divisible by 3, so k³ - k = 3m. Now check for n = k + 1: (k + 1)³ - (k + 1). Expanding and rearranging gives us (k³ - k) + 3k² + 3k. Substituting our assumption gives 3m + 3k² + 3k, which factors out to 3(m + k² + k). Because the expression can be factored by 3, it is guaranteed to be divisible by 3.