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

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).

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.

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.

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.

To see why we need the base case, consider the following proposition:

Proposition: $\forall n \in \mathbb{N}, n = 0$

Proof: Assume this property holds for all $m \leq k$, and consider $n = k+1$.

= $k + 0$ (By inductive hypothesis noting that $1 \leq k$ is the smallest element of $\mathbb{N}$)

= $0 + 0$ (By inductive hypothesis)

= $0$

Hence the proposition holds for all $n \in \mathbb{N}$

QED

The problem with this proof is that I haven't actually explicitly shown there exists any integer in $\mathbb{N}$ that is equal to zero; moreover, and more importantly, I can never find such an integer. As such, given that I cannot establish the base case I cannot conclude the proposition is true.

Its common this question because the introduction to inductive proof is teached very axiomatically ("proof for n=1, then proof for n+1").

An inductive proof is where one proves that a set $A$ is inductive. A set $A$ is inductive if satisfies that

• $1\in A$
• $n\in A \Rightarrow n+1 \in A$

If $A$ is inductive, then $A=\mathbb N$

In your example, what it is really being proved is that $A=\{n\in N:1+2+3+...+n = \frac{n(n + 1)}{2}\}$ is inductive. That is, $A=\{n\in N:1+2+3+...+n = \frac{n(n + 1)}{2}\}=\mathbb N$

Notice that if $1\not\in A$ then we can not say that $1\in A \Rightarrow 1+1\in A$, hence $A\neq \mathbb N$

The first test assures that it will be true for the minimum value (could be $0, 1, 2$ or anything). The subsequent proof that you do proves that if it is true for any natural number, it will be true for the next number as well.

So, lets say $1+2+3+...+n=\frac {n(n+1)}{2}$ is true for $n=1$ (which it is), then if you can prove that if it is true for any natural number, it will be true for the subsequent one as well, then this will be true for 2 as well. If it true for 2, it will be true for 3 and so on..

The first test is simply a starting point, that's all.

The base case part of an inductive proof shows that the statement you are trying to prove holds for some number in the series, in your example,

Prove that $1+2+3+...+n=\frac{n(n+1)}{2}$ for all $n$ greater than or equal to $1$

the first number in your proof would be $1$. But you could also show that this sequence holds for all $n$ greater than or equal to $2$ and it would be a valid proof.

In the inductive step, we show that if the statement holds for some number $P(n)$, then the statement also holds for $P(n + 1)$, the next number in the series. In the above example, you already showed that the statement holds for $n = 1$, which is some number $P(n)$, therefore if we can show that the statement is also valid for $P(n + 1)$, then we would know that the statement is valid for every number greater than $1$ by the axiom of induction.

Take a look at this: We prove by induction that the number

$$8^n+73$$

Is divisible by $7$ for every natural number $n$. Suppose that $8^n+73$ is divisible by $7$. Then

$$8^{n+1}+73 =8\cdot 8^n+73 = 7\cdot 8^n +8^n +73.$$

$7\cdot8^n$ is divisible by $7$ and $8^n+73$ is divisible by $7$ by assumption, so their sum is divisible by $7$.

There's another way of viewing a proof by induction. It's a demonstration that the set of counterexamples of your statement is empty because it has no least element. Since any non-empty set of natural numbers must have a least element, if the set of counterexamples has no least element, it must be empty.

Viewed from this perspective, the inductive step shows us that candidate $n+1$ can't possibly be the smallest counterexample of the proposition $P(k)$ because the contrapositive of $P(n) \Rightarrow P(n+1)$ is $\lnot P(n+1) \Rightarrow \lnot P(n)$. So the inductive step proves that if $n+1$ is indeed a counterexample to our proposition, $n$ also must be a counterexample, so $n+1$ can't possibly be the smallest counterexample.

Why doesn't this complete the proof of $P(k)$ for all $k$? Because there's a number out there, $1$ (or $0$) that can't be expressed in the form $n+1$ (where $n \in \Bbb N^+$ or $n \in \Bbb N$). So to be sure your proposition really doesn't have any counterexamples, you need to show that this special number, the base case, also isn't a counterexample fo $P(k)$.