# Induction

To prove a claim for every whole number n, show it for n = 1 (base case). Then show that truth for n = k forces truth for n = k + 1.

Maths (university) · Part 01: Logic, sets and proof · Card 7 of 9 · Last updated 2026-10-19

## Analogy

Dominoes: knock over the first, and make sure each one knocks the next. All of them fall.

## Example

**1 + 2 + ... + n = n(n+1)/2**

Base n = 1: 1 = 1(2)/2. True.
Assume it holds for n = k.
Add k+1: k(k+1)/2 + (k+1) = (k+1)(k+2)/2.
That is the formula for n = k+1.

## In practice

Use it for sums, divisibility and formulas that depend on a whole number n.

## Practice

### Flashcards

- **What are the two parts of a proof by induction?** The base case, then the inductive step from n = k to n = k + 1.

### Interview questions

**Prove by induction that 1 + 2 + ... + n = n(n+1)/2 for every whole number n >= 1.**

- Base case n = 1: both sides equal 1
- Assume true for n = k
- Add (k+1) to both sides
- Simplify to (k+1)(k+2)/2
- State that the claim holds for all n

## Questions people ask

### Why do I need the base case in induction?

The step only says 'if it works for k, it works for k + 1'. Without a starting point, nothing is ever true to begin the chain. A false claim such as 'n = n + 1' passes the step but fails at the base case, so both parts are required.

### What is the inductive hypothesis?

It is the assumption that the claim is true for n = k, for one fixed but arbitrary k. You do not prove it. You use it to show the claim for k + 1. In the sum formula, you replace 1 + ... + k with k(k + 1)/2 during that step.

## Related concepts

- [Contrapositive](https://studyvisually.com/learn/science/maths-university/maths-university-part-1/maths-university-part-1-concept-3)
- [Direct proof](https://studyvisually.com/learn/science/maths-university/maths-university-part-1/maths-university-part-1-concept-5)
- [Proof by contradiction](https://studyvisually.com/learn/science/maths-university/maths-university-part-1/maths-university-part-1-concept-6)
- [Epsilon-delta definition](https://studyvisually.com/learn/science/maths-university/maths-university-part-2/maths-university-part-2-concept-9)

Web page: https://studyvisually.com/learn/science/maths-university/maths-university-part-1/maths-university-part-1-concept-7
Study this card in the app: https://studyvisually.com/app/learn?category=maths-university&card=maths-university-part-1-concept-7