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.

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

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

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

$</code> ... <code>$</code>...<code>."> Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in $</span> ... <span>$ or $</span> ... <span>$ to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

There are no comments in this discussion.