# 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?

• seems like if you want to prove something from here to infinity checking "here" is a good first step... but I don't know a formal name for that. Commented Dec 1, 2013 at 1:12
• Here - "the least element" maybe @GradyPlayer. Honestly I think that you couldn't comprehensively conclude that the expression is true for the entire set of numbers.
– Zhoe
Commented Dec 1, 2013 at 1:14
• IH: All sets of $n \ge 4$ lines on the plane intersect at a single point. If it holds true for $n\ge 4$ points, then it holds true for $n+1$ points since the first $n\ge 3$ points intersect at a point and so too do the last $n$ lines and the two intersection points must be the same point. Therefore, all lines on the plane intersect at a single point. Commented Dec 1, 2013 at 3:26
• A row of dominos can't fall if none of them are pushed. Commented Dec 1, 2013 at 13:17

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.

• He’s up a creek without a pad? Commented Dec 1, 2013 at 1:27
• Either that or the resident cottonmouth got a springy meal. Commented Dec 1, 2013 at 1:29
• @BrianM.Scott ....brilliant!
– Tom
Commented Dec 1, 2013 at 1:31

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

• Nice example! It's non-trivial but clearly shows what is wrong. Commented Dec 1, 2013 at 11:30

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.

• It might help to explain why the statement isn't true if your base case is n=1000. Other than the obvious.... how can someone know their base case is appropriate. For example, $n! \ge e^n$ (for sufficiently large $n$) however $n=0$ is a horrible base case. Commented Dec 1, 2013 at 5:09
• "Baseless induction." What a succinct description of the problem! Commented Mar 10, 2015 at 0:57

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.

• How did you get P(n+1)=(n^2+3n+3)/2 ? Is it not (n^2 + 5n + 7)/2 ? Commented May 2, 2015 at 10:36
• @Nubcake. Changing the variable suppose we have $P(t) = (t^2+t+1)/2$. Then if we substitute $t=n+1$ we get $P(n+1) = ((n+1)^2_(n+1)+1)/2$, and so $P(n+1) = (n^2+3n+3)/2$. Commented May 4, 2015 at 1:13

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 definition might change if you treat $0$ as a natural number. Then $A$ is inductive if $0\in A$ Commented Dec 1, 2013 at 1:49

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