Proof Techniques and Mathematical Induction

Introduction and Context

Computer applications depend on claims that must be trusted: an algorithm terminates, a data structure maintains an invariant, a security protocol satisfies a condition, or a recursive program produces the intended result. Intuition and testing are useful, but neither establishes universal truth. A mathematical proof is a logically valid argument showing that a conclusion follows from accepted definitions, assumptions, and previously established results.

Proof writing is therefore not merely an academic exercise. It develops the ability to specify assumptions, reason systematically, detect hidden cases, and communicate why a program or algorithm is correct. This chapter introduces the principal proof techniques used in discrete mathematics and computer science: direct proof, contrapositive proof, contradiction, proof by cases, existence and uniqueness proofs, counterexamples, mathematical induction, strong induction, and loop invariants.

Learning Objectives

After studying this chapter, you should be able to:

• distinguish definitions, conjectures, theorems, lemmas, and corollaries;
• construct direct, contrapositive, contradiction, cases, existence, and uniqueness proofs;
• disprove universal claims using counterexamples;
• apply ordinary and strong mathematical induction;
• use invariants to reason about iterative algorithms;
• identify assumptions, boundary cases, and logical gaps in proofs;
• connect mathematical proof techniques with software verification and professional practice.

1. The Structure of Mathematical Reasoning

A proposition is a declarative statement that is either true or false. For example, “Every even integer is divisible by 2” is a proposition. A variable statement such as “x is greater than 3” becomes a proposition only after a value or quantifier is supplied.

A proof begins with premises and ends with a conclusion. Each step must follow from a definition, an assumption, an established theorem, or a valid rule of inference. Common logical forms include:

• P → Q: if P, then Q;
• P ∧ Q: P and Q;
• P ∨ Q: P or Q;
• ¬P: not P;
• ∀x P(x): for every x, P(x);
• ∃x P(x): there exists an x for which P(x) holds.

A theorem is a statement proved to be true. A lemma is an auxiliary result used in proving another result. A corollary follows relatively directly from a theorem. A conjecture is a proposed statement whose truth has not yet been established.

Definitions are especially important in computer applications. An integer n is even if there exists an integer k such that n = 2k. An integer n is odd if there exists an integer k such that n = 2k + 1. These definitions should be used explicitly rather than replaced by informal impressions.

A valid proof is not the same as an example. Showing that a statement works for 2, 4, and 6 does not prove that it works for every even integer. Conversely, a single valid counterexample is enough to disprove a universal claim.

2. Direct Proofs

A direct proof is the natural method for proving a conditional statement P → Q. Assume P, transform the assumption through valid steps, and derive Q.

Theorem: The sum of two even integers is even

Let a and b be even integers. By definition, there exist integers r and s such that a = 2r and b = 2s. Therefore,

Since r + s is an integer, a + b has the form 2 times an integer. Hence a + b is even.

The proof depends on the domain: r and s must be integers. The same algebra over arbitrary real numbers would not establish evenness, because evenness is an integer property.

Direct proof strategy

1. State the assumptions clearly.
2. Replace concepts using their definitions.
3. Perform justified algebraic or logical steps.
4. Reach the exact form required by the conclusion.
5. State the conclusion explicitly.

Direct proofs are common in programming specifications. If an input satisfies a precondition, a proof may show that each transformation preserves the required postcondition.

3. Contrapositive Proofs

The contrapositive of P → Q is ¬Q → ¬P. A statement and its contrapositive are logically equivalent. Sometimes proving the contrapositive is easier than proving the original implication.

Theorem

If n² is even for an integer n, then n is even.

A direct proof would need to derive that n is even from the form of n². The contrapositive is simpler:

If n is not even, then n is odd. Thus n = 2k + 1 for some integer k. Then

Therefore n² is odd, so it is not even. The contrapositive is true, and consequently the original theorem is true.

Contrapositive reasoning is particularly useful when the negation of the conclusion has a clear structural form. In computing, a claim such as “If a file is encrypted, unauthorized users cannot read it” may be difficult to prove directly because “cannot read” is complex. A formal security argument may instead characterize what would have to occur if unauthorized reading were possible.

