Question

To prove the result \(C(n + 1,k) = C(n,k - 1) + C(n,k),0 \le k < n\) where \(k\) and \(n\) are integers.

Short answer

The given result is true. Thus \(C(n + 1,k) = C(n,k - 1) + C(n,k),0 \le k < n\)

Step-by-step solution

 Given

The given result is \(C(n + 1,k) = C(n,k - 1) + C(n,k),0 \le k < n\)

The Concept of Stirling numbers formula

The objects are labelled but the boxes are unlabelled, we can use the Stirling numbers formula

\(\sum\limits_{j = 1}^k {\frac{1}{{j!}}} \sum\limits_{i = 0}^{j - 1} {{{( - 1)}^i}} C(ji){(j - i)^n}\)

Prove of result

The given result is \(C(n + 1,k) = C(n,k - 1) + C(n,k),0 \le k < n\)

Consider right hand side of above equation:

\(\begin{array}{c}C(n,k - 1) + C(n,k) = \frac{{n!}}{{(k - 1)!(n - k + 1)!}} + \frac{{n!}}{{k!(n - k)!}} = \frac{{n!}}{{(k - 1)!(n - k)!}}\left( {\frac{1}{{n - k + 1}} + \frac{1}{k}} \right)\\ = \frac{{n!}}{{(k - 1)!(n - k)!}}\left( {\frac{{k + n - k + 1}}{{k(n - k + 1)}}} \right)\\ = \frac{{(n + 1) \cdot n!}}{{(k \cdot (k - 1)!)((n - k)! \cdot (n - k + 1))}}\\ = \frac{{(n + 1)!}}{{k!(n - k + 1)!}}\end{array}\)

\(\begin{array}{c}\;\;\;\;C(n,k - 1) + C(n,k) = C(n + 1,k)\\{\rm{Hence , }}C(n + 1,k) = C(n,k - 1) + C(n,k),0 \le k < n\\\therefore \end{array}\)