matt grime said:
Well it would go something like.
0Cr is an integer, for all r (1 if r=0, and zero otherwise). Suppose that for a given n, all the nCr are integers, then since {n+1}Cr = nCr + nC{r-1} it follows that the {n+1}Cr are integers for all r. Hence, by induction, nCr is an integer for all n and all r.
Nice trick, defining 0Cr as zero for all integral r but r=0.
If r is limited to the integers between 0 and n inclusive, the recursive relation {n+1}Cr = nCr + nC{r-1} doesn't generate {n+1}C{n+1} and {n+1}C0. One also needs to show that nC0 and nCn = 1 for all n >= 0. That's easy, but it does make the proof longer and the proof is no longer purely inductive. That neat trick, which is consistent with defining nCr using the gamma function, makes the proof purely inductive.
Edited to add
soulflyfgm said:
nCr is n element of N for every o<= r<= n.
Suppose that a given r, all the nCr are nutural numbers
then since {n+1}Cr = nCr + nC{r-1} it follows that the {n+1}Cr are natural numbers for all n. Hence, by inducion, nCr is a natural number for all n and all r.
can some one tell me if this prove is correct or can some one help me make it better?
thank you so much
Two things are wrong with your proof.
First, you have to prove that the recursive relationship {n+1}Cr = nCr + nC{r-1} is valid. You stated it as a given.
Second, it has no basis. Any proof by induction that some predicate P is true for all integers n>=n0 has to have two parts: 1. Prove that P(n0) is true. 2. Prove that if P(k) is true then so is P(k+1). Your proof omits the first part.
matt grime establishes the basis very nicely by
defining 0Cr as 1 if r = 0 and 0 for all other integers. This definition is consistent with the standard definition of 0C0. Matt's definition makes the proof purely inductive.
The definition is a subtle trick. Why is 0c1 = 0? What is 0c1? By the standard definition of nCr, 0c1 is 0!/(1!(-1)!), and (-1)! is not defined. Matt's definition is consistent with the analytic continuation of nCr to the gamma function: For example, 0c1 = gamma(1)/(gamma(1)*gamma(0)) = 0.