5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The example I provided for proving $n+5\geq 0$ for all $n\geq -5$ where $n\in\mathbb{Z}$ may be kind of lame, but I hope it illustrates the overall point--induction is still valid regardless of what integer you start at. $\endgroup$ – Daniel W. Farlow Mar 28 '15 at 8:51
  • $\begingroup$ One important point is missing in this question: the conclusion is not the same independently of which $n_0$ is used: it only hods for $k\geq n_0$. $\endgroup$ – Marc van Leeuwen Mar 28 '15 at 9:20
  • 1
    $\begingroup$ While it's maybe going a bit far here, there is so-called well-founded (or Noetherian) induction, which can be used for any partially ordered set with a minimal element. The idea of induction is: we have to give infinitely many proofs to show that a statement holds for infinitely many objects. Instead, we show how to form a new proof for an object by using the proof for a predecessor, and we give explicit proofs for all minimal objects. With those proofs for the minimal objects together with the construction of proofs for successors, we then have covered all objects in the order. $\endgroup$ – G. Bach Mar 28 '15 at 9:52
17
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ +1 for mentioning downward induction, an underrated and not often used technique. For anyone interested, here's one definition of downward induction (maybe it should be called upward-downward induction?): Let $S(n)$ be a statement involving $n$. If (i) $S(n)$ is true for infinitely many $n$, and (ii) for each $m\geq 2, S(m)\to S(m-1)$, then for every $n\geq 1$, the statement $S(n)$ is true. $\endgroup$ – Daniel W. Farlow Mar 28 '15 at 9:48
  • $\begingroup$ @crash: There's something missing from your description. For example, $n \leq 5$ satisfies all your propositions but not the conclusion. $\endgroup$ – Ben Voigt Mar 28 '15 at 17:20
0
$\begingroup$

Suppose that $(a_n)$ is any sequence of numbers for $n = 1, 2, 3...$, not necessarily positive, or integers for that matter (in fact, $(a_n)$ may not even be numbers at all: there are some interesting proofs in set theory where $(a_n)$ represents a sequence of sets). The terms in the sequence can be viewed as a function of it's index, i.e. $a_n = a(n)$

Now let $S(n)$ be the statement that $P(a(n))$ is true where $P$ is the proposition related to the sequence $(a_n)$.

If you prove that $S(1)$ is true and $S(n) \Rightarrow S(n+1)$ then by induction, $S(n)$ is true for all $n$.

Consequently, $P(a_n)$ is true for all $a_n$.

I.e. you can use induction on any sequence at all provided you can prove the proposition true for the first term and that truth for the n'th term implies truth for the n+1 th.

$\endgroup$
0
$\begingroup$

If the induction starts at $n_0$, then the proof would establish $S(n)$ for all $n\ge n_0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy