Mathematical Induction Math Example 1

Follow the full solution, then compare it with the other examples linked below.

Example 1

medium
Use mathematical induction to prove: 1+2+3+⋯+n=n(n+1)21 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} for all n≥1n \ge 1.

Solution

  1. 1
    Base case (n=1n=1): LHS =1= 1. RHS =1⋅22=1= \frac{1 \cdot 2}{2} = 1. True.
  2. 2
    Inductive hypothesis: Assume the formula holds for n=kn = k, i.e., 1+2+⋯+k=k(k+1)21 + 2 + \cdots + k = \frac{k(k+1)}{2}.
  3. 3
    Inductive step: Show it holds for n=k+1n = k+1. LHS =k(k+1)2+(k+1)=k(k+1)+2(k+1)2=(k+1)(k+2)2= \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.
  4. 4
    This matches (k+1)((k+1)+1)2\frac{(k+1)((k+1)+1)}{2}. By induction, the formula holds for all n≥1n \ge 1.

Answer

1+2+⋯+n=n(n+1)2 for all n≥11 + 2 + \cdots + n = \frac{n(n+1)}{2} \text{ for all } n \ge 1
Mathematical induction has two steps: verify a base case, then show that if the statement holds for kk, it holds for k+1k+1. This creates a chain of truth for all natural numbers.

About Mathematical Induction

Mathematical induction proves statements indexed by integers by verifying a base case and an inductive step.

Learn more about Mathematical Induction →

More Mathematical Induction Examples

Example 2 hard

Prove by induction: [formula] for all integers [formula].

Example 3 medium

Prove by induction: [formula] for all [formula].

Example 4 medium

Prove by induction that [formula] for all [formula].

← All Mathematical Induction Examples Mathematical Induction Concept