1
$\begingroup$

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

1 Answers 1

1

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

  • 0
    @Chan: It's a convention.2011-02-07