Discrete Mathematics for Computer Science

proof by induction

steps with example

variable $n$
property $P (n)$
base case $P (0)$
induction hypothesis
- weak induction
  assume $P (n - 1)$ is true
- strong induction
  assume $P (k)$ is true $\forall k < n$
induction step
induction hypothesis $\Rightarrow P (n)$ is true