Chapter 2 #3 : Binomial Coefficients and The Binomial Therom

3.

If $0 \le k \le n$, the "binomial coefficient" $\left(\!\!\begin{array}{c}n \\ r \end{array}\!\!\right)$ is defined by

$\left(\!\! \begin{array}{c} n \\ r \end{array} \!\!\right) = \frac{n!}{r!(n-r)!} = \frac{n(n-1)! \dots (n-k+1)}{k!}, \quad \text {if} \; k \neq 0, n$

$\left(\!\! \begin{array}{c} n \\ r \end{array} \!\!\right) = \left(\!\! \begin{array}{c} n \\ n \end{array} \!\!\right) = 1$ (a special case of the first formula if we define $0! = 1$), and for $k<0$ or $k>n$ we just define the binomial coefficient to be 0.)

(a) Prove that

(1)

\begin{align} \left(\!\! \begin{array}{c} n + 1 \\ k \end{array} \!\!\right) = \left(\!\! \begin{array}{c} n \\ k-1 \end{array} \!\!\right) + \left(\!\! \begin{array}{c} n \\ k \end{array} \!\!\right) \end{align}

(this equality is often known as "Pascal's Rule" or "Pascal's Recursion")

Proof:
The proof is purely algebraic.

(2)

\begin{align} \left(\!\! \begin{array}{c} n \\ k-1 \end{array} \!\!\right) + \left(\!\! \begin{array}{c} n \\ k \end{array} \!\!\right) \\ \\ = \frac{n!}{(k-1)!(n-k+1)!} + \frac{n!}{k!(n-k)!} \quad \text {, by definition of binomial coefficient} \\ \\ = \frac{n!k!(n-k)! \; + \; n!(k-1)!(n-k+1)!}{k!(k-1)!(n-k)!(n-k+1)!} \quad \text {, from adding quotients} \\ \\ = \frac{n!k(k-1)!(n-k)! \; + \; n!(k-1)!(n-k+1)(n-k)!}{k!(k-1)!(n-k)!(n-k+1)!} \\ \\ = \frac{n!(k-1)!(n-k)![k + n - k + 1]}{k!(k-1)!(n-k)!(n-k+1)!} \\ \\ = \frac{n!(n+1)}{k!(n-k+1)!} \\ \\ = \frac{(n+1)!}{k!(n+1-k)!} \\ \\ = \left(\!\! \begin{array}{c} n+1 \\ k \end{array} \!\!\right) \quad \text {, by definition of binomial coefficient} \\ \\ Q.E.D. \end{align}

This relation gives rise to the following configuration, known as "Pascal's Triangle" - a number not on one of the sides is the sum of the two numbers above it; the binomial coefficient $\left(\!\!\begin{array}{c}n \\ k \end{array}\!\!\right)$ is the $(k+1)$st number in the $(n+1)$st row.

(b) Notice that all the numbers in Pascal's triangle are natural numbers. Use part (a) to prove by induction that $\left(\!\!\begin{array}{c}n \\ r \end{array}\!\!\right)$ is always a natural number.

Proof:

$\text {Let } n, k \in N+\{0\} \text { and } 0 \le k \le n$

Then, by definition of binomial coefficients $\left(\!\! \begin{array}{c} 0 \\ k \end{array} \!\!\right) = \left(\!\! \begin{array}{c} 0 \\ 0 \end{array} \!\!\right) = 1$ , since $0 \le k \le n$ and $\left(\!\! \begin{array}{c} 1 \\ k \end{array} \!\!\right) = \left(\!\! \begin{array}{c} 1 \\ 0 \end{array} \!\!\right) = 1$ or $\left(\!\! \begin{array}{c} 1 \\ k \end{array} \!\!\right) = \left(\!\! \begin{array}{c} 1 \\ 1 \end{array} \!\!\right) = 1$ , since again $0 \le k \le n$

Then $\left(\!\! \begin{array}{c} n \\ k \end{array} \!\!\right) \in N$ if $0 \le k \le n \le 1$

Now suppose that $n$ is an arbitrary element of $N$. And assume that: $\left(\!\! \begin{array}{c} n \\ k \end{array} \!\!\right) \in N \text {,} \quad \forall \: k \in N \text {, such that } 1 < k \le n$

This implies that $\left(\!\! \begin{array}{c} n \\ k \end{array} \!\!\right) \in N$ and $\left(\!\! \begin{array}{c} n \\ k-1 \end{array} \!\!\right) \in N$

From Pascals rule we have, $\left(\!\! \begin{array}{c} n+1 \\ k \end{array} \!\!\right) = \left(\!\! \begin{array}{c} n \\ k \end{array} \!\!\right) + \left(\!\! \begin{array}{c} n \\ k-1 \end{array}\!\!\right)$

Now, since $\left(\!\! \begin{array}{c} n \\ k \end{array} \!\!\right)$ and $\left(\!\! \begin{array}{c} n \\ k-1 \end{array} \!\!\right)$ are elements of $N$, and since the set $N$ is closed under addition, we must admit that $\left(\!\! \begin{array}{c} n \\ k \end{array} \!\!\right) + \left(\!\! \begin{array}{c} n \\ k-1 \end{array}\!\!\right) = \left(\!\! \begin{array}{c} n+1 \\ k \end{array} \!\!\right)$ is an element of $N$.

It has been shown that $\left(\!\! \begin{array}{c} 0 \\ k \end{array} \!\!\right)$ and $\left(\!\! \begin{array}{c} 1 \\ k \end{array} \!\!\right)$ are elements of $N \: \text{(} 0 \le k \le n \le 1\text{)}$, and $\left(\!\! \begin{array}{c} n+1 \\ k \end{array} \!\!\right)$ is an element of $N$ whenever $\left(\!\! \begin{array}{c} n \\ k \end{array} \!\!\right)$ and $\left(\!\! \begin{array}{c} n \\ k-1 \end{array} \!\!\right)$ are elements of $N$. Thus, by the property of mathematical induction:

(3)

\begin{align} \left(\!\! \begin{array}{c} n \\ k \end{array} \!\!\right) \in N, \quad \forall \: n, k \in N+\{0\} \; \text{such that } 0 \le k \le n . \end{align}

$Q.E.D$

---