4. Proof by Contradiction

To prove a proposition P by contradiction, assume that P is false and show that this assumption produces an impossibility. The contradiction may conflict with a known theorem, a definition, or two mutually incompatible conclusions.

Theorem: √2 is irrational

Assume, for contradiction, that √2 is rational. Then it can be written as √2 = p/q, where p and q are integers, q ≠ 0, and the fraction is in lowest terms. Squaring gives

Thus p² is even. By the theorem proved above, p is even, so p = 2r for some integer r. Substitution gives

Hence q² is even and q is even. Both p and q are therefore divisible by 2, contradicting the assumption that p/q was in lowest terms. Consequently, √2 is irrational.

Contradiction is powerful but should be used carefully. The contradiction must genuinely follow from the negated claim; merely obtaining an unexpected result is not enough. Proofs by contradiction are common in impossibility results, security arguments, and demonstrations that an algorithm cannot satisfy incompatible requirements.

5. Proof by Cases

A proof by cases divides the domain into exhaustive possibilities and proves the conclusion in each case. The cases must cover all possibilities, and they should not introduce unsupported assumptions.

Example: For every integer n, n² is even or odd

Every integer is either even or odd. If n is even, then n = 2k and

so n² is even. If n is odd, then n = 2k + 1, and the calculation above shows that n² is odd. These two exhaustive cases establish the claim.

Cases can be based on sign, parity, ranges, character types, or control-flow alternatives. In software, a proof may separately analyze an empty input, a singleton input, and an input with at least two elements. Boundary cases deserve particular attention because they often expose incorrect algorithms.

6. Existence and Uniqueness Proofs

An existence claim has the form ∃x P(x). It asserts that at least one object has a specified property.

Constructive existence

A constructive proof provides an explicit object. For example, there exists an even prime: the integer 2 is prime and even.

Nonconstructive existence

A nonconstructive proof establishes that an object must exist without identifying it. Such proofs are mathematically valid, although constructive proofs are often more useful in computing because they can suggest an algorithm.

Uniqueness

To prove that an object is unique, prove two parts:

1. existence: at least one object satisfies the property;
2. uniqueness: any two objects satisfying the property are equal.

Theorem: An integer has a unique remainder modulo m

Let m be a positive integer. For every integer a, there exist unique integers q and r such that

Existence is supplied by the division algorithm. For uniqueness, suppose

a = mq + r and a = mq' + r' with both remainders between 0 and m − 1. Subtracting gives

The right side lies strictly between −m and m. The only multiple of m in that interval is 0. Hence r' − r = 0, so r = r', and then q = q'.

Uniqueness matters in hashing, modular arithmetic, parsing, database keys, and canonical representations. If a representation is not unique, comparison and storage operations become ambiguous.

7. Counterexamples and Disproof

A universal statement has the form ∀x P(x). To disprove it, it is sufficient to find one x for which P(x) is false. This is a counterexample.

Claim: “Every prime number is odd.” The counterexample is 2, which is prime and even. Therefore the claim is false.

A counterexample must satisfy the original domain restrictions. If a claim concerns positive integers, a negative integer is irrelevant. A near miss is not a counterexample unless it meets all stated assumptions.

Counterexamples are valuable in software engineering. Testing an algorithm on carefully selected edge cases can quickly refute an incorrect universal claim, although passing tests cannot prove correctness for all inputs. Useful test categories include empty inputs, minimum and maximum values, duplicate values, already sorted data, reverse order, and values causing overflow.

8. Mathematical Induction

Mathematical induction proves a statement P(n) for every integer n ≥ n₀. It relies on two components:

1. Base case: prove P(n₀).
2. Inductive step: assume P(k) for an arbitrary k ≥ n₀ and prove P(k + 1).

The assumption P(k) is the inductive hypothesis. The variable k must be arbitrary, not a specially selected value.

Theorem: Sum of the first n positive integers

For every integer n ≥ 1,

