2 · Proof techniques · DAA Study Hub

Direct proof, contradiction, contrapositive and induction, with fill-in skeletons.

In one sentence

A proof is an argument that leaves no case uncovered. Four templates cover almost every proof in this course: direct, contradiction, contraposition and induction.

Everyday analogy

Direct proof = following road signs. Start from what you know and take one justified step at a time until you reach the claim.
Contradiction = a detective's alibi check. "Suppose the butler did it… then he was in two places at 9 pm. Impossible. So the butler didn't do it."
Contraposition = proving the reverse, negated. "If it rained, the ground is wet" is the same claim as "if the ground is dry, it didn't rain."
Induction = dominoes. Show the first domino falls (base case), and that any falling domino knocks over the next (inductive step). Then they all fall.

The four templates

Technique	To prove	You write
Direct	$P \Rightarrow Q$	Assume $P$ . … therefore $Q$ .
Contradiction	$S$	Assume not $S$ . … reach something impossible. So $S$ .
Contraposition	$P \Rightarrow Q$	Assume not $Q$ . … therefore not $P$ .
Induction	$S(n)$ for all $n \ge n_0$	Base: $S(n_0)$ . Step: assume $S(k)$ , prove $S(k+1)$ .
Counterexample	" $S$ is false"	Show one case where $S$ fails.

Strong induction

In the step you may assume $S(n_0), S(n_0+1), \dots, S(k)$ (all smaller cases), not just $S(k)$ . This is useful for recursive algorithms that split into pieces of any smaller size.

Induction as dominoes

Which technique? A decision picture

Contrapositive truth check

Statement	Form	Same truth as the original?
If $n$ is divisible by 4 then $n$ is even	$P \Rightarrow Q$	original (true)
If $n$ is odd then $n$ is not divisible by 4	$\neg Q \Rightarrow \neg P$	✅ contrapositive: equivalent, also true
If $n$ is even then $n$ is divisible by 4	$Q \Rightarrow P$	⚠️ converse: a different claim, and false ( $n = 6$ )

Common mistakes

Circular induction: assuming $S(k+1)$ and "showing" it's true.
Forgetting the base case. The steps alone don't start the dominoes falling.
Converse ≠ contrapositive. $Q \Rightarrow P$ is a different claim from $P \Rightarrow Q$ .
In contradiction, not saying what the contradiction is. Name the two facts that clash.

Mastery check

Solve without hints, then explain your choice of technique

Prove for all $n \ge 1$ : $3 + 7 + 11 + \dots + (4n - 1) = n(2n + 1)$ .

Your mastery check

Not started

Solve the problem above with no hints, close the page and explain it out loud. Tick each step honestly.

Solved the mastery check with no hints

Said it in one sentence

Explained it with my own analogy

Walked through the steps of my own hand trace

Explained why it is correct / how fast it is

Named a trap a beginner would fall into

Status

Tick all six steps to unlock “Mastered”.

Which study mode worked for you?

Saved in this browser onlySee all my progress →

References

Supplementary Notes: Proof techniques (6 pp.): direct proof (p. 1), contradiction and contraposition (p. 2), induction and strong induction (p. 3), worked induction examples incl. a recurrence (pp. 4–6).
04 Correctness & Space: Slide 17 (induction for recursive algorithms).
CLRS 4e Appendix A (induction used on summations) and §4.3 (induction used to verify recurrences).

2 · Proof techniques

Everyday analogyCopy Anchor Link

The four templatesCopy Anchor Link

Common mistakesCopy Anchor Link

Mastery checkCopy Anchor Link

✅ Answer

ReferencesCopy Anchor Link

On this page

Everyday analogy

The four templates

Common mistakes

Mastery check

References