Free Version
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:

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

...and:

prove that it must then follow that $P(k+1)$ is true, in other words you prove $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$.

A

It's OK to leave out $P(0)$, $P(1)$ and just start by checking $P(2)$, and follow by proving $P(k)$ implies $P(k+1)$, for all $k\ge 2$.

B

It's OK to go backwards: if I prove $P(k)$ implies $P(k-1)$, for any $k$, then I can work back down to $P(i)$ being true for $0\le i\le k$.

C

We can make the whole thing shorter by checking $P(0)$ and assuming $P(n)$ is true for all $n$.

D

If we check $P(0)$ and make the stronger assumption $P(i)$ is true for $0\le i\le k$, then we can deduce $P(k+1)$ at once (without a proof) as $k$ is arbitrary.

E

If it turns out that $P(20)$ is easier to prove than $P(0)$, I can start by checking $P(20)$, and follow by proving $P(k)$ implies $P(k+1)$, for all $k\ge 20$, and follow this by proving $P(k)$ implies $P(k-1)$ for $1\le k\le 20$. Alternatively, we can check $P(k)$, $0\le k\le 19$, directly or on a calculator.