Is induction valid when starting at a negative number as a base case?

I'm reading the text Discrete and Combinatorial Mathematics by Grimaldi, and he puts forth the theorem of the principle of mathematical induction as such:

Let $S(n)$ denote an open mathematical statement that involves one or more occurrences of the arable $n$ which represents a positive integer.

$\textbf{a)}$ If $S(1)$ is true, and

$\textbf{b)}$ if whenever $S(k)$ is true ( for some particular, but arbitrarily chosen, $k \in\mathbb{Z^+}$), then $S(k+1)$ is true,

then $S(n)$ is true for all $n \in \mathbb{Z^+}$.

He then states that:

All that is needed is for the open statement $S(n)$ to be true for some first element $n_{0}\in \mathbb{Z}$ so that the induction process has a starting place. We need the truth of $S(n_{0})$ for our basis step. The integer $n_{0}$ could be $5$ just as well as $1$. $\textbf{It could even be zero or negative}$ , because the set $\mathbb{Z^+}$ is in union with $\{0\}$ or any finite set of negative integers is well ordered.

The negative part confuses me specifically. Won't this mean that the theorem can be false or would require changes both in premises and conclusion, since if the base case $n_{0}<0$ there could be some integer $m<k$ for instance, such that $S(m)$ is false? Also, can anyone direct me or provide an example of an induction proof that uses a negative base case?

Solution 1:

Probably the easiest way to understand it all is to think about it as sort of "reindexing":

Most often encountered formulation of induction:

Let $S(n)$ be a statement involving $n$. If

• (i) $S(1)$ holds, and
• (ii) for every $k\geq 1, S(k)\to S(k+1)$,

then for every $n\geq 1$, the statement $S(n)$ holds.

With the above formulation in mind, we can give a more general but equivalent formulation:

More generalized formulation of induction:

Let $S(n)$ denote a statement regarding an integer $n$, and let $k\in\mathbb{Z}$ be fixed. If

• $S(k)$ holds, and
• for every $m\geq k, S(m)\to S(m+1)$,

then for every $n\geq k$, the statement $S(n)$ holds.

Explanation: Let $T(n)$ be the statement $S(n+k-1)$, and repeat the above but instead with $T$ replacing every occurrence of $S$. Then the base case becomes $T(1)=S(1+k-1)=S(k)$, as desired.

Example: Suppose you have the statement $S(n)$ where $$ S(n) : n+5\geq 0, $$ and you claim this is true for all $n\geq -5$, where $n\in\mathbb{Z}$. Your base case would be $n=-5$, and this is true since $-5+5=0\geq 0$. As explained above, when we reformulate the proposition, the base case would be $T(1) = 0 = S(-5)=S(k)$. The following schematic may be easier to understand: $$ \color{blue}{T(n)}\equiv S(n+k-1) : (n+k-1)+5\geq 0\equiv n+k+4\geq 0\equiv\underbrace{\color{blue}{n-1}}_{k\,=\,-5}\color{blue}{\geq 0}\\\Downarrow\\[1em] \color{blue}{T(n): n-1\geq 0}. $$ As you can see above, proving $S(n)$ is true for all $n\geq -5$ is the exact same as proving $T(n)$ is true for all $n\geq 1$.

Solution 2:

The basic idea is that you have a bunch of "points" on a line or grid, and you want to show that every point (or number associated with the point) has a certain property.

You do this by:

• showing that one point has the property
• showing that, if any point has the property, another point a hop away must have the same property
• showing that you can get to any point from your original point by means of these hops

The standard method is:

• start with $0$ or $1$
• use hops of $+1$

$$0\longrightarrow 1\longrightarrow 2\longrightarrow 3\longrightarrow\cdots$$

It's easy to see that you will eventually get to any positive integer.

But you could start anywhere convenient. For example, the statement you want to prove in general may be meaningless or false for $n<5$. In that case you may start with a base case of $5$.

Suppose you wanted to prove a statement involving pairs of numbers $(x,y)$. Then you could use induction by proving the statement for $(1,1)$, then showing that truth for $(x,y)$ implies truth for $(x+1,y)$ and also that $(x,y)\implies(x,y+1)$. These two moves will allow you to get to any point with positive integer coordinates, starting from $(1,1)$.

You can even go backwards. For example, with Cauchy induction, you use the two moves $n\longrightarrow 2n$ and $n\longrightarrow n-1$.