Base case: when n = 1, the left side is 1 and the right side is 1(2)/2 = 1.

Inductive step: Assume the formula holds for k ≥ 1:

Then

This is the required formula with n = k + 1. Therefore the statement holds for all n ≥ 1.

Induction resembles a row of falling dominoes: the base case starts the process, and the inductive step establishes the link from every row to the next. Both parts are essential. A proof of the inductive step without a valid base case proves nothing about the intended starting domain.

Choosing the induction variable

The induction variable should measure progress through the domain or algorithm. For recursive algorithms, it is often the input size. For a statement about powers, sequence positions, or tree height, the natural measure may be exponent, index, or height. The measure must be well-founded: it should not decrease indefinitely through nonnegative integers.

9. Strong Induction

In ordinary induction, the inductive step assumes only P(k). In strong induction, the step assumes all earlier statements P(n₀), P(n₀ + 1), …, P(k) and proves P(k + 1). Strong induction is useful when the next case depends on several earlier cases rather than only the immediately preceding one.

Theorem: Every integer n ≥ 2 is prime or can be expressed as a product of primes

Base case: n = 2 is prime.

Inductive step: Let k ≥ 2 and assume the claim for every integer from 2 through k. Consider k + 1. If it is prime, the claim holds. If it is composite, then k + 1 = ab where 2 ≤ a ≤ k and 2 ≤ b ≤ k. By the strong inductive hypothesis, a and b are each prime or products of primes. Combining their factorizations gives a product of primes for k + 1.

Strong induction is closely related to recursive decomposition. A recursive algorithm may solve a problem of size n by solving subproblems of several smaller sizes. To prove correctness, it is then natural to assume correctness for every smaller size.

10. Invariants and Algorithm Verification

An invariant is a property that remains true throughout a process. In loop verification, a loop invariant is established before the first iteration, preserved by every iteration, and used after termination to prove the postcondition.

A standard proof has three parts:

• Initialization: the invariant is true before the loop begins.
• Maintenance: if it is true before an iteration, it remains true afterward.
• Termination: when the loop stops, the invariant combined with the exit condition implies the desired result.

Worked example: sum of an array

Consider the pseudocode:

sum ← 0
for i ← 0 to n − 1 do
    sum ← sum + A[i]
return sum

Assume A contains n elements indexed from 0 through n − 1, and arithmetic does not overflow. A suitable invariant before iteration i is

For i = 0, the sum over the empty prefix is 0, so initialization holds. During iteration i, the algorithm adds A[i], producing the sum of the first i + 1 elements; maintenance holds. After the final iteration, i = n, and the invariant states that sum equals every element of A. Thus the algorithm is correct.

A loop invariant should be strong enough to support the postcondition but simple enough to prove. A statement that is true but unrelated to the desired result is not useful. Invariants also appear in binary search, sorting, graph traversal, resource accounting, and concurrent-system reasoning.

11. A Detailed Applied Case: Verifying Binary Search

Background

Binary search locates a target value in a sorted array. It repeatedly compares the target with the middle element and discards the half that cannot contain the target.

Problem

Show that binary search is correct: if the target occurs in the sorted array, the algorithm returns a valid position; otherwise, it reports absence. Also explain why the algorithm terminates.

Assumptions

Let A be sorted in nondecreasing order. The search interval is represented by inclusive indices low and high. The algorithm maintains the possibility that the target lies in the current interval.

Invariant

At the start of each iteration, if the target occurs anywhere in A, then it occurs within indices low through high. Equivalently, no index outside the current interval can contain the target under the deductions already made.

Analysis and approach

Initially, low = 0 and high = n − 1, so the interval includes every valid index. If A[mid] is the target, returning mid is correct. If A[mid] is less than the target, sortedness implies that no index at or below mid can contain the target; setting low = mid + 1 preserves the invariant. If A[mid] is greater than the target, no index at or above mid can contain it; setting high = mid − 1 preserves the invariant.

A useful termination measure is the interval length

