Skip to main content
MathidiaMathematics Academy
Proof and mathematical language
Lesson 5 of 75
Review

Mathematical induction

Objective. Prove identities, divisibility and inequalities by induction.

  1. 1. Learn
  2. 2. Worked example
  3. 3. Practice
  4. 4. Feedback
  5. 5. Continue

Learn: the key idea

Mathematical induction proves a statement P(n) holds for all integers n≥n₀ by establishing a base case P(n₀) and an inductive step showing P(k)⇒P(k+1) for arbitrary k≥n₀. Together these two pieces act like dominoes: the base case starts the chain, and the inductive step guarantees each subsequent case follows. For example, to prove 1+2+⋯+n=n(n+1)/2, check n=1 gives 1=1·2/2=1, then assume it holds for k and add (k+1) to both sides to show it holds for k+1. Induction also extends to proving divisibility (e.g. 3 divides n³−n) and inequalities. The inductive hypothesis must be used explicitly within the inductive step, not merely restated.

Worked example

Use induction to prove that 1+2+⋯+n = n(n+1)/2 for all integers n≥1.

-1012234+2
Number line from -1 to 4 with a jump of 2 forwards from 1
  1. 1Base case n=1: left side is 1, right side is 1(2)/2=1, so it holds.
  2. 2Inductive hypothesis: assume 1+2+⋯+k = k(k+1)/2 for some k≥1.
  3. 3Add (k+1) to both sides: 1+2+⋯+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2.
  4. 4This matches the formula at n=k+1, so by induction the formula holds for all n≥1.

Answer: n(n+1)/2 holds for all n≥1 by induction

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. A frequent flaw is proving the base case and the final formula separately without ever using the inductive hypothesis P(k) inside the step for P(k+1); without that link, the chain of dominoes is broken and the proof is invalid.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard