binomial coefficient recursive relation

Topics

• combinatorics

Consider choosing $k$ elements from $n$ elements:

• If an element (say first one) is chosen, we need to pick $k-1$ elements from remaining $n-1$, which is $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$
• If the first one is not chosen, we need to pick $k$ elements from remaining $n-1$, which turns out to be $\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$

Since both cases cover all possibilities, we have:

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$$

This formula is also how pascal’s triangle is constructed.

Related