COMP2121 Chap.2 Proof Methods and Mathematical Induction
Proof Methods and Mathematical Induction
Choosing a proof shape
A direct proof assumes the hypothesis and derives the conclusion. The contrapositive assumes the conclusion fails and shows the hypothesis fails.
Contradiction assumes the negation and reaches something impossible, and proof by cases splits a disjunctive hypothesis into parts that together cover everything.
Induction and recursion
Induction proves a statement for every positive integer from a basis and an inductive step, and strong induction lets the step use every earlier case.
Recursive algorithms are proved correct the same way, and their recurrences, such as the Towers of Hanoi count, are solved by unrolling.
How the solutions present a proof
The course's own model answers open by naming the method, state precisely what is assumed, and end with the claim written in words.
In a proof by contradiction the assumption is the negation of the whole statement, and the contradiction is pointed out explicitly rather than left for the reader to spot.
For divisibility and parity arguments, the integers are written in the form 2k or 2k plus 1, or with a stated remainder, before any algebra starts.
Spotting a faulty induction
Exercises that present a wrong proof and ask for the error are a regular question type.
The usual flaw is an inductive step that silently needs two overlapping groups, or a property of k plus 1 objects that only holds once the number of objects is large enough. The familiar claim that all horses share one colour fails exactly at the passage from one horse to two, where the two groups of k objects no longer overlap. Finding the smallest value where the step breaks is the complete answer.
What this chapter covers
- 01
Direct proof
- 02
Contrapositive
- 03
Proof by contradiction
- 04
Proof by cases
- 05
Weak and strong induction
- 06
Recurrences and faulty proofs
Worked example · free
Push truth along an induction chain
- 1State and check the basis case n equals 1.
- 1State the induction hypothesis for n equals k.
- 3Derive the claim for k plus 1 from the hypothesis.
Key terms
- Contrapositive
- The implication from not q to not p, which is equivalent to p implies q.
- Induction hypothesis
- The assumption that the statement holds for k, used to prove it for k plus 1.
- Strong induction
- Induction whose step may assume the statement for every value up to k.
- Recurrence
- An equation defining each term of a sequence from earlier terms.
Proof Methods and Mathematical Induction FAQ
When should I use the contrapositive?
Use it when the negated conclusion gives a usable formula and the hypothesis does not, such as proving that n is odd from a property of an expression in n. Assuming the conclusion fails often produces the parity or remainder you need.
What makes an induction proof wrong?
Usually an inductive step that silently needs a case the basis never proved, or a hypothesis applied to an object that does not satisfy its conditions. Check the smallest value the step is used on.
Is a proof by contradiction the same as a contrapositive proof?
No. A contrapositive proof ends by showing the hypothesis fails. A contradiction proof assumes the hypothesis and the negated conclusion together, then derives a statement that cannot be true.
How many base cases does strong induction need?
Enough to cover every value the inductive step cannot reach on its own. If the step for k plus 1 uses the cases k and k minus 1, two consecutive base cases are needed, otherwise the chain of implications never starts.
How is a recursive algorithm proved correct?
By induction on the size of the input. The basis checks the smallest inputs the algorithm handles directly, and the step assumes the recursive calls return correct results on smaller inputs, then shows the combining step produces the correct answer for the larger one. Recurrences for running time are solved by unrolling.
Exam move
For each proof method, keep one model you can reproduce from memory, with the first and last lines written out. Practise induction on sums, divisibility and inequalities, labelling every part. When you meet a false proof, write the faulty line and a one-sentence reason, which is the form the course solutions use.
Each week, take one false proof from the exercises and write the exact line where it fails, with the smallest value that exposes the gap. Rehearse the closing sentence of each method too, since a proof that never states its conclusion leaves the reader to finish it.
Working through Proof Methods and Mathematical Induction in COMP2121? Sia is AskSia’s AI Computer Science tutor — ask any COMP2121 Proof Methods and Mathematical Induction question and get a clear, step-by-step explanation grounded in how COMP2121 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.