Practice question · Multiple choice
A famous fake proof shows all horses are the same colour by induction: true for one horse, and any n+1 horses split into two overlapping groups of n. Where does it break?
Hints
- Write out the argument for exactly two horses. What is in the overlap?
- The inductive step must hold for EVERY n. Test the smallest one.
Show the answer
B. At n = 1 → 2, where the two groups of one horse do not overlap
Why
With two horses the sub-groups are {first} and {second}, sharing nothing, so no horse links the colours. The step holds for every n ≥ 2 and fails at exactly the point the chain must pass through, which is why 'the step works' has to be checked at the base, not just in general.
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.
- Order the parts of a proof by induction that 1 + 2 + ... + n = n(n+1)/2.
- 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…