Whenever the algorithm does not return, the new interval is strictly smaller than the old interval. Since L is a nonnegative integer, it cannot decrease forever. Eventually the interval is empty or the target is found. If the interval is empty, the invariant implies that the target does not occur anywhere in A, so reporting absence is correct.

Outcome and learning points

Binary search illustrates three proof ideas together: cases for the comparison outcomes, an invariant for correctness, and a decreasing nonnegative measure for termination. Its running time is logarithmic in the array length under the usual random-access model, but correctness depends on sorted input and careful boundary handling. An implementation that uses an incorrect midpoint calculation or inconsistent inclusive/exclusive bounds may fail despite having the right high-level idea.

This case is illustrative rather than a substitute for testing. Testing can reveal implementation errors; the invariant explains why a correct implementation works for every permitted input.

12. Common Errors and Best Practices

Common errors

• proving several examples instead of a universal statement;
• using the conclusion as an unstated premise;
• confusing the converse Q → P with the original implication P → Q;
• omitting the base case in induction;
• assuming the inductive statement for a specific k rather than an arbitrary k;
• using cases that are not exhaustive;
• presenting an object without proving it satisfies the required property;
• claiming uniqueness after proving only existence;
• selecting a loop invariant that is not preserved;
• ignoring domain restrictions, overflow, empty inputs, or termination.

Best practices

State the domain and assumptions before beginning. Use definitions explicitly. Name the proof technique when it clarifies the structure. Separate the inductive hypothesis from the claim being proved. For algorithms, specify preconditions, postconditions, invariants, and termination measures. Prefer a short proof with justified steps to a long proof containing unexplained algebra. Finally, review the argument for boundary cases and hidden dependence on machine limitations.

13. Professional and Contemporary Relevance

Formal reasoning supports software verification, compiler correctness, cryptographic protocol analysis, database integrity, distributed systems, and safety-critical applications. Automated theorem provers and proof assistants can check formal arguments, while static analyzers use invariant-like reasoning to identify possible errors. AI-assisted programming can generate plausible code and even suggested proofs, but generated claims require human scrutiny: assumptions may be missing, edge cases overlooked, or a proof may contain a circular step. Responsibility for correctness remains with the developer or analyst.

Proof techniques also support governance and auditability. A documented argument makes it possible to inspect why a system satisfies a requirement, what assumptions it depends on, and where its guarantee ends. This distinction between proven properties and empirical performance is essential when software affects privacy, safety, finance, or access to services.

Chapter Summary

A proof is a logically valid argument from assumptions and definitions to a conclusion. Direct proofs derive the conclusion from the hypothesis; contrapositive proofs establish ¬Q → ¬P; contradiction assumes the negation and derives impossibility; and case-based proofs handle exhaustive alternatives. Existence proofs establish that an object is available, while uniqueness proofs show that no two distinct objects satisfy the same specification. A single valid counterexample disproves a universal statement.

Mathematical induction consists of a base case and an inductive step. Strong induction allows the step to use all earlier cases and is well suited to recursive decompositions. Loop invariants apply the same logical pattern to iterative algorithms: initialization, maintenance, and termination. Binary search demonstrates how cases, invariants, and a decreasing measure combine to prove algorithmic correctness. In professional computing, these techniques complement testing, clarify assumptions, support verification, and expose the limits of a system’s guarantees.

Key Terms

Proposition: A declarative statement that is either true or false.

Premise: A statement assumed or previously established in an argument.

Theorem: A proposition supported by a valid proof.

Lemma: An auxiliary result used in proving a larger result.

Corollary: A result that follows directly from a theorem.

Conjecture: A proposed statement not yet proved or disproved.

Direct proof: A proof that derives the conclusion directly from the hypothesis.

Contrapositive: The logically equivalent form ¬Q → ¬P of P → Q.

Contradiction: An impossible conclusion obtained from an assumption and used to establish its negation.

Proof by cases: A proof that establishes a claim separately for exhaustive alternatives.

Existence proof: A proof that at least one object satisfies a property.

Uniqueness proof: A proof that at most one object satisfies a property.

