Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If $0 \leq r \leq n$, is it possible to use this equation: $$C( n, r ) = C( n - 1, r ) + C( n-1, r - 1 ).$$ The problem is I want to prove that $C( n, r )$ is integers by induction. In other words, I have to prove $C( n + 1, r )$ is integer deducted from $C( n, r )$. I thought of the equation above but I found the condition for r is slightly different.

So is there any other equality that I can use for this problem?

Thanks,
Chan

share|improve this question
    
@Arturo Madigin: Thanks for the edit. –  Chan Feb 7 '11 at 22:28
    
You need to replace $n$ by $n-1$ in the second term on RHS. –  user17762 Feb 7 '11 at 22:29
    
@Sivaram: Thanks! –  Chan Feb 7 '11 at 23:31
add comment

1 Answer

up vote 1 down vote accepted

Yes, you can use the equation, if interpreted correctly: since $C(m,k)$ is the number of ways of selecting a $k$-element subset from a set with $m$ elements, then we get $C(m,k) = 0$ if $k\gt m$ or if $k\lt 0$.

With the corrected equation, it should follow easily by induction on $n$, with the induction hypothesis being that $C(k,r)$ is an integer for every $r$ with $0\leq r\leq k$ (you'll have to deal with $r=0$ separately when trying to use the formula). Alternatively, if you feel uneasy about assuming the result for all $r$ corresponding to $k$, you can do induction on $n+r$ (which will also require you to deal with $r=0$ separately).

share|improve this answer
    
Thanks a lot! I really did not know that when r < 0 then C(n, r ) = 0. –  Chan Feb 7 '11 at 22:39
    
@Chan: It's a convention. –  Arturo Magidin Feb 7 '11 at 22:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.