What is the purpose of the first test in an inductive proof?

Learning about proof by induction, I take it that the first step is always something like "test if the proposition holds for $n = \textrm{[the minimum value]}$"

Like this:

Prove that $1+2+3+...+n = \frac{n(n + 1)}{2}$ for all $n \ge 1$.

Test it for $n = 1$:

$$n = \frac{n(n + 1)}{2} \implies 1 = \frac{2}{2}\textrm{, which holds.}$$

* The rest of the proof goes here *

So, I do it all the time (like a standard). But I never really thought about why. Why do I do such test? I can see that if the test does not hold, it cannot be proven by induction, I guess. But is there another reason we do this?

Solution 1:

Imagine a pond with an infinite linear progression of lily pads. You have a frog who, if he hops on one pad, he is guaranteed to hop on the next one. If he hops on the first pad, he'll visit them all. But if he never makes the first lilypad, all bets are off.

Solution 2:

We have to test the "base case" because otherwise we could "prove" things by induction that aren't true. For instance: let's "prove" that the sum of the first $n$ even numbers is odd. Certainly if $S = 2+4+\cdots+2n$ is odd, then $2+4+\cdots+2n+(2n+2) = S + 2n+2$ is also odd, since an even number plus an odd number is odd.

So by "induction", the sum of the first $n$ even numbers is odd.

Of course this is false, and the reason we got something false is that we didn't verify that the base case holds (it doesn't).

Solution 3:

The induction proof is, in a metaphor, a game of dominos. Your goal is to make the pieces fall over, where if the $n$th domino falls, so will the $(n+1)$st. However, if you don't knock down the beginning domino, none may fall over.

An example of what goes wrong without appropriate base case...

Claim: For all $n \in \Bbb{N}=\{1, 2, 3, ...\}$, $n \geq 1000$.

Proof without base case: If $n \geq 1000$ the $n+1 > n \geq 1000$.

An example of what goes totally wrong...

Claim: For all $n \in \Bbb{N}$, $n > n$.

Proof without base case: If $n > n$, then by adding $1$ to both sides we see $n+1>n+1$. Therefore, by baseless induction, we've "proved" the claim.

Solution 4:

Let's take your example and modify it slightly:

Prove that $1+2+\cdots+n=\frac{n^2+n+1}{2}$ for all $n\ge 1$.

Let $P(n)$ be the statement "$1+2+\cdots+n=\frac{n^2+n+1}{2}$". Then you need to show that $P(n)$ implies $P(n+1)$. Substituting $n+1$ for $n$ we find that $$ P(n+1) =\frac{n^2+3n+3}{2} $$ Now let's establish the inductive step, that is, that we can use $P(n)$ to establish $P(n+1)$. $$ \begin{align} 1+2+\cdots+n+(n+1) &=(1+2+\cdots+n)+(n+1)\\ &= \frac{n^2+n+1}{2}+(n+1)&\text{by the inductive hypothesis}\\ &= \frac{n^2+3n+3}{2}&\text{as required} \end{align} $$ So we can conclude the highlighted statement. Sort of. Except for the fact that $P(1)$, the base case, sinply isn't true, since it asserts that $$ 1=\frac{1^2+1+1}{2} $$ As has been noted before, if you can't get the first domino to topple, none of the rest will, either.

Solution 5:

Let's prove that all objects in the universe are the same color. We'll prove by induction that given any set of $n$ objects, all of them are the same color.

Inductive step: Given a set $\{1, ... n+1\}$ of objects, we know that $\{1, ... n\}$ are all the same color $c_1$, and that $\{2, ... n+1\}$ are all the same color $c_2$. But if $n\geq 2$ these two sets overlap, so $c_1$ and $c_2$ must be the same. Therefore $\{1, ... n+1\}$ are all the same color.

Base case: If $n=1$, it's obvious. If $n=2$, then the two elements are the same color because... er...

Base case left as an exercice to the reader.