Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re: Re: Binomial Expansion

by japhy (Canon)
on Mar 29, 2001 at 21:39 UTC ( [id://68141]=note: print w/replies, xml ) Need Help??


in reply to Re: Binomial Expansion
in thread Binomial Expansion

Ok, for fun, and because I like mathematical proofs (I made it to the USA Mathematic Olympiad twice), here's the proof I use. In pseudo-code, the n-choose-r function looks like:
nCr (n,r) { res = 1; for i in 1 .. r { res *= n; n--; res /= i; } return res; }
The question is, why does res remain an integer? It is not difficult to show that res /= 1 is an integer, but how can we prove that by the time we get to res /= 7, res is a multiple of 7?

The proof is that by the time we have gotten to res /= X, we have multiplied res's original value, 1, by X continuous integer, and in every series of X continuous integers, there will be one number divisible by X:

X = 2, series = (y, y+1); one is div. by 2 X = 3, series = (y, y+1, y+2); one is div. by 3 ... in nCr(17,7), n is of the series (17,16,15,14,13,12,11) i is of the series ( 1, 2, 3, 4, 5, 6, 7) (17/1) (17/1) (16/2) (17/1) (16/2) (15/3) (17/1) (16/4) (15/3) (14/2) (17/1) (16/4) (15/(3*5)) (14/2) (13/1) (17/1) (16/4) (15/(3*5)) (14/2) (13/1) (12/6) (17/1) (16/4) (15/(3*5)) (14/(2*7)) (13/1) (12/6) (11/1)
We're allowed to move the denominators around like I did, because we've already showed the product will already be an integer. The product looks like:
r ----- | | n - (i-1) | | --------- | | i i=1


japhy -- Perl and Regex Hacker

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://68141]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others examining the Monastery: (2)
As of 2024-03-19 07:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found