Binomial Theorem Corollaries

Recall the binomial theorem, which states that for any $n \in \mathbb N$ and $x \in \mathbb R$ ,

$\displaystyle (1 + x)^n = \sum_{k=0}^n {n \choose k} x^k,$

where we define $0^0 := 1$ by convention.

Problem 1. Prove that for any $a, b \in \mathbb R$ ,

$\displaystyle (a + b)^n = \sum_{k=0}^n {n \choose k} a^{n-k} b^k.$

(Click for Solution)

Solution. If $a = 0$ then the result is trivial. If $a > 0$ , then

$\begin{aligned} (a+b)^n &= a^n \cdot \left(1 + \frac ba\right)^n = a^n \cdot \sum_{k=0}^n \left( \frac ba \right)^k \\ &= a^n \cdot \sum_{k=0}^n a^{-k} \cdot b^k = \sum_{k=0}^n a^{n-k} \cdot b^k. \end{aligned}$

Problem 2. Evaluate the sums $\displaystyle \sum_{k=0}^n {n \choose k}$ and $\displaystyle \sum_{k=0}^n (-1)^k {n \choose k}$ .

(Click for Solution)

Solution. By Problem 1,

$\displaystyle (1 + (\pm 1))^n = \sum_{k=0}^n (\pm 1)^k {n \choose k}.$

Therefore, $\displaystyle \sum_{k=0}^n {n \choose k} = (1+1)^n = 2^n$ and $\displaystyle \sum_{k=0}^n (-1)^k {n \choose k} = (1-1)^n = 0$ .

Problem 3. Prove that $\displaystyle \sum_{k \in \mathbb N_0 :\, 2k \leq n} {n \choose 2k} = \sum_{k \in \mathbb N_0 :\, 2k+1 \leq n} {n \choose 2k+1}$ .

(Click for Solution)

Solution. By Problem 2,

$\begin{aligned} 0=\sum_{k=0}^n (-1)^k {n \choose k} &= \sum_{k \in \mathbb N_0 :\, 2k \leq n} (-1)^{2k} {n \choose 2k} + \sum_{k \in \mathbb N_0 :\, 2k+1 \leq n} (-1)^{2k+1} {n \choose 2k+1} \\ &= \sum_{k \in \mathbb N_0 :\, 2k \leq n} {n \choose 2k} - \sum_{k \in \mathbb N_0 :\, 2k+1 \leq n} {n \choose 2k+1}. \end{aligned}$

Therefore,

$\displaystyle \sum_{k \in \mathbb N_0 :\, 2k \leq n} {n \choose 2k} = \sum_{k \in \mathbb N_0 :\, 2k+1 \leq n} {n \choose 2k+1}.$

Problem 4. Evaluate the sums $\displaystyle \sum_{k= 1}^n k {n \choose k}$ and $\displaystyle \sum_{k= 1}^n k^2 {n \choose k}$ .

(Click for Solution)

Solution. Recall the vanilla binomial theorem

$\displaystyle (1 + x)^n = \sum_{k=0}^n {n \choose k} x^k.$

Differentiating on both sides twice,

$\begin{aligned} n(1+x)^{n-1} &= \sum_{k=1}^{n} k {n \choose k} x^{k-1}, \\ n(n-1)(1+x)^{n-2} &= \sum_{k=2}^{n} k(k-1) {n \choose k} x^{k-2}. \end{aligned}$

Setting $x = 1$ in the first identity,

$\displaystyle \sum_{k=1}^{n} k {n \choose k} = n \cdot 2^{n-1}.$

Setting $x = 1$ in the second identity,

$\begin{aligned} n(n-1)\cdot 2^{n-2} &= \sum_{k=2}^{n} k(k-1) {n \choose k} = \sum_{k=2}^{n} k^2 {n \choose k} - \sum_{k=2}^{n} k {n \choose k}. \end{aligned}$

By algebruh, since $\displaystyle 1^r {n \choose 1} = n$ for any $r$ ,

$\displaystyle \sum_{k=1}^{n} k^2 {n \choose k} = n(n-1)\cdot 2^{n-2} + n \cdot 2^{n-1} = n \cdot 2^{n-1} \cdot (2n-1).$

Problem 5. Evaluate $\displaystyle \sum_{k= 0}^r {m \choose k} {n \choose r-k}$ .

(Click for Solution)

Solution. Using the binomial theorem on the product

$\displaystyle (1+x)^{m+n} = (1+x)^m (1+x)^n,$

we have

$\begin{aligned} \sum_{r=0}^{m+n} {m+n \choose r} x^r &= \left(\sum_{k=0}^m {m \choose k} x^k\right) \cdot \left(\sum_{l=0}^n {n \choose l} x^l\right) \\ &= \sum_{k=0}^m \sum_{l=0}^n {m \choose k} {n \choose l} x^{k+l} \\ &= \sum_{r=0}^{m+n} \sum_{k+l=r} {m \choose k} {n \choose l} x^r \\ &= \sum_{r=0}^{m+n} \sum_{k=0}^r {m \choose k} {n \choose r-k} x^r. \end{aligned}$