 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/discrete-mathematics-probability-and-continuous-mathematics/3/a/solution

Mathematical induction has two obligations. Establish the base case

S (0)

if the natural numbers start at zero, or

S (1)

if they start at one. Then prove the induction step: for an arbitrary natural

k

in the relevant range, assume

S (k)

and deduce

S (k + 1)

The base case starts the chain, and the step propagates truth to every subsequent natural number:

S (n_{0}) \land (\forall k \geq n_{0}, S (k) \Rightarrow S (k + 1)) ⟹ \forall n \geq n_{0}, S (n) .

 New to topics? Read the docs here!