# Are proofs by induction inferior to other proofs?

http://mathoverflow.net/questions/71691/geometric-meaning-of-a-trigonometric-identity

In the question on mathoverflow that is linked above, I mentioned that I had proved an identity by mathematical induction. Noam Elkies, a professor at Harvard, posted an answer. He did not answer the question actually posed. Rather, he posted a better proof of the identity that I had proved by induction.

Is his proof actually better? My inclination is to say "yes", but I'm not staking my life on that.

But some years ago, I concluded that when a proposition can be proved either by mathematical induction or by other methods, the proof by other methods is usually better. This was based in part on various particular examples. But I can't remember what any of those are!

So was I right? And if so, what are (1) the examples (hundreds of them, if you have them!), and (2) the explication of how they are better?

-
What does "better" / "inferior" mean? I'm highly tempted to close as "not a real question". – Zev Chonoles Sep 3 '11 at 6:41
Would the person who voted to close please explain? @Zev: This looks like a reasonable question to me. Similar questions on proofs by contradiction have created a lively and highly interesting discussion, I don't see an a priori reason why this should be different here. For what it's worth, I vote against closing. – t.b. Sep 3 '11 at 6:44
what I don't like in the question is use of "better" as if it were obvious what it meant, and the only issue is determining whether it applies to induction proofs or not. – Zev Chonoles Sep 3 '11 at 7:40
There's a second vote to close; I thus join Theo and Jonas to vote against closure. – J. M. Sep 3 '11 at 10:58
I, like Theo, Jonas and J. M., vote against closure. – David Speyer Sep 3 '11 at 11:35

To add to Kaveh's answer: this article discusses (lightly) the "virtues" of each kind of proof, using as example three proofs for the Binomial theorem: induction, combinatorics and calculus. Each has its merits. One extract:

[A 'good' proof] should explain why the result not only is true but should be true. [...] Deep understanding of how induction and recursion are intertwined is needed for the induction proof to give the should be true reaction. For most mathematicians and students of mathematics induction proofs give little enlightenment and may be judged to be rather ugly because of that failure.

-
+1. I think there are two extremes when it comes to why a proof works. There are proofs that rely on key insights which give you a deep understanding of what is going on, both in the proof and more generally. There are also proofs that rely on seemingly arbitrary coincidences, the kind that you cannot reuse, cannot satisfactorily explain, and which give you no benefit outside of the proof. There are a lot of induction proofs that fall into the latter group. However, this does not mean that induction is inherently less insightful. – Aaron Sep 5 '11 at 17:35

Much of reverse mathematics deals with weak notions of induction. As a very simple example, we can consider Peano arithmetic in its first order form. We have definitions of successor, addition, multiplication and some of their pertinent properties. Then we have induction, which states that if a formula $\varphi$ is true "by induction", then it is true for all natural numbers. What reverse mathematics does (in this context) is to see what happens if we limit what $\varphi$ looks like.

Some truths about the natural numbers can already proved when induction is only allowed over (say) quantifier-free formulas. Other theorems require more difficult notions. Some theorems are deducible from each other using only weak induction, and so in some sense they are "equivalent".

In the case at hand, it might be true that from this point of view, the non-inductive proof is not "better", since to prove everything from first principles might necessitate strong tools (I haven't looked at the specific proof). However, if you allow yourself to assume certain truths (a theory), it might be true that the non-inductive proof is "better".

It is, in the end, up to you to decide what is better and not, to provide some "reason" (or framework), and to convince us of its importance (if not validity, since the notion of "absolute" truth is not involved here, only relative truth).

-

What Yuval wrote is correct, but that is more about formal proofs and from the perspective of a logician or a person working in foundations of mathematics. I want to explain one of the reasons that people sometimes claim that a non-inductive proof is better than another one which is explicitly using induction.

From formal and foundational perspective, you may need to use induction to prove the statement working a formal theory, it might be there explicitly or it might be hidden behind lemmas and theorems that are being used.

So why is it sometimes claimed that a proofs is better than another one?

Because a proof is not always a formal proof (an informal proof is something that would convince you about the truth), and because a proof contains more information than just the truth of the statement. It tell us why the statement is true. This is not a rigorous (AFAIK) but rather an intuitive one. Mathematics is not just formal proofs, intuition is also an important part of it. Over time we learn the skill to understand some mathematical concepts, objects, theorems, ... so well that we don't need to check their formal definitions or proofs anymore, we start to "see" them (some can see a reference to Godel's views about philosophy of mathematics here :). And when we "see" them, we don't need a formal proof for them to use them.

