I've come to learn more about induction recently for proving things, and one thing stands out to me.

It seems like you could just data-mine patterns and guess a relationship you think might be correct, prove it with induction, and then that's it. You don't necessarily learn anything about why the underlying relationship is correct.

For example if I saw the Towers of Hanoi problem (number of moves to complete given number of discs $n$), I could theoretically just look at the data, guess $2^n-1$ and prove it with induction, and be right, even though I didn't need to go through generating functions or fancy recurrence expansions or characteristic polynomials and what have you.

This leads me to wonder:

Are there any proofs that exist by induction alone, i.e. where some other proof or derivation does not exist? Something that is true but not necessarily known why, through some alternative means?

  • 1
    $\begingroup$ This touches upon the philosophy of induction, and more concretely on the question "what is and what is not a proof by induction?" Some will say that more or less any proof in mathematics has some form of induction, if not used overtly then hidden implicitly in results and constructions used. Where do you draw the line? $\endgroup$ – Arthur Jul 25 '16 at 18:57
  • $\begingroup$ The purpose of a proof is to verify propositions which are not obvious by logical inference from propositions which are obvious. Induction is based upon the observation that any collection of positive integers has a smallest element. If you understand that, how is that a deficient understanding of why a non-obvious proposition is true when verified by the principle of induction? $\endgroup$ – John Wayland Bales Jul 25 '16 at 19:07
  • $\begingroup$ @JohnWaylandBales I suppose what bugs me is that it is possible to show something as being true even though it could have been achieved through guesswork alone, any not any kind of meaningful analysis or utilization of known identities or relationships. It feels less interesting to me even though it's very powerful. $\endgroup$ – KaliMa Jul 25 '16 at 19:19
  • 1
    $\begingroup$ You may enjoy this article I wrote a few years ago that deals with induction and the whole issue of whether or not you "learn anything" when you prove something by it. $\endgroup$ – Daniel W. Farlow Jul 25 '16 at 19:46
  • $\begingroup$ @KaliMa It legitimate to wonder is there are some significant principles underlying what may be obvious in certain examples. That is the fact underlying the utility of logical (as opposed to mathematical) induction: seeking the principles which underlie observations. The inquiring mind does not always say "Oh, that's obvious!" and move on, but given the time and interest, looks for underlying principles. $\endgroup$ – John Wayland Bales Jul 25 '16 at 20:50

One respectable author, David Gunderson, in his tome Handbook of Mathematical Induction (MAA book review here, if interested), touches on the question you asked:

It seems that not all statements provable by induction also have direct (using only deductive logic and no induction) proofs, though proving this claim might be difficult! It's very likely that there are mathematical statements for which only an inductive proof is known. (p. 105)

Gunderson goes on to "flip the script" and poses an even more interesting/surprising question when he writes, "This next exercise might indeed ask more than can be answered, but the questions in it might make for interesting discussion."

Exercise 31 (p. 105): Does there exist a mathematical truth that does not have a (meaningful) [sic] proof by induction? If someone handed you such a truth, how could you guarantee that no inductive proof exists? Does there exist a property provable by induction, but with no other kind of proof? Again, how would one show that no direct proof exists? Can one characterize those mathematical truths for which no inductive proof exists, or can one characterize those statements that have inductive proofs, but fail to have any other proof?

Prior to this exercise, he remarks on how induction suffers from the weakness that one already needs to "know" (or guess) the desired result before induction can be applied and that only in certain situations can induction be used to discover, say, a particular identity. Finding a particular identity might be done without induction, but for more complicated problems, one often guesses at a formula via non-inductive techniques, whereas induction may provide the easiest proof. In fact, some mathematicians, such as David Bradley in his More on Teaching Induction letter to the editor (p. 8) for the MAA Focus, argue that induction is an overused proof technique and should generally be avoided if a more conceptual/direct proof can be found. Of course, some mathematicians, including Gunderson and Paul Stockmeyer, do not quite agree with this, where the latter goes on to write in his own letter to the editor (More on Induction) in the MAA Focus (p. 28) that, "We can certainly construct proofs of combinatorial identities, such as $1+2+3+\cdots+n=n(n+1)/2$ that hide the induction from our students. As mathematicians, though, we should keep in mind that with identities of this type induction is always present, at least in the background."

Gunderson supports Stockmeyers' argument and notes that since the counting numbers are defined recursively, and many operations in math (like addition of integers) are defined recursively, and confirmed inductively, that induction is almost always at work. He goes on to say the following:

One might take this reasoning a bit further and argue that induction is actually alive in any mathematical statement. (p. 104)

Interestingly, a recent discussion on a Reddit math thread concerned itself with whether or not some statements are only provable by a particular method, with "induction or contradiction" being highlighted as possible proof techniques. Gunderson actually gives the exercise

Let $1\leq a_1\leq a_2\leq\cdots\leq a_n$ be positive integers. Prove that if $$\frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_n}=1,$$ then $a_n<2^{n!}$.

as an example of a problem that "seems only to have a proof by contradiction or downward induction."

Regardless, it appears that your question in particular, and several other related questions such as those in Exercise 31, are far from being "settled."

| cite | improve this answer | |

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