Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|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
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|cite|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

Your Answer


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.