Mathematical Induction

Mathematical Induction is the standard tool for proving statements indexed by integers (usually $n \geq 1$ ). It functions like a domino effect.

Structure of Proof

To prove a statement $P (n)$ is true for all integers $n \geq k$ :

Base Case: Verify that $P (k)$ is true.
Inductive Hypothesis: Assume $P (m)$ is true for some arbitrary integer $m \geq k$ .
Inductive Step: Prove that $P (m + 1)$ is true, using the assumption that $P (m)$ is true.

Conclusion: By the Principle of Mathematical Induction,

P (n)

is true for all

n \geq k

Common Applications

1. Summation Formulas

Example

Prove

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

Proof. Base Case ( $n = 1$ ): LHS $= 1$ , RHS $= \frac{1 ( 2 )}{2} = 1$ . True. Hypothesis: Assume $1 + \dots + m = \frac{m ( m + 1 )}{2}$ . Step: Add $m + 1$ to both sides.

1 + \dots + m + (m + 1) = \frac{m ( m + 1 )}{2} + (m + 1)

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

This matches the formula for

n = m + 1

. ∎

2. Divisibility

Example

Prove

n^{3} - n

is divisible by 3 for all

n \geq 1

Proof. Base Case ( $n = 1$ ): $1^{3} - 1 = 0$ , divisible by 3. Step: Assume $m^{3} - m = 3 k$ . Consider $(m + 1)^{3} - (m + 1) = (m^{3} + 3 m^{2} + 3 m + 1) - m - 1$ $= (m^{3} - m) + 3 m^{2} + 3 m = 3 k + 3 (m^{2} + m)$ . Since both terms are divisible by 3, the sum is divisible by 3. ∎

Practice Problems

Exercise (Problem 1)

Prove that

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

Exercise (Problem 2)

Prove that for any

n \geq 4

2^{n} < n!

Exercise (Problem 3)

Prove that

1 \cdot 1! + 2 \cdot 2! + \dots + n \cdot n! = (n + 1)! - 1