Proof by Induction

Level 1 - Math I (Physics) topic page in Real Numbers.

Mathematical Induction

Mathematical induction is a proof technique used to establish that a statement is true for all natural numbers \(n \in \mathbb{N}\).

The principle works like dominoes falling: if the first domino falls and each domino causes the next to fall, then all dominos will fall.

The Two Steps

Step 1: Base Case

Verify the statement is true for the smallest value, usually \(n = 1\) (or \(n = 0\)).

Base Case

\[P(1) \text{ is true}\]

Step 2: Inductive Step

Assume the statement is true for some arbitrary value \(n = k\) (this is the inductive hypothesis), then prove it must also be true for \(n = k + 1\).

Inductive Hypothesis

\[\text{Assume } P(k) \text{ is true}\]

Inductive Conclusion

\[\text{Prove } P(k+1) \text{ is true}\]

Conclusion

If both steps are proven, then \(P(n)\) is true for all \(n \geq 1\).

Example: Sum of First n Integers

Statement: \(P(n): 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\)

Base Case

For \(n = 1\):

Base Case Verification

\[1 = \frac{1 \times 2}{2} = 1 \quad \checkmark\]

Inductive Step

Assume \(P(k)\) is true:

Inductive Hypothesis Sum

\[1 + 2 + \cdots + k = \frac{k(k+1)}{2}\]

Now prove \(P(k+1)\):

Inductive Step Start

\[1 + 2 + \cdots + k + (k+1)\]

Inductive Step Using Hypothesis

\[= \frac{k(k+1)}{2} + (k+1)\]

Inductive Step Simplify

\[= \frac{k(k+1) + 2(k+1)}{2}\]

Inductive Step Factor

\[= \frac{(k+1)(k+2)}{2}\]

Inductive Step Conclusion

\[= \frac{(k+1)((k+1)+1)}{2}\]

This is exactly \(P(k+1)\). ∎

Therefore, the formula holds for all positive integers \(n\).

Important Notes

The inductive hypothesis must be assumed for some arbitrary \(k\), not a specific value
Both steps are essential—omitting either invalidates the proof
Sometimes the base case starts at \(n = 0\) or another value depending on the statement

Summation Notation

Binomial Coefficients