Chroma Mobile

Mathematical induction is a powerful and elegant proof technique used to establish the truth of a statement for all positive integers. Think of it as climbing an infinite ladder. To prove you can climb the entire ladder, you only need to show two things:

You can get on the first rung.
If you are on any given rung, you know how to climb to the next one.

If you can prove both of these, you've proven you can climb the entire ladder to infinity!

The Formal Principle

Let $P(n)$ be a statement about a positive integer $n$. To prove that $P(n)$ is true for all positive integers $n$, we must complete two steps:

Base Case: Show that the statement $P(1)$ is true.
Inductive Step: Assume the statement $P(k)$ is true for some arbitrary positive integer $k$ (this is the Inductive Hypothesis). Then, using this assumption, show that the statement $P(k+1)$ must also be true.

The Three Steps Explained

The Base Case: We start by proving the statement is true for the very first value, usually $n=1$. This is like stepping onto the first rung of the ladder. It anchors our proof.
The Inductive Hypothesis: We assume the statement is true for an arbitrary positive integer $k$. We don't prove this; we just assume it. This is like saying, "Let's assume we're standing on some random rung, the $k$-th rung."
The Inductive Step: This is the core of the proof. We use the Inductive Hypothesis (that $P(k)$ is true) to logically prove that the statement must also be true for the next integer, $k+1$. This shows that if we're on any rung, we can always get to the next one.

Example Problem

Prove that for every positive integer $n$, the sum of the first $n$ integers is given by the formula:

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

Solution Walkthrough

Here, our statement $P(n)$ is the equation $1 + 2 + \dots + n = \frac{n(n+1)}{2}$.

Step 1: The Base Case (n=1)

We need to show that the formula holds true for $n=1$. Let's check both sides of the equation.

Left-Hand Side (LHS): The sum of the first 1 integer is just $1$.
Right-Hand Side (RHS): Plugging $n=1$ into the formula gives $\frac{1(1+1)}{2} = \frac{1(2)}{2} = 1$.

Since LHS = RHS (1 = 1), the Base Case is true. We're on the first rung!

Step 2: The Inductive Hypothesis

We assume that the statement $P(k)$ is true for some arbitrary positive integer $k$. This means we assume:

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

We will use this assumed equation as a fact in the next step.

Step 3: The Inductive Step

Our goal is to prove that $P(k+1)$ is true. That is, we want to prove:

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

Let's start with the Left-Hand Side (LHS) of the $P(k+1)$ equation and use our Inductive Hypothesis to simplify it.

The LHS is $\underbrace{1 + 2 + 3 + \dots + k} + (k+1)$.

Notice that the part in the underbrace is exactly the LHS of our Inductive Hypothesis, $P(k)$. We can substitute its value, $\frac{k(k+1)}{2}$:

\begin{align*} \text{LHS} &= \left( 1 + 2 + \dots + k \right) + (k+1) \\ &= \frac{k(k+1)}{2} + (k+1) \quad \text{(by Inductive Hypothesis)} \\ &= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} \quad \text{(finding a common denominator)} \\ &= \frac{k(k+1) + 2(k+1)}{2} \quad \text{(combining the fractions)} \\ &= \frac{(k+1)(k+2)}{2} \quad \text{(factoring out (k+1))} \\ &= \frac{(k+1)((k+1)+1)}{2} \quad \text{(re-arranging to match the goal)} \end{align*}

This final expression is exactly the Right-Hand Side (RHS) of the $P(k+1)$ statement we wanted to prove. We have successfully shown that if $P(k)$ is true, then $P(k+1)$ must also be true.

Conclusion

Since we have successfully verified the Base Case and completed the Inductive Step, the Principle of Mathematical Induction guarantees that the formula is true for all positive integers $n$. This technique is a cornerstone of discrete mathematics, computer science, and many other fields for proving properties of sequences, algorithms, and structures.

The Principle of Mathematical Induction