Are there any proofs that only exist by induction?

Question

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?

Answer 1

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