Mathematical Induction and Recursive Definitions

principle of induction

prove P(n) is true for all positive integers n

basis step

show P(1) is true (or P(b) for starting point b)

inductive step

show P(k) → P(k + 1) is true for arbitrary k
assumption P(k) is inductive hypothesis

analogies:

infinite ladder (rung 1, rung k to k + 1)

dominoes (domino 1 falls, k knocks k + 1)

(just a reminder)

recursive step

rule for finding value from smaller integers