|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png) Viewing Message
|
|
|
| ``Re: better proof n choose r (combinations)''
by perucho on 2009-07-24 21:31:35 |
|
| Hi polarbeer,
I understand you don't like induction proofs, however you *need* to learn about induction proofs (mandatory if you're studyng math or any other affine discipline).
I admit Matte's proof it is not a trivial induction proof, but neither is too hard. Let me see if can to help you a little.
First you must realize Matte isn't proving the formula
n \choose r = n!/[r!(n-r)!] (actually he is using that formula), but he want to prove that n \choose r *is an integer*. I think this fact confusing you. Okey, induction over n. for n=0 you have
0 \choose 0 = 0!/(0!0!)=1, an integer. There is not some element? Wrong! 0 is an element! so that such element give us just *one* combination. For that reason Matte says that for n=0, the proposition is true.
Second, now arises what I think is your major doubt. Matte wrote(sic):
"Thus, suppose the claim holds for n \geq 1." (\geq = greater or equal than). At this moment you may think: "well, if the claim is valid for n \geq 1 and the proof by induction is over n, what else I have to prove? Hey, give a break! What about the hypothesis ``for n \geq r \geq 0''? The proof also depends on r, so we also need use the hypo (of course!). For that reason Matte continues writing:
" For r=1,....,n, Pascal's rule (a well-known formula) gives
n+1 \choose r = n \choose r + n \choose r-1." (1)
Third, notice that the 2 terms on RHS of (1) is based on the induction's central assumption (we assume that the proposition is valid for n, i.e. those both terms are integers), while we need to show that the LHS of (1) i.e. the theorem is also valid for n+1.
So from (1) one realizes that *all of* the terms
n+1 \choose 1,... n+1 \choose n,
*are integers*.
Fourth and finally (maybe the most abstract part of the proof), we note Matte wrote: "For r=1,...,n". So, if, for the binomial antecedent(the upper number) n+1 and the remaining consequent r=0 and n+1, the proposition is also valid (i.e. they are integers too), we get it! And so Matte ends the demo by writing:
"Since
n+1 \choose 0 =1, n+1 \choose n+1 =1 (integers!)
the proof is complete"
You don't be afraid about those kind of demonstrations, it is just only to be familiar with them.
Matte's proof is quite elegant and compact.
perucho
|
| | [ reply | up | top ] |
|
|
|
|
|
|
