Lesson 14 of 48
Proof technique
Contradiction and induction, the two workhorses.
Contradiction proves a thing by making its opposite explode. Induction proves infinitely many statements with two finite ones. Recursion at lesson 25 is induction wearing a different hat.
Do this
Produce a correct proof by contradiction and a correct proof by induction, each on a claim you have not been shown worked. For the induction, state the base case and the inductive step explicitly.
The question that unlocks the next lesson
An induction proof shows P(k) ⇒ P(k+1) but never checks P(1). What is wrong?
- ANothing — the implication is the whole proof
- BWithout a base case, the chain is never started, so nothing is proved
- CThe step should be P(k) ⇒ P(k+2)
- DIt proves the statement only for even numbers