Why do you need to show A(1) before proving A(n) by induction?

Question

My instructor stated that in order to have a valid proof by mathematical induction, you first have to show A(1) holds, and then assume A(n) to deduce A(n+2). Why is the first step necessary if we are going to assume A(n) though?

I get that showing A(1) is true suggests that A(n) might be, but that could very easily not be the case. Perhaps A(3) does not hold. So why logical benefit do we gain by proving A(1) before completing a more general proof by induction?

Answer 1

A proof by induction has two parts, and you have to prove each of them:

• $(i)\quad$ $A(n)$ implies $A(n+1)$, for all natural numbers $n$;

• $(ii)\quad$ $A(1)$ is true.

Together, these two facts imply that $A(n)$ is true for all natural numbers $n$. For example, to see $A(3)$ is true (given these two facts), we argue as follows:

• We know $A(1)$ is true by $(ii)$.

• Since $A(1)$ is true, $A(1+1)$ is also true by $(i)$.

• Since $A(1+1)$ is true, $A(1+1+1)$ is also true by $(i)$.

• So $A(3)$ is true!

However, we need both pieces for induction to work. For example, let $A(n)$ be the property "$n=n-3$." Then:

• Clearly (for any $n$) if $A(n)$ is true, then $A(n+1)$ is also true: since $A(n)$ means $n=n-3$, so $n+1=n-3+1$, so $n+1=(n+1)-3$ - but this is just $A(n+1)$!

• However, $A(n)$ is in fact false for every $n$.

Answer 2

What you're really showing in the step case is that if $A(n)$ is true, then $A(n+1)$ is true. So you're showing $A(n) \implies A(n+1)$. With just this, you don't know if your statement is true for any actual values of $n$. When you prove it for a value, for example $A(1)$, that together with $A(n) \implies A(n+1)$ gives you $A(1) \implies A(2) \implies A(3) \implies ...$ so you can just follow that chain of implications and your statement is true for any $n \geq 1$

For example: The induction step of "All integers are of the form $\frac{2k+1}{2}$ for some integer $k$" is true since $\frac{2k+1}{2} + 1 = \frac{2(k+1)+1}{2}$. You can't verify it for any value of $n$ though, since no integers are actually of that form.

Answer 3

The reason proof by induction works is because of the well-ordering principle (WOP) of the natural numbers. The well-ordering principle says any nonempty subset of the natural numbers has a least element. It turns out that WOP is logically equvalent to the principle of mathematical induction (PMI). This is fairly straightforward to prove as follows:

$WOP\leftarrow PMI$ Suppose $S$ has no minimal element. Then $ n = 1 \notin S$, because otherwise $n$ would be minimal. Similarly $n = 2 \notin S$, because then $2$ would be minimal, since $n = 1$ is not in $S$. Suppose none of $1, 2, \cdots, n$ is in $S$. Then $n+1 \notin S$, because otherwise it would be minimal. Then by induction $S%$ is empty, a contradiction.

$WOP\leftarrow PMI$ Suppose $P(1)$ is true, and $P(n+1)$ is true whenever $P(n)$ is true. If $P(k)$ is not true for all integers, then let $S$ be the non-empty set of $k$ for which $P(k)$ is not true. By well-ordering $S$ has a least element, which cannot be $k = 1$. But then $P(k-1)$ is true, and so $P(k)$ is true, a contradiction.

So clearly WOP is true iff PMI is true. A lot of teachers don't like going through this in basic rigorous mathematics courses, which to me is a big mistake. Students need to understand why induction works,it's a critical method of proof.

How's that?