6
$\begingroup$

When doing a proof by mathematical induction, I was wondering if there is any logical reason why the assumption (n=k) and induction (n=k+1) steps couldn't be done first, then do the basis case (n=1) afterwards, rather than the traditional way of doing this basis case first? I am teaching this to my students and I think it would make more sense to them to first show that P(k+1) is true if P(k) is true, and then show that P(1) is true, then P(2) must be true, P(3) is true, etc. and P(n) is true for all n. Anyway, I can't see any flaws in the logic? Please advise.

$\endgroup$
  • 12
    $\begingroup$ There isn't anything flawed with the logic. The steps can happen in either order. $\endgroup$ – Spencer Sep 8 '17 at 5:45
  • 10
    $\begingroup$ Quantum mechanics. If you prove that that if $2n+1$ being odd means $2 (n+1)+1$ being odd before proving that $1$ is odd, the observer effect will kick in and you'll discover that $1$ is now even. It used to be that reals were countable but a novice mathematician tried to do a proof by in induction on the well ordering principle without doing a base case of 1 first. The reals have been uncountable since. Everyone is mad at him. Don't make the same mistake. Math is hard enough as it is right now. $\endgroup$ – fleablood Sep 8 '17 at 6:51
  • 3
    $\begingroup$ My point being: if the base case is true, it's not going to stop being true just because you chose to prove it at a different time. $\endgroup$ – fleablood Sep 8 '17 at 7:01
  • 1
    $\begingroup$ Maybe a sound "pedagocical" reason suggests to start from the beginning... We can see induction as an infinite modus ponens: we have $P(1)$ and we instantiate $\forall n \ (P(n) \to P(n+1))$ with $n=1$ getting $P(2)$. With $P(2)$, we repeat with $n=2$ to get $P(3)$. And so on. $\endgroup$ – Mauro ALLEGRANZA Sep 8 '17 at 7:08
  • 1
    $\begingroup$ On, the third hand, as dxiv points out, in his/her answer, it's sometimes possible to prove an induction step even when the base case is false and the statement is false. Example. Prove that if you add one to any number you get the number one less than it. induction step: If n+1=n-1 then n+2=(n+1)+1=(n-1)+1=n. That can get really confusing. But as base case: 1+1!=0 you can't actually make such an error. $\endgroup$ – fleablood Sep 8 '17 at 7:19
27
$\begingroup$

Formally, there is no requirement to prove P(1) first. Practically, though, verifying P(1) first can save a lot of aggravation in cases where the inductive step works, but the base step turns out to not hold true. Try to prove that $2n+1$ is even for $\forall n \in \mathbb{N}$ by induction, for example: the inductive step certainly works, but the proposition is false since the base case $2 \cdot 1 + 1$ turns out to be odd - and you'd only realize that at the very end if you were to check P(1) last.

(And then, there are those funny cases like All horses are the same color where the fallacy falls squarely in between the base step and the proper induction step.)

$\endgroup$
3
$\begingroup$

There is pedagogical value in showing a proof by induction following in parallel the definition of proof by induction. The definition tends to be something like "If $P(1)$ and if for all $k$, $P(k) \implies P(k+1)$, then for all $k$, $P(k)$." Following this pattern helps students see that you actually are implementing the definition.

Once one is done with learning how to do induction, one is writing inductions in service of communicating a result to a reader.

A good way to organize a multi-component proof is Notation, Trivialities, Work. The reason you handle trivialities first is that these are things the reader should be looking for, but which are disposed of quickly. It most rapidly reduces the reader's cognitive load since they only have to remember that they are looking for a smaller list of results to complete the proof. Consequently, if your base case is easier, put it first. If your inductive step is easier, put it first. Either order is logically adequate.

$\endgroup$
2
$\begingroup$

One way to make logic simpler to understand and write is to write things in their order of dependence.

Facts proven about P(1) can be used later on in the proof of P(k)->P(k+1) easily.

Facts proven about P(k)->P(k+1) being used to prove P(1) would be more suspect, because those facts rely on an assumption that P(0) is true when reasoning about P(1).

By putting the base case first, the argument with the fewest assumptions, it becomes easier to "cherry pick" things you proved when proving the base case "blindly".

Then you follow up with a case with more assumptions -- that P(k) is true for some k -- and proceed to prove P(k+1).

