Moderate# Proof by Induction: What is it? What are Common Misconceptions?

ABSALG-QIEKNX

The idea of proof by induction is as follows.

Suppose that you want to prove that a statement $P(n)$ is true for all integers $n\ge 0$.

You start by

proving $P(0)$ is true

...then you:

assumethat $P(k)$ is true for some $k\ge 0$

...and:

provethat it must then follow that $P(k+1)$ is true, in other words youprove$P(k)$ implies $P(k+1)$.

The idea is that, as you know $P(0)$ is true, since you checked it, you can use the $P(k)$ to $P(k+1)$ step to prove that $P(1)$ is true, then use the $P(k)$ to $P(k+1)$ step again to prove $P(2)$ is true and so on, and thereby you prove $P(n)$ is true for all $n$.

**Which one of the following is not a mistake?**

You should assume, as above, that you are trying to prove a formula or statement $P(n)$ for **ALL** integers $n\ge 0$.