# Question regarding combination

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

-
@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

## 1 Answer

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).

-
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