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