Counterexample: An instance that falsifies a universal claim.

Mathematical induction: A method using a base case and an inductive step.

Inductive hypothesis: The assumed statement used in the inductive step.

Strong induction: Induction in which all earlier cases may be assumed.

Invariant: A property preserved during a process or algorithm.

Precondition: A requirement assumed before an algorithm executes.

Postcondition: A property expected after execution.

Termination measure: A nonnegative quantity that decreases to establish termination.

Review Questions

5 Short Answer Questions

1. What is the difference between a theorem and a conjecture?
2. State the contrapositive of P → Q.
3. What two components are required for ordinary mathematical induction?
4. What is a counterexample, and why is one sufficient to disprove a universal claim?
5. Name the three principal obligations for proving a loop invariant.

5 Long Answer Questions

1. Construct a direct proof that the sum of two odd integers is even.
2. Prove by contrapositive that if n² is odd for an integer n, then n is odd.
3. Explain proof by contradiction and reconstruct the proof that √2 is irrational.
4. Describe ordinary induction and strong induction, and give a computing-related situation suited to each.
5. Explain the binary-search invariant, including initialization, maintenance, termination, and the role of sortedness.

3 Analytical / Application Questions

1. A program claims to return the maximum element of every nonempty array. Identify a suitable loop invariant and explain how it proves correctness.
2. Analyze the claim “Every integer greater than 1 is prime or even.” Determine whether it is true; if false, provide a counterexample and explain why it works.
3. Design a proof plan for a recursive algorithm that computes factorial. Specify the induction variable, base case, inductive hypothesis, and inductive step.

Multiple Choice Questions with Answers

Question 1

Which proof method establishes P → Q by proving ¬Q → ¬P?

A. Direct proof

B. Contrapositive proof

C. Proof by cases

D. Existence proof

Correct Answer: B. Contrapositive proof

Question 2

What is sufficient to disprove a statement of the form ∀x P(x)?

A. A proof of P for one value

B. Several confirming examples

C. One valid counterexample

D. A contradiction unrelated to x

Correct Answer: C. One valid counterexample

Question 3

In an induction proof, what does the inductive hypothesis assert?

A. The conclusion is false for k

B. P(k) holds for an arbitrary permitted k

C. P(k + 1) holds without assumptions

D. Only the base case holds

Correct Answer: B. P(k) holds for an arbitrary permitted k

Question 4

Which condition is required for a proof of uniqueness?

A. At least one object exists and any two such objects are equal

B. The object is computable in constant time

C. The proposition has a counterexample

D. All possible objects are different

Correct Answer: A. At least one object exists and any two such objects are equal

Question 5

If n = 2k + 1 for an integer k, what can be concluded?

A. n is even

B. n is prime

C. n is odd

D. n is negative

Correct Answer: C. n is odd

Question 6

Which loop-verification obligation shows that an invariant remains true after one iteration?

A. Initialization

B. Maintenance

C. Termination

D. Specification

Correct Answer: B. Maintenance

Question 7

Why is strong induction appropriate for the prime-factorization theorem?

A. The next case may depend on multiple smaller cases

B. It eliminates the need for a base case

C. It applies only to real numbers

D. It proves statements without assumptions

Correct Answer: A. The next case may depend on multiple smaller cases

Question 8

What assumption is essential for the standard binary-search correctness argument?

A. The array contains distinct values only

B. The array is sorted

C. The array length is prime

D. The target is always present

Correct Answer: B. The array is sorted

Question 9

Which statement correctly describes a direct proof?

A. Assume the conclusion and derive the hypothesis

B. Assume the negation and derive an impossibility

C. Assume the hypothesis and derive the conclusion

D. Test several examples and generalize

Correct Answer: C. Assume the hypothesis and derive the conclusion

Question 10

What does a decreasing nonnegative termination measure establish?

A. That every input is valid

B. That the process cannot continue indefinitely

C. That the output is unique

D. That the hypothesis is unnecessary

Correct Answer: B. That the process cannot continue indefinitely