None of these matter in a formal sense, because the things proven during P(k)->P(k+1) that rely on P(k) have that requirement regardless of if it is written first. But the idea that you start a logical proof and can "steal results" you proved earlier on for use later in the proof is a cognitive shortcut (that doesn't always hold).

$\endgroup$
1
$\begingroup$

Of course this is possible, there is no reason to do the base step first, it is however true that the fundamental idea of proof by mathematical induction is that

Let $A$ be a set such that $A\subseteq\mathbb N$, then let

$$1\in A$$ $$k\in A$$ $$k+1\in A$$

Hence, it can be inferred that $A=\mathbb N$, since $k$ can be an arbitrarily large value, and will still be an element of the set of all natural numbers.

Meaning naturally, any theorem that can be proven by means of mathematical induction is proven for $1$ first, and then for $k+1$. In addition, it is often easier to prove the desired theorem for $1$ than it is to prove the desired theorem for $k+1$, but of course even this is up to preference.

Ultimately, it is not written that proof by induction has to start with the base step, but note that if the theorem can be proven for the inductive step but not for the base step then the theorem is disproven.

$\endgroup$
  • 6
    $\begingroup$ You're missing an "\implies" in your quoted block. $\endgroup$ – Eric Towers Sep 8 '17 at 13:59
  • $\begingroup$ @EricTowers where should the \implies be inserted? $\endgroup$ – joshuaheckroodt Sep 8 '17 at 16:07
  • 1
    $\begingroup$ @joshuaheckroodt Between $k \in A$ and $k+1 \in A$. $\endgroup$ – JiK Sep 8 '17 at 19:09
1
$\begingroup$

Not only there is no reason, from the logical point of view, why the base case must be proved first as furthermore the very first text dealing with Mathematical Induction — Levi ben Gershon's Maaseh Hoshev (The Art of Calculation), written in 1321 — dealt with it doing first the inductive step and only after the base case.

$\endgroup$
0
$\begingroup$

It is good practice, at all levels of explanation, not to make the reader read something that seems pointless.

Frequently the basis case is trivial and obvious, and there is no point wasting any time on it on its own. For instance, when proving "At any party there are at least two people who have the same number of friends", making a great fuss about "When two people are alone in a room, they both know the same number of people in the room" is pointless and ridiculous without knowing the induction that is coming. It is much more motivating to get the induction done first, so that the reader or listener knows "I am on the verge of proving infinitely many facts at once, if only I have a place to start". Once that is established, the "place to start" has a reason for existing, and there is a motivation to discover it and get one's head round it.

This all applies even more when (as sometimes happens) once can take the induction all the way back to $N=0$, which is practically meaningless as well as trivial.

Mathematical proof, like computer programming, is primarily a literary activity and whatever makes it work as good literature is what ought to be done.

$\endgroup$
0
$\begingroup$

I'm surprised nobody mentioned the computational aspect of this.

Many computer programs rely on recursive functions, which are effectively algorithmic implementations based on the same steps as an inductive proof.

In computer programs however, the base case(s) are typically dealt with first, and the 'recursive' step (i.e. essentially the "inductive hypothesis") is dealt with only if the base cases do not apply.

Since inductive proofs share such similarities with their algorithmic recursive implementations, notationally speaking it makes sense to be consistent in putting base cases first.

See http://jeffe.cs.illinois.edu/teaching/algorithms/notes/98-induction.pdf (pages 6-8) for a nice example of this.

$\endgroup$
  • $\begingroup$ If your pseudo-Prolog program actually understands mathematics on natural numbers, you write your first step as passesTest(n+1) <- return passesTest(n), which doesn't match a call to passesTest(1) since there is no $n\in\mathbb N$ such that $n+1=1$; therefore the second rule fires instead. Alternatively, you can write the first step as passesTest(x) but make explicit the fact that $x>1$ (which is implicitly true in the mathematical inductive step, where $x=n+1$). $\endgroup$ – David K Sep 8 '17 at 14:06
  • $\begingroup$ I don't agree. The recursive definition fac(n)= if n>0 then n*fac(n-1) else 1 fi (for natural numbers $n$) mentions the inductive case first, then the base case, and it is perfectly fine. What one should not do is plunge into the expression for the inductive case without testing that it applies at all (but the same holds for the base case). Your example is different, it basically says passesTest(n) <- n=1 OR passesTest(n-1) where OR is the lazily evaluated logical or (the || operator of C); it is obviously not symmetric, whence passesTest(n) <- passesTest(n-1) OR n=1 is wrong. $\endgroup$ – Marc van Leeuwen Sep 8 '17 at 14:25
  • 1
    $\begingroup$ You are confusing checking the base case (which OP asks about) of a statement proved by induction with checking FOR the base case in a recursive definition (which just evaluates a simple condition). $\endgroup$ – Marc van Leeuwen Sep 8 '17 at 19:53
  • $\begingroup$ Another flaw in the argument is that the inductive step of the proof actually doesn't appear in the pseudocode at all. How does the program "know" that passesTest(n) will have the same value as passesTest(n-1) when $n\neq1$? You gave an example where you proved it in words but you didn't encode that part of the proof. I think what the pseudocode shows is that after you have proved the inductive step and the base case you can legitimately assume $P(n)\implies P(n+1)$ and $P(1)$ so you know your program is correct. $\endgroup$ – David K Sep 8 '17 at 21:09
  • 1
    $\begingroup$ I looked at the actual programs on page 8 of the link. Admittedly, few people like a default: label at the top of a switch in a C-like language, but you could list it first. Also, notice the branch on $n > 23,$ which is required because switch is ill-designed for this kind of problem. The LISP-like example is cleaner; the only compelling reason I can think of to put the inductive case at the end is if it helps your particular compiler to see that it can unroll the loop. The actual computation will always iterate the inductive step zero or more times and end on a base case. $\endgroup$ – David K Sep 20 '17 at 18:13

Your Answer

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

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