Answers · The mathematics underneath
Why does induction need a base case if the step works?
In shortThe step only says that if one case holds then the next does; without a first case there is nothing to start from, so no case is proved.
In an induction, the base case is what makes the chain start. A step that proves only says that each case would force the next; without a case already known, it forces nothing.
The chain with actual numbers
Take as the claim . The first case is : the left side is , and the right side is , so is true. For the step, suppose holds for some particular . Adding to both sides of the assumed equality and simplifying gives the next case.
The first case plus the step produces a finite route to every whole number. From , the step with gives ; the step with gives ; and so on. Check the arithmetic on the first two links: says , both sides ; says , both sides . The step is the same general argument each time, not a new check for , or any later number. Without , the first application has no input.
People sometimes read the step as a licence to check , then , then , and so on forever. It is not that. The step is one general implication, proved once for an arbitrary , and the base case is the one place where the condition of that implication is met outright. That is why two finite checks settle infinitely many cases.
A sound step, no base, no proof
Here is a claim with a step that works for every and is false for every : is . The step says: if , then adding to both sides gives , which is . That conditional is true for every . The base case fails at , since . Nothing follows, and indeed no number equals the next. This is the plainest case of a perfect step proving nothing: the step is true, the claim is false everywhere, and the missing base is the whole difference.
The natural guess is that a step covering every transition must cover every case. It does not. A transition is not a case. The step is a conditional, and a conditional can be true while its antecedent is false for every number; is exactly that. The step never asserts for any , so it cannot manufacture . The base case is the only place a case is asserted outright. Remove it and the argument has no true instance to apply the step to.
Where a step can be narrower than it looks
A step can also fail to work for the general case even though it works for the small cases you tried. The classic shape is the claim that every group of horses is one colour. The first case is true: a group of one horse has one colour. The step from to is argued by taking two overlapping groups of horses, each one colour, and concluding the union is one colour. That argument needs the two groups to overlap. For , each group has one horse, and two groups of one horse cannot overlap unless they are the same horse, so the step from to is not established. The step works only for , and the chain never reaches .
Another step may need more than the single case before it. If it uses as well as , or several earlier cases, the single-step form is invalid. It can be repaired by a strong step that assumes all earlier cases, but the repair must be stated and the base case still has to start the chain. A step that quietly uses two previous cases is a step nobody can check from the written argument. The first case and the step are two separate checks, and neither replaces the other.
Worth keeping
- A sound step can be true for every n while the claim is false for every n, so the base case is not a formality.
- If the step only works from some n onward, the base case must be at that n or an earlier link must be proved separately.
- A step that uses more than the previous case must say so and use the strong form; otherwise the argument is incomplete.
Where this goes next
This question is one step of Arguing That It Always Holds, a course that works through its subject from the beginning. The page that teaches this part of it is Proving It for Every Number, and it reads the whole way through whether or not you have an account.
What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.
Read that pageThe whole courseOther questions people ask about this
- How do you make a vague claim precise enough to tell whether it's true?Fix what is being talked about, what is asserted, which cases are covered and the cut-off, then name an observation that would prove it false.
- Why does the negation of "A and B" become "not A or not B"?Negating 'A and B' asserts that at least one of the two fails, so the and becomes an or.
- Why is an if-then statement true when the condition is false?An if-then claim only forbids one case, the condition holding while the result fails, so when the condition is false there is nothing left for it to forbid and it stays true.
- What is the difference between variance and standard deviation?They measure the same spread: variance is the average squared distance from the mean, standard deviation is its square root, so you report the standard deviation and calculate with the variance.
- How do you find the parabola that best fits a function near a point?Match the function's height, slope and bending at the chosen point; those three conditions single out exactly one parabola.
- Why does a test for a rare disease give so many false positives if the test is accurate?A positive result means the test fired, not that you are likely to be ill; when the disease is rare, healthy people vastly outnumber ill ones, so a small false-alarm rate on them swamps the few true cases.