0
$\begingroup$

This question already has an answer here:

My instructor stated that in order to have a valid proof by mathematical induction, you first have to show A(1) holds, and then assume A(n) to deduce A(n+2). Why is the first step necessary if we are going to assume A(n) though?

I get that showing A(1) is true suggests that A(n) might be, but that could very easily not be the case. Perhaps A(3) does not hold. So why logical benefit do we gain by proving A(1) before completing a more general proof by induction?

$\endgroup$

marked as duplicate by ncmathsadist, Daniel W. Farlow, user228113, M. Vinay, Claude Leibovici Jun 12 '16 at 5:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Can you state the principle of mathematical induction you are using? $\endgroup$ – Daniel W. Farlow Jun 11 '16 at 23:35
  • $\begingroup$ In an induction process, we always need to start from an outset point which could be $1$ or anything else, but for sure without proving for a proper outset, your proof is not complete. $\endgroup$ – Majid Jun 11 '16 at 23:35
  • 1
    $\begingroup$ You have to knock over the first domino to make the rest of them fall. $\endgroup$ – user4894 Jun 11 '16 at 23:38
  • $\begingroup$ Let's prove by induction that all natural numbers are bigger than $1000$. In fact, if $n\ge 1000$, then $n+1\ge 1001\ge1000$. QED. $\endgroup$ – user228113 Jun 12 '16 at 3:37
4
$\begingroup$

A proof by induction has two parts, and you have to prove each of them:

  • $(i)\quad$ $A(n)$ implies $A(n+1)$, for all natural numbers $n$;

  • $(ii)\quad$ $A(1)$ is true.

Together, these two facts imply that $A(n)$ is true for all natural numbers $n$. For example, to see $A(3)$ is true (given these two facts), we argue as follows:

  • We know $A(1)$ is true by $(ii)$.

  • Since $A(1)$ is true, $A(1+1)$ is also true by $(i)$.

  • Since $A(1+1)$ is true, $A(1+1+1)$ is also true by $(i)$.

  • So $A(3)$ is true!

However, we need both pieces for induction to work. For example, let $A(n)$ be the property "$n=n-3$." Then:

  • Clearly (for any $n$) if $A(n)$ is true, then $A(n+1)$ is also true: since $A(n)$ means $n=n-3$, so $n+1=n-3+1$, so $n+1=(n+1)-3$ - but this is just $A(n+1)$!

  • However, $A(n)$ is in fact false for every $n$.

$\endgroup$
  • $\begingroup$ Thanks for the response. What if you showed A(1) held, and showed that assuming A(n) allows you to deduce A(n+1), but it turned out A(2) was false? Or is there something preventing a case like this from arising? $\endgroup$ – IgnorantCuriosity Jun 11 '16 at 23:40
  • 3
    $\begingroup$ @IgnorantCuriosity How could that happen? If "$A(1)$" is true, and "$A(1)$ implies $A(2)$" is true (this is a special case of "$A(n)$ implies $A(n+1)$", then of course "$A(2)$" is true; that's what "implies" means. (See en.wikipedia.org/wiki/What_the_Tortoise_Said_to_Achilles for an amusing exchange around this.) Now of course, what can happen in practice is that I think that I've proved "$A(1)$", and I think that I've proved "$A(n)\rightarrow A(n+1)$", and I also think that I've proved "Not $A(2)$." In this case, I know that at least one of my proofs is wrong. $\endgroup$ – Noah Schweber Jun 11 '16 at 23:42
  • $\begingroup$ (Technically, there's also the possibility that the axioms I'm using are inconsistent. But I think that's just going to muddy things at first; for now, assume that the axioms we're using are in fact true statements about the world of mathematics. This is an assumption that you can explore in more detail - and maybe even reject! - down the road; but for now I think getting a good grasp of induction comes first.) $\endgroup$ – Noah Schweber Jun 11 '16 at 23:45
  • $\begingroup$ I don't have an example of a statement that shows this happening, but my question comes from seeing your demonstration that a false A(n) can deduce A(n+1), and the false theorem that n^2 + n + 41 generates primes. In this case, it holds for the first 39 numbers, but not the 40th. I suppose the fact that we have no way of proving whether something generates primes comes into play here, but initially the scenario of having a true A(1), and deducing A(n+1) from a false A(n) seemed plausible. $\endgroup$ – IgnorantCuriosity Jun 11 '16 at 23:53
  • $\begingroup$ @IgnorantCuriosity Ah, I think I see the issue: what we prove in the inductive step of a proof by induction is that $A(n)$ implies $A(n+1)$ for every $n$. And we don't just give a plausibility argument - we have to prove it. So in a case like you mention, what's going on is: we see $A(1)$; we see that $A(n)\rightarrow A(n+1)$ is true for a whole bunch of specific $n$s; but *that's not a proof* that $A(n)\rightarrow A(n+1)$ is true for every $n$! And so that's the difference. "Proof by induction" is not just generalizing from a bunch of cases. $\endgroup$ – Noah Schweber Jun 11 '16 at 23:55
0
$\begingroup$

What you're really showing in the step case is that if $A(n)$ is true, then $A(n+1)$ is true. So you're showing $A(n) \implies A(n+1)$. With just this, you don't know if your statement is true for any actual values of $n$. When you prove it for a value, for example $A(1)$, that together with $A(n) \implies A(n+1)$ gives you $A(1) \implies A(2) \implies A(3) \implies ...$ so you can just follow that chain of implications and your statement is true for any $n \geq 1$

For example: The induction step of "All integers are of the form $\frac{2k+1}{2}$ for some integer $k$" is true since $\frac{2k+1}{2} + 1 = \frac{2(k+1)+1}{2}$. You can't verify it for any value of $n$ though, since no integers are actually of that form.

$\endgroup$
  • $\begingroup$ After posting I see that my answer is more or less the same as Noah's, but I'll leave it up in case it's useful to someone. $\endgroup$ – rVitale Jun 11 '16 at 23:47
0
$\begingroup$

The reason proof by induction works is because of the well-ordering principle (WOP) of the natural numbers. The well-ordering principle says any nonempty subset of the natural numbers has a least element. It turns out that WOP is logically equvalent to the principle of mathematical induction (PMI). This is fairly straightforward to prove as follows:

$WOP\leftarrow PMI$ Suppose $S$ has no minimal element. Then $ n = 1 \notin S$, because otherwise $n$ would be minimal. Similarly $n = 2 \notin S$, because then $2$ would be minimal, since $n = 1$ is not in $S$. Suppose none of $1, 2, \cdots, n$ is in $S$. Then $n+1 \notin S$, because otherwise it would be minimal. Then by induction $S%$ is empty, a contradiction.

$WOP\leftarrow PMI$ Suppose $P(1)$ is true, and $P(n+1)$ is true whenever $P(n)$ is true. If $P(k)$ is not true for all integers, then let $S$ be the non-empty set of $k$ for which $P(k)$ is not true. By well-ordering $S$ has a least element, which cannot be $k = 1$. But then $P(k-1)$ is true, and so $P(k)$ is true, a contradiction.

So clearly WOP is true iff PMI is true. A lot of teachers don't like going through this in basic rigorous mathematics courses, which to me is a big mistake. Students need to understand why induction works,it's a critical method of proof.

How's that?

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.