# Binomial Coefficients

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. Note by Arron Kau
6 years, 6 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$