A discrete algorithm works with objects that can be distinguished exactly: strings, subsets, integers, vertices, or finite sequences. A proof must say which objects are allowed, what the procedure promises, and why every permitted input receives the promised result. Logic and counting supply the language for those statements. They also expose mistakes that a handful of successful executions cannot detect.
Motivation
Suppose we want to count length- binary strings with no two consecutive ones. Enumerating all strings is possible for small , but it hides the structure. A better approach classifies a legal string by its ending and expresses the count in terms of smaller inputs. Before implementing that recurrence, we should know why the cases cover all strings, why they do not overlap, and what happens for the empty string.
The same obligations occur in a correctness proof. A loop that updates two counts may look plausible, yet an incorrect starting value can silently shift the entire sequence. An invariant connects the values stored by the program to the mathematical objects they are supposed to count. Induction then turns that connection into a proof for all input lengths.
These ideas begin with careful quantifiers. “For every input there exists a correct answer” is different from “there is one answer correct for every input.” Likewise, a condition that is sufficient for a string to be legal need not characterize all legal strings. Discrete mathematics rewards making such distinctions before a formula or algorithm becomes complicated.
Definitions
Definition 12.3.1
(Implication, converse and contrapositive)
A proposition is a statement with a truth value in the setting under discussion. The implication fails only when is true and false. Its contrapositive is equivalent; its converse need not be. A biconditional requires both directions.
Definition 12.3.2
(Quantifiers, negation and empty domains)
Quantifiers always have a domain. The negation of is ; the negation of an existence statement is a universal failure statement. Thus to refute a claim that every legal input terminates, one must exhibit a legal input with nontermination. A malformed input outside the specified domain does not refute that claim.
If the domain is empty, a universal statement over it is true: there is no domain element that violates the assertion. An existential statement over it is false because there is no available witness. This convention is forced by the negation rules, rather than an exception to them. It also explains why an algorithm's specification should state which inputs actually exist; a guarantee over an empty input class does not produce a solution object.
Definition 12.3.3
(Cardinality, bijection and partition)
For a finite set , write for its cardinality. A bijection proves by matching objects without omission or repetition. A partition splits a set into disjoint pieces whose union is the whole set. The sum rule counts a partition; the product rule counts successive choices when every earlier choice has the stated number of possible continuations.
Definition 12.3.4
(Loop invariant and correctness)
A loop invariant is a proposition about the input, program state and iteration index that holds before each iteration under the loop's precondition. To use it in a proof, establish initialization, preservation, and the consequence at exit. Partial correctness means that any terminating permitted execution gives the required answer. Total correctness adds termination, often proved by a nonnegative integer quantity that strictly decreases each iteration.
Definition 12.3.5
(Counting legal binary strings)
Let be the number of strings of length over containing no adjacent ones. There is one empty string, so , and the strings of length one give . The empty string is an object being counted; it is not the absence of a counting problem.
Theorem/proposition
Theorem 12.3.6
(Inclusion-exclusion for finite sets)
For subsets of a finite universe,
The subsets need not be disjoint, and all intersections in the formula are required.
Theorem 12.3.7
(A recurrence and its verified iterative computation)
For , the legal-string counts satisfy . The following procedure returns for every integer input : if , return one; otherwise start and repeat exactly times, using the old values on the right, then return .
The simultaneous-update convention is part of the algorithm. Replacing it by two assignments that accidentally reuse the newly updated first coordinate changes the procedure. A proof verifies one precise program, not a family of vaguely similar update rules.
Proof sketch or proof idea
Proof
(One element's net contribution)
For inclusion-exclusion, examine the contribution of one universe element . If it lies in none of the sets, it contributes zero on both sides. If it lies in exactly sets, it is counted in intersections of sets. Its net contribution on the right is
because . It therefore contributes exactly once on both sides. Summing over the finite universe proves the identity. The argument is local to an element, so it explains why subtracting pairwise intersections alone is insufficient when triple overlaps occur.
Proof
(Partition by the final symbol)
For the recurrence, partition legal length- strings by their final symbol. Those ending in zero arise uniquely by appending zero to a legal length- string. Those ending in one must end in the two-symbol block , and arise uniquely by appending that block to a legal length- string. Both constructions preserve legality, have inverse deletion operations, and their images are disjoint. Their counts add to the required total.
Proof X-ray
A recurrence needs both a partition and inverse constructions
It is not enough to describe two ways of making some legal strings. Deletion proves every target string comes from the proposed source, while unique reconstruction prevents double counting inside a case. The final-symbol partition prevents overlap between cases. These are the exact reasons the recurrence is an equality rather than merely an upper or lower bound.
Proof
(A state invariant for the loop)
For the program, number the performed updates by . The invariant after updates is . At , it holds by the two initial counts. If it holds after updates, the simultaneous assignment gives by the recurrence, so it is preserved. After updates, . The separate branch returns the correct initial value. The remaining update count is a nonnegative integer decreasing by one, establishing termination.
This proof illustrates ordinary induction through a program state. Strong induction has the same logical force, but permits the induction step to use every smaller input. For the recurrence itself, two previous counts are needed, so either use strong induction or package two successive claims into one invariant. A well-chosen statement can make the proof simpler without making its conclusion weaker.
Why induction reaches every case
Let be a proposition for integers . Ordinary induction requires a base proof of and, for an arbitrary , a proof of the implication . The hypothesis is temporary: it is available only inside that implication. The base starts a chain of valid implications, so every fixed integer at or above is reached after finitely many steps. Checking many individual cases, or proving the implication without its base, does not supply this chain.
Strong induction instead proves assuming for every integer with . At there are no such , so the step must establish the base without an assumption. In practice one may prove several initial cases separately and use the strong step only thereafter. The two forms have equal force: apply ordinary induction to , the assertion that holds for all . The strong step extends to .
The same reasoning can be expressed through the well-ordering principle: every nonempty set of nonnegative integers has a least member. If the strong step holds but some fails, choose the least member of the nonnegative set of offsets for failing indices, and let be its corresponding index. All earlier claims are true, so the step proves the allegedly failing claim, a contradiction. This argument explains why “choose the smallest counterexample” is valid here; a general set of integers without a lower bound need not have a least element.
Worked example 12.3.8
(Existence of a prime factorization by strong induction)
A prime is an integer greater than one whose only positive divisors are one and itself. Every integer is a product of one or more primes. At this is immediate. Suppose the assertion holds for every integer from through . If is prime, the one-factor product works. Otherwise for integers satisfying . The hypothesis factors both and into primes; concatenating the two finite products factors . Thus the claim follows by strong induction. For example, . This proves existence, not uniqueness of the factorization; uniqueness requires a further argument.
Counterexample mode
A step cannot repair missing starting cases
Consider the false claim : “ is even,” for all . The implication is true, and is true, but these reach only the even indices. The separate case would be needed to reach the odd indices, and it is false. A step that advances by two needs two starting cases to cover both parity chains; verifying just one is insufficient.
For algorithms, a strong-induction proof is useful when a recursive call can have several possible smaller input sizes. The proof must show each call's size is smaller and still in the stated domain, then use the induction hypothesis for those calls. To prove termination, also account for the control flow: if each invocation does finite local work, makes finitely many calls, and each call strictly decreases a nonnegative integer size, then no infinite call chain exists and the computation terminates. Correctness of a value conditional on return alone does not establish termination.
Worked examples
Worked example 12.3.9
(Quantifier order changes a claim)
For integers, is true: choose . The reversed statement is false: for a proposed , choose . To prove the first statement, the witness may depend on the universally chosen input. The second statement requires one fixed witness that works independently of every input. In algorithm language, an output computed from its input is different from one constant output claimed to solve every instance.
Worked example 12.3.10
(Counting with a double-counting correction)
Among integers from one through thirty, let be multiples of two and multiples of three. There are fifteen in , ten in , and five in the intersection, which consists of multiples of six. Thus twenty are divisible by two or three. Ten are divisible by neither. Adding fifteen and ten without subtracting five counts each multiple of six twice. The universe matters: changing the interval changes the floor counts even though the inclusion-exclusion identity stays the same.
Worked example 12.3.11
(Following a verified state rather than guessing a sequence)
For , start . The four updates give , , and , so the answer is thirteen. After the third update, the state means and ; it does not mean that both entries count length-five strings. Keeping that interpretation attached to the state prevents an off-by-one error when the stopping condition is translated into code.
The number of arithmetic additions in the iterative algorithm is linear in , but its values grow. We have , so they use at most binary digits. Under ordinary digit-by-digit addition, the total bit-operation cost is bounded by a constant times , hence by . The two-variable state uses bits. Describing it as “constant space” is appropriate only if one explicitly counts integer registers of unbounded size as single units. The distinction between arithmetic operations and bit operations will recur for number-theoretic algorithms.
Common mistakes
Common mistake
(Treating checked cases as a proof)
A few computed cases are useful checks but do not prove a universal statement. Conversely, a single legal counterexample disproves one. When an induction attempt fails, inspect the induction statement and base cases before altering the theorem. A recurrence that uses needs enough initial values to reach its first valid step.
Common mistake
(Misusing the product rule)
The product rule does not require choices to be probabilistically independent; it requires a counting statement about the number of continuations at each stage. If the number varies, sum the appropriate counts rather than multiplying one convenient value. Counting ordered selections and unordered subsets also gives different objects: forgetting order after counting requires a justified constant number of orderings per object.
Counterexample mode
Sequential assignment can invalidate a correct recurrence
If the update is implemented as followed by , the second instruction uses the new . Starting at gives instead of . The mathematical recurrence was correct; the implementation no longer matches it. A temporary variable or simultaneous assignment repairs the program.
Summary
Quantifiers specify who chooses each object and what may depend on the input. Partitions and bijections justify exact counts; inclusion-exclusion repairs overlaps. Induction proves recurrence identities, while an invariant ties those identities to changing program state. Termination and the chosen cost model are separate obligations that should remain visible alongside the answer.
Exercises
Quick check
(Negate the statement “For every integer , there exists a legal length- binary string ending in one.” Determine whether the statement is true.)
Negate the quantifiers one at a time, then test .
Solution · Answer
The negation is: there exists an integer such that every legal length- string fails to end in one. It is true at , because the only length-zero string is empty and has no final symbol. Thus the original universal claim is false. Restricting it to repairs it: the string consisting of zeros followed by one is legal.
Quick check
(Count integers from one through sixty divisible by at least one of two, three and five. Show all inclusion-exclusion terms.)
Add the single sets, subtract the pairs, then add back the triple.
Solution · Answer
The single-set counts are thirty, twenty and twelve. Pairwise intersections have sizes ten, six and four, from divisibility by six, ten and fifteen. The triple intersection has size two, from multiples of thirty. The union therefore has elements. The triple overlap is added back because the pairwise subtraction removed it too many times.
Exercise 12.3.12
(A program counts subsets of an -element set by starting and doubling exactly times. State and prove an invariant, including the case .)
Core
Solution(3)
- 1
State the invariant
Key step
After doublings, , the number of subsets of the first elements.
- 2
Check initialization and preservation
Initially and , and the empty set has exactly one subset. Adding a new element gives two disjoint possibilities for every old subset, including or excluding that element, so doubling preserves the interpretation.
- 3
Read off the exit value and termination
At the answer is . A counter of remaining iterations decreases by one each time, which proves termination, including immediate termination when .
Quick check
(Explain why legal strings ending in one are counted by only for , and compute .)
Check what deleting the final block requires.
Solution · Answer
For , a string ending in one is the single symbol one and has no preceding zero to delete. The two-symbol suffix argument therefore starts at . The base value handles that separate case. Using the verified recurrence, .
Exercise 12.3.13
(Prove by strong induction that every integer is a sum of distinct nonnegative integer powers of two. Find such a representation for .)
CoreProof
Solution(4)
- 1
Base case
.
- 2
Split off the parity
Key step
For , put and , so and is zero or one.
- 3
Apply the induction hypothesis to
is a sum of distinct powers of two. Doubling gives a representation of in which every exponent is at least one.
Because: The hypothesis covers every integer from to .
- 4
Add the remainder
∎If , append , which repeats no power. Hence the claim holds for . For example, . This argument proves existence, not uniqueness.