# How much rigour in proofs?

Just a quick pointer: you could probably get away with skipping to the last 2 paragraphs, as the rest covers my motivation for answering this question.

Over this coming holidays I'm hoping to spend a little time reading through Spivak's Calculus, and answering some of the more difficult/interesting looking questions. While I've learnt most of the material before, the calculus courses in first year at my Uni were all taught primarily for engineers, and I feel I have a very 'handwavy' understanding of ideas like continuity, Riemann sums, etc., etc.

Anyway, I ran into this question in chapter 2 of the book last night:

Prove that:

$$\sum_{k=0}^{l} \binom{n}{k}\binom{m}{l-k}=\binom{n+m}{l}$$

Spivak recommended considering the binomial expansion of $(1+x)^a(1+x)^b$ and after a minute or so I saw the 'reason' why this statement is true. Briefly, we need to consider the coefficient of $x^l$ in the binomial expansion suggested above. Expanding out $(1+x)^{n+m}$ with the binomial theorem gives the coefficient $\binom{n+m}{l}$, the RHS of the expression above. On the other hand, if we expand out $(1+x)^n$ and $(1+x)^m$ separately and multiply them together, we're going to have to add up all of the different cross-multiplications that give an l'th order term: there's $\binom{n}{0}x^0\times \binom{m}{l}x^l$,$\binom{n}{1}x^1\times \binom{m}{l-1}x^{l-1}$, etc. And if we add these up we get the expression on the LHS of the equality above. These 2 expressions for the coefficient of $x^l$ must be equal, so therefore the equality above must hold.

Q.E.D.

Done.

Cool.

However, I'm still very uncomfortable with leaving the question with just this answer. The entire reason I'm reading through Spivak is to try to learn some mathematical rigour, and yet, while I'm sure this argument is valid, I have a feeling many analysts would want a little more... ummm...something :)

And this where I'm stuck. On one end of the scale, we could expect all proofs to be entirely based on axioms or previously proven theorems - Euclid style. At the other end we get arguments like this one above, or like Newton's intuitionistic view of a limit. My question is simply 'when should I be satisfied that a proof is a proof?' How much rigour is sufficient? Indeed, how much rigour is used in proofs in professional mathematics (I'd gather that's quite field-dependent)?

Thank you very much for your thoughts

-
Rigor does not mean much. Try to have your proofs be correct and complete, and preferably discuss that; leave rigor for dead bodies. – Mariano Suárez-Alvarez Nov 20 '11 at 6:03
Actually, I think most analysts would like your argument; now, algebraists, on the other hand, might instead prefer arguing that in order to choose $l$ items from $n+m$ choices, you may select $k$ from the first $n$ and $l-k$ from the last $m$ possibilities, and do this for each possible choices of $k$... – Arturo Magidin Nov 20 '11 at 6:05
Since you're learning on your own, just answer the following question honestly for every proof: "If I had to, could I provide the details?" If you are confident that you could, then there's little to be gained by actually doing so. If you are unsure, then perhaps developing the argument a little further will be enlightening. – Austin Mohr Nov 20 '11 at 7:43
Austin has identified the litmus test. If you write out your proof clearly, you should be able to identify some places that you have made assertions that might warrant further explanation. For example, if two polynomials in $x$ are equal, then the coefficients for a given power of $x$ must be equal. And the coefficient of the $l^\text{th}$ order term on the LHS is the given sum. If you are not confident in how to prove such assertions, then you should probably spell it out for yourself, at least once. Your proof should convince your target audience, which always includes yourself. – yasmar Nov 20 '11 at 8:55
I find that some students feel uneasy when their proofs contain lots of words and few equations. They shouldn't. That's how textbooks are written, after all! Equations are for communicating things precisely - they are a tool - but they are not the goal; persuasion is the goal. – Greg Martin Nov 20 '11 at 11:14

The highest degree of rigor would be achieved this way: Write down a list of axioms and a list of rules of inference. Start from an axiom and modify its logical formula using only one rule at a step and at each step clearly stating what rule you have used.

I'm not a logician and my description is probably not very good, but my point is that, whether or not this or some similar approach could be called "absolutely rigorous", it is highly impractical. At some stage in your development you know the law of associativity and need not be reminded of it every time it is used. At a later stage in your development the same is true about, say, the binomial theorem.

So, in practice, rigor is a relative concept. Proofs are written for the reader to check them. The goal of the author is to make this checking as quick and effortless as possible (this is often not true for textbook authors). To this end he must find the right amount of detail. The reader should not lose time by having to check four steps for a statement he could have easily understood in one step. On the other hand, the reader should not be forced to brood a long time over a statement that could also be written up for example with three intermediary steps each taking only a tenth of this time to check.

But this checking process depends on the reader. In my opinion, you cannot talk about rigor without talking about the "mathematical maturity" your average reader has. In a research paper proofs are considered rigorous that would be called handwaving or incomprehensible in an undergraduate textbook.

Of course, giving the right amount of steps in proofs is only one aspect of rigor. Another is not speaking about concepts you haven't properly defined. But this is relative as well. In a research paper about mathematical physics you don't have to clearly state the axioms for the real numbers. In a calculus textbook you do.

In your particular example: If you can expect your readers to know for example that the coefficients of polynomial functions are unique, your proof (or at least that part of it) is rigorous. If not, it is not, and you have to give some explanation.

You ask about when should you be satisfied that a proof is a proof. My opinion: if and only if you are sure you could, if required, fill in all thinkable intermediary steps and trace each fact you use back to the very axioms. If you are already asking yourself "is this really a proof?", it is most certainly not for you (though it is for Spivak, and, if he succeeded, for his intended readership). You have to break it down to steps that are completely obvious to you. In your mathematical development more and more arguments come to fulfill this criterion. For example, when you first learn about induction, you need to clearly state the base case, the induction hypothesis and so on. Once you have seen your share of proofs by induction, you are satisfied and often grateful if the author just writes "by induction we get...".

-

I think the most important message here is that while rigor may be relative, it has to be measured by your audience's skill, not yours.

Logically, there is a "base truth" for rigor, namely step-wise application of logical rules. You probably don't want to write down proofs like that.

I enjoyed reading Leslie Lamport's How to write a proof?. Again, you probably don't want to write your proofs on his finest level of granularity, but it might show how deeply you can dig. I like his idea about unfoldable proofs; we really should do that in order to be able to server multiple audiences at one.

Myself, I believe that any proof has to be definite in its steps. If you do a large step you expect your readers to follow, don't write words like "clearly" or "obviously" but refer to the specific result needed. That means that you have to research the step prior to writing, which help avoiding bugs.

-