# 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. –  Ｊ. Ｍ. 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-conductive 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.

-