Motivation
A discrete proof must explain why infinitely many cases follow from finitely many steps. Testing examples cannot do this, and an induction step without a valid starting point cannot either. Before discussing induction, we must say exactly what a claim quantifies over and which choices may depend on earlier choices.
Definitions
Definition 1.1.1
(Predicates, quantifiers and dependence)
A predicate becomes a proposition when a value of is supplied or when is quantified over a stated domain. The statement requires every in to satisfy ; requires at least one witness. In the witness may depend on ; in a single witness must work for all .
Concept lensStructural
Dependent witnesses as functions
A statement asserts that a witness can be chosen for each , that is, that there is a function with for every . When is given by an explicit rule, as for “every integer has a larger integer”, that function is the proof; for arbitrary infinite domains, passing from the statement to such a function uses the axiom of choice. The reversed statement asks for a constant function. In this language the two quantifier orders differ as a function differs from a constant, and the negation names one input at which no witness exists, so that no such function can exist.
We take . An implication is false only when is true and false. Its contrapositive is equivalent, but its converse need not be. A counterexample to a universal statement must satisfy its hypotheses and violate its conclusion; an irrelevant example does not refute it.
Theorem/Proposition
Theorem 1.1.2
(Negating quantifiers)
For a predicate on any stated domain,
Thus is , with domains retained.
Theorem 1.1.3
(Ordinary and strong induction)
Suppose is a proposition for each . If holds and holds for every , then all hold. The same conclusion follows from and the stronger-hypothesis step: for every , together imply .
Proof sketch or proof idea
Proof
(The negation laws)
A universal statement fails precisely when at least one element fails the predicate; this proves the first negation law. An existential statement fails precisely when no element satisfies the predicate, equivalently every element fails it, proving the second. The laws remain valid on an empty domain: a universal claim is then true and an existential claim false. Applying the laws from outside inward preserves the order of dependencies.
Proof
(Induction through a least failing index)
For induction, suppose some is false and choose the least failing index . The base case rules out . In ordinary induction, is true by minimality, so the step makes true, a contradiction. In strong induction, every earlier is true, so the stronger-hypothesis step gives the same contradiction.
Strong induction is also derivable from ordinary induction by defining to mean that every for holds. The strong step proves . This explains why “strong” refers to the available induction hypothesis, not to a different truth principle.
Proof X-ray
What the least failing index supplies
The argument uses one property of that the theorem never states: every nonempty set of nonnegative integers has a least element. The base case is used once, to show , which is what makes an index at all; without it the argument fails, and indeed the step can hold for every while every is false. Minimality certifies the hypotheses of the step: ordinary induction needs only , strong induction needs all of , and both are available for the same reason. The step is then applied exactly once, at , contradicting the choice of . The reduction of strong to ordinary induction confirms that the two principles differ only in what the step may assume: packages the whole history into one statement.
A proof by induction must keep the inductive statement fixed. If the step needs a stronger fact than the stated hypothesis, strengthen the proposition and prove the new base cases; do not silently assume the missing fact.
Worked examples
Worked example 1.1.4
(One witness or a family of witnesses?)
Over the integers, is true: choose . But is false: for any proposed , choose . Its negation is , verified by the same choice. Merely swapping the quantifiers changes the mathematical problem.
Worked example 1.1.5
(An induction with visible algebra)
For , , where the empty sum at is . If the formula holds at , then adding the next term gives . The base case and this calculation prove all cases. The argument uses exactly the previous identity, without assuming the desired identity at .
Worked example 1.1.6
(Why strong induction matches factorization)
Every integer is a product of primes. The case holds. Assuming the claim for all integers from through , either is prime or with . In the latter case the hypothesis applies separately to , and multiplying their factorizations proves the claim. Knowing only the case would not directly control those two factors.
A statement's domain is part of its content
A formula alone is not yet a mathematical assertion. The domain determines which objects can serve as examples, witnesses and counterexamples. A statement about integer squares may be true while the same words about arbitrary real numbers are false. The claim that a square is at least the original number, for example, holds for nonnegative integers but fails for real numbers strictly between zero and one. Dropping a domain restriction changes the theorem, even if the algebraic expression remains identical.
When a proof introduces an arbitrary object, it must respect that domain and use only the stated hypotheses. The word arbitrary does not mean a conveniently selected test case. In a universal proof, the argument must work for every admissible object without making an additional unsupported choice. In an existence proof, by contrast, a convenient explicit construction is welcome, provided it satisfies every condition imposed on the witness.
Negation makes these obligations especially clear. To refute a universal claim, one counterexample suffices. To refute an existential claim, every possible witness must fail. Thus a handful of failed guesses cannot prove that no witness exists. A nonexistence proof needs a structural obstruction, such as parity, divisibility or a bound that applies uniformly to all candidates. This distinction will recur in counting arguments and algorithmic impossibility claims.
Implications and vacuous cases
An implication does not assert that its hypothesis occurs. If no object satisfies the hypothesis, the implication is true throughout the domain. This is why a universal claim about all elements of an empty set is true. There is no counterexample, because no element exists to meet the hypothesis and violate the conclusion. An existence claim over the same empty set is false because it has no witness.
Vacuous truth is useful rather than exceptional. It allows a statement about all earlier terms of a sequence to make sense at the first term, and a claim about all edges incident to an isolated vertex to be read without inventing special objects. The proof writer must still check whether the conclusion being sought is universal or existential. An empty construction may satisfy a condition on every selected object while failing a separate requirement that at least one object be selected.
Counterexample mode
The converse changes the assertion
The claim “if an integer is divisible by four, then it is even” is true. Its converse is false: the integer two is even but not divisible by four. The contrapositive, “if an integer is not even, then it is not divisible by four,” is equivalent to the original. To repair a proof that accidentally uses the converse, either supply the stronger hypothesis or find an argument that uses only the valid implication.
How many base cases are needed?
The number of base cases is dictated by the recurrence or proof step. If a proof establishes the next case from the immediately previous case, one valid start can propagate forward. If it establishes a case from the previous two, both initial cases must be supplied. A step that advances by two reaches only one parity class from a single starting point; a second starting point is needed to cover the other parity.
This can be expressed without informal propagation language. Consider the set of indices reachable from the proved starting cases using the allowed step. The conclusion is justified only at indices in this set. If the intended domain contains an index that cannot be reached, the proof has a gap. For strong induction, the usual formulation covers all earlier indices, but a particular argument may still need several small cases because the proposed decomposition does not exist for the smallest inputs.
As a concrete application, every integer at least twelve can be written as a nonnegative integer combination of four and five. The four initial values twelve, thirteen, fourteen and fifteen have such representations. Any larger integer is four more than a smaller integer still at least twelve. Strong induction therefore supplies the representation by adding one more four. A single base value would not justify the other residue classes, because adding four preserves the remainder modulo four.
Strengthening an inductive statement deliberately
Sometimes the desired conclusion is too weak to support its own next step. A standard response is to prove a stronger assertion that includes the extra information needed. This is legitimate only when the stronger assertion has its own proof, including its base cases. Adding an unsupported assertion to the induction hypothesis is equivalent to assuming part of the result.
For instance, a sequence proof may need a bound on two consecutive terms rather than one. Define a new predicate asserting both bounds together. In the step, the old second bound becomes the new first, and the recurrence proves the new second. This packages the exact information the recurrence needs. The method is the same as introducing a loop invariant in an algorithm: one tracks enough state to make the update provable.
An audit of any induction proof follows the same discipline. Identify the index being proved and list the earlier indices actually used. Check that each is strictly earlier and inside the domain of the hypothesis. Then inspect the smallest indices separately, where the decomposition or recurrence may not yet apply. Finally verify that no assertion at the current index was used before being proved. This audit locates hidden circularity and missing base cases.
From examples to a useful conjecture
Examples have a productive role before a proof: they can reveal a pattern, suggest the correct starting index, or expose a missing hypothesis. They can also test a proposed formula after it is derived. Their limitation is logical rather than practical: any finite table leaves unexamined infinitely many later inputs. A proof must supply a mechanism that covers those unexamined inputs.
A good counterexample is often more informative than a long list of confirming cases. When a conjecture fails, ask which assumption would prevent the failure. If a division step failed at zero, a nonzero hypothesis may repair it. If cancellation failed for a composite modulus, invertibility may be the missing condition. The repaired statement should then be proved from its revised hypotheses; excluding the first counterexample does not guarantee all other failures have been removed.
These habits explain why precise statements belong at the beginning of a proof rather than being reconstructed afterward. A statement records the exact promise the argument must fulfill. The proof records how each promise follows. Keeping those roles separate makes later generalization possible: one can inspect which hypotheses were used and which were merely convenient.
Common mistakes
Common mistake
(Checking cases is not an induction step)
Proving and checking is not an induction step. Conversely, the implication can be true for every even when all are false: an implication with false hypothesis says nothing about the conclusion's truth.
Common mistake
(Where the horse argument breaks)
The claim “all finite sets of horses have one color” has a familiar false induction: remove one horse at each end and compare the two smaller groups through a shared horse. The groups do not overlap when the original set has size . Thus the alleged step from size to size fails. Locate the exact failed hypothesis rather than merely reporting that the conclusion looks implausible.
Summary
Quantifier order records permitted dependence. Negation changes each quantifier while preserving that order. Induction proves infinitely many cases because a hypothetical least failure contradicts the step; the step and base cases must cover every index claimed.
Exercises
Quick check
(Prove that divides for every nonnegative integer .)
Use the identity .
Solution · Answer
At , is divisible by . If for an integer , then , also divisible by . Induction proves the claim for every stated index.
Quick check
(Negate the statement “for every integer there exists an integer such that ”. Decide the original claim and its negation.)
Keep both domains and the order of the quantifiers.
Solution · Answer
The negation is . It is false. For any integer , choose ; then . This choice proves the original statement and rules out every proposed bound in its negation.
Quick check
(Let and for . Prove that for every , and say how many base cases the step requires.)
The step uses the two previous terms.
Solution · Answer
Both base cases hold: and . Two are needed because the step proving the formula at uses it at and at ; with only checked, the step could not be applied even once. If the formula holds at and , then , and , so this is the formula at . For instance and .