Practice question · Put in order
Order the parts of a proof by induction that 1 + 2 + ... + n = n(n+1)/2.
- Conclude the formula holds for every natural number n
- Inductive hypothesis: assume the formula holds for n = k
- Simplify to the formula with k+1 in place of k
- Base case: check the formula holds for n = 1
- Inductive step: add k+1 to both sides
Hints
- Induction has two obligations before the conclusion: anchor it, then propagate it.
- The step must end in exactly the original formula with k+1 substituted.
Show the answer
- Base case: check the formula holds for n = 1
- Inductive hypothesis: assume the formula holds for n = k
- Inductive step: add k+1 to both sides
- Simplify to the formula with k+1 in place of k
- Conclude the formula holds for every natural number n
Why
Base case anchors the chain, the hypothesis supplies a foothold, the step propagates it from k to k+1, and the conclusion follows for all n. Both obligations are essential, either one alone proves nothing.
Practise Mathematical Induction
The app has 6 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Mathematical Induction
- Select every statement that is TRUE about mathematical induction.
- An inductive step alone, without a base case, is enough to prove a statement for all n.
- Using the formula 1 + 2 + ... + n = n(n+1)/2, compute the sum of the first 10 natural numbers.
- Complete the statement of the inductive step.
- An induction proof assumes the very statement it is trying to prove holds for n, then proves it for n+1. Why…
- A famous fake proof shows all horses are the same colour by induction: true for one horse, and any n+1 horses…