In Combinations, we introduced **binomial coefficients** \( \binom{n}{k} \) as the number of ways to choose \( k \) objects from a set of size \( n \). Binomial coefficients also arise naturally when considering powers of binomial expressions, as shown in the following theorem.

### Binomial Theorem: If \( a, b\) are variables and \( n\) is a positive integer, then

\[ \displaystyle (a+b)^n = \sum_{i = 0}^{n}\binom{n}{i}a^{i}b^{n-i} .\]

The two different ideas mentioned above are actually very closely related to each other. When we expand \( (a + b)^{n} \), each term in the expansion comes from choosing either \( a \) or \( b \) from each of the \( n \) binomials in the product. This is why the terms in our expression are of the form \( a^{i}b^{n-i} \). To get the term \( a^{i}b^{n-i} \), we have to multiply \( i \) copies of \( a \) and \( n-i \) copies of \( b \). If we choose \( i \) of the \( n \) binomials from which to use the term \( a \), then we are left with \( n-i \) of the binomials from which to use the term \( b \). The total number of ways to choose \( i \) of the \( n \) binomials is \( \binom{n}{i} \), which is why this is the coefficient of the term \( a^{i}b^{n-i} \).

The binomial coefficients can be arranged into a chart called **Pascal’s Triangle** that uses the relation \( \binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1} \). The \( i \)th row of Pascal’s triangle has the binomial coefficients \( \binom{i}{0}, \binom{i}{1}, \ldots, \binom{i}{i} \). The first row is considered row 0 and contains the coefficient \( \binom{0}{0} \).

\[ \begin{array}{ccccccccccccc} & & & & & &\binom{0}{0} & & & & & & \\ & & & & &\binom{1}{0} & &\binom{1}{1} & & & & & \\ & & & &\binom{2}{0} & &\binom{2}{1} & &\binom{2}{2} & & & & \\ & & &\binom{3}{0} & &\binom{3}{1} & &\binom{3}{2} & &\binom{3}{3} & & & \\ & &\binom{4}{0} & &\binom{4}{1} & &\binom{4}{2} & &\binom{4}{3} & &\binom{4}{4} & & \\ &\binom{5}{0} & &\binom{5}{1} & &\binom{5}{2} & &\binom{5}{3} & &\binom{5}{4} & &\binom{5}{5} & \\ \binom{6}{0} & &\binom{6}{1} & &\binom{6}{2} & &\binom{6}{3} & &\binom{6}{4} & &\binom{6}{5} & &\binom{6}{6} \\ \end{array} \]

By plugging in the values of the binomial coefficients, we obtain Pascal's Triangle:

\[ \begin{array}{ccccccccccccc} & & & & & & 1 & & & & & & \\ & & & & & 1 & & 1 & & & & & \\ & & & & 1 & & 2 & & 1 & & & & \\ & & & 1 & & 3 & & 3 & & 1 & & & \\ & & 1 & & 4 & & 6 & & 4 & & 1 & & \\ & 1 & & 5 & & 10 & & 10 & & 5 & & 1 & \\ 1 & & 6 & & 15 & & 20 & & 15 & & 6 & & 1 \\ \end{array} \]

When working with binomial coefficients, we can generally approach problems in two different ways, either algebraically (by manipulating the expressions), or combinatorially (by interpreting the expressions).

## Worked Examples

## 1. Show algebraically that \( \binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1} \).

Solution: We expand the expression on the left hand side in terms of factorials:

\[ \begin{aligned} \binom{n}{k} + \binom{n}{k+1} = & \frac{n!}{k!(n-k)!} + \frac{n!}{(k+1)!(n-k-1)!}\\ = & \frac{n!(k+1)}{(k+1)!(n-k)!} + \frac{n!(n-k)}{(k+1)!(n-k)!}\\ = & \frac{n!(n+1)}{(k+1)!(n-k)!}\\ = & \frac{(n+1)!}{(k+1)!(n-k)!}\\ = & \binom{n+1}{k+1}\\ \end{aligned} \]

## 2. Show combinatorially that \( \binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1} \).

Solution: The right hand side counts the number of ways to choose \( k+1 \) people from \( n+1 \) people. If we consider one of the \( n+1 \) people, then either they are chosen in the set of \( k+1 \) people or they are not. The number of ways to choose \( k+1 \) people which includes this person is \( \binom{n}{k} \) (we need to choose \( k \) of the \( n \) other people). The number of ways to choose \( k+1 \) people which do not include this person is \( \binom{n}{k+1} \) (we need to choose \( k+1 \) of the \( n \) other people).

## 3. Show that \( \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^{n} \).

Algebraic solution: From the Binomial Theorem, we have

\[ (a + b)^{n} = \sum_{i = 0}^{n}\binom{n}{i}a^{i}b^{n-i} .\]

If we let \( a = b = 1 \), this expression becomes

\[ 2^n = \sum_{i=0}^{n}\binom{n}{i} = \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} .\]

Combinatorics solution: We use the technique of Double Counting. Consider the number of ways to choose a team out of \( n\) players. From Combinations, there are \( { n \choose i}\) ways to choose a team of exactly \( i\) players; therefore, the left hand side represents the number of ways to choose a team according to the number of players. On the other hand, we can choose a team by deciding if a specified player is in the team or not. By the Rule of Product, there are \( 2^n\) ways to do this which is the right hand side. Hence, the two sides are equal.

## Comments

There are no comments in this discussion.