Are proofs by induction inferior to other proofs?

Solution 1:

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.

Solution 2:

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

Solution 3:

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.