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

Last edited: 2024-09-13