Sometimes when we work with Yuval on a topic that he is more knowledgeable than me, he claims some statement is true and I have no doubt that the statement is true but I don't see that it is true at first. I don't dispute the truth of the statement but I tell him "I don't see it", and he explains it more and then I also start to "see" it! :)

From the perspective of a beginner that does not see the truth of any mathematical theorems and needs proofs for all of them (which from foundational point of view will need induction) it might be the case that there is not a big difference between the proofs. But you hear a lot when some mathematician claims that one proof is better than another one. The main reason is that a proof helps us intuitively understand the reason a statement is true, it helps us "see" that the statement is true. It is more than just expressing that the statement is true. Different proofs give us different perspectives on its truth. A completely formal proof as a sequence of formal mathematical expressions can show the correctness of a statement, and we can check that the proof is correct, it is a mechanical task of low complexity, but often it will not tell us the reason the proof works, it does not help us understand the reason the statement is true. On the other hand, a better informal proof using concepts and theorems that we "see" can help us in understanding the reason the statement is true, and hopefully eventually we might even "see" that the statement is true.

Using induction can be similar to doing a formal proof, while using other concepts and theorems about them is similar to the informal proofs that use what we can already see.

-

Probably the question that should be asked is if the result can be obtained from scratch without knowing it! Often, many textbook or homework problems ask students to use induction to prove some theorem, but the student would be unable to come up with the theorem in the first place. This kind of problems is no good. For example, instead of asking for a closed form for $\sum_{k=1}^n k^2 2^k$ (using only arithmetic and exponentiation), they give the answer and ask for a proof by induction, which is almost totally useless.

One can see a sharp distinction between proofs by induction where the hypothesis "drops from the sky" and proofs that naturally arrive at the conclusion by other means. Despite the fact that all the other proofs must use induction at the formal level, they feel more natural when there is no strange and inexplicable cancellation of terms that occurs when you prove the answer correct by induction.

As t.b. commented, in combinatorics one would generally prefer bijective proofs basically for this reason; nothing cancels and there is a clear direct correspondence between one collection and another. Similarly it is better to show how to solve a recurrence relation by a general method than to just state the solution and prove it by induction.

Such considerations of cancellations in proofs occur in other ways besides the use of induction. In geometry one prefers a synthetic solution (using geometric arguments) rather than an analytic solution (using equations over a real-closed field), simply because in an analytic solutions there is usually unexplainable cancellation of factors along the way that never show up in a purely synthetic proof. Some even avoid trigonometry for the same reason, but some theorems are far nicer when expressed in trigonometry.

The amount of redundancy in a proof, corresponding to unnecessary detours that result in later cancellation can be somewhat quantified in Euclidean geometry by the total degree of the rational functions involved. In the most elegant synthetic solution one almost always deals with linear or quadratic expressions and there are no unnecessary cancellations, but in an analytic solution every circle intersection doubles the degree by two. In fact this is why automated theorem provers still cannot handle complicated geometric theorems that have reasonably short synthetic proofs, because humans can construct new points that link existing ones in a simple way that avoids later cancellation.

In logic we have the cut-elimination theorem for sequent calculus, which is a bit like saying there is always a direct proof that does not use any new idea that is not already contained in the theorem to be proven. However, as proven by George Boolos, not allowing such indirect proofs (using cut) can force the minimal length of proof to be far larger than otherwise. So if we go by proof length to compare proofs we may need some 'cancellation'.

There is therefore a trade-off between proof length and explanatory power. In the example I started with, the shortest proof will probably be by induction! But the most satisfying one will show how to solve such problems in general, through the anti-difference operator and anti-difference by parts. It is quite clear that here structural insight is more important than a short proof, since the 'new ideas' introduced do not just solve this problem but a whole class of problems. Furthermore, these enable finding the closed form without knowing it. This reminds one of the distinction between P and NP, where a problem in NP has a solution that can be verified in polynomial time, exactly like most textbook induction problems can be verified in a routine way, but a problem in P has a solution that can be found in polynomial time.

Anyway these are just my views, since I also have thought much about this kind of issue with induction. Some instances of induction are so natural that people do not even notice it and sometimes insist there is no induction, like whenever you use a summation sign. Other times induction feels like the wrong tool. One such simple example is the handshake-lemma in graph theory, where there is an induction proof that feels like it does not explain anything, and the double-counting proof that explains it all. Many students claim that the latter does not use induction, but formally it does!

-