The University of Hong Kong · FACULTY OF COMPUTER SCIENCE

COMP2121 Chap.2 Proof Methods and Mathematical Induction

- one subject, every graph, every model, every mark
6 Chapters5-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 2 of 11 · COMP2121

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.

In this chapter

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

Q [5 marks]. This practice weighting was set for revision and is not an official University marking scheme. Prove that 2 to the power n is greater than n for every positive integer n.
Induction pushes truth along a chain, one link at a time.Induction pushes truth along a chain, one link at a time. The first block is the basis P(1); each arrow is one use of the inductive step from P(k) to P(k+1); together they reach every positive integer, which is the falling-domino picture.P(1)P(k)P(k+1)basisinductive stepthen every P(n)
Induction pushes truth along a chain, one link at a time. The first block is the basis P(1); each arrow is one use of the inductive step from P(k) to P(k+1); together they reach every positive integer, which is the falling-domino picture.
  • 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.
For n equal to 1, two is greater than one. Assume 2 to the k exceeds k. Then 2 to the k plus 1 equals twice 2 to the k, which exceeds 2k, and 2k is at least k plus 1 because k is at least 1. So 2 to the k plus 1 exceeds k plus 1, and by induction the inequality holds for every positive integer.
Sia tip — Write Basis, Hypothesis and Step as labels so each part can be credited separately.
Glossary

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.
FAQ

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.

Study strategy

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.

A+Everything unlocked
Unlocks this Bible + all 52 of your subjects at The University of Hong Kong, plus 1,000+ more Bibles across the AskSia library.
Sia - your COMP2121 tutor, unlimited, worked the way the exam marks it
The full 5-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works