Q. 1.9 - A First Course in Probability

Question

Use Theoretical Exercise 8 to prove that

$\left(\begin{array}{c}2n\\ n\end{array}\right)=\sum _{k=0}^n{\left(\begin{array}{c}n\\ k\end{array}\right)}^2$

Step-by-Step Solution

Answer

It is proved that $\left(\begin{array}{c}2n\\ n\end{array}\right)=\sum _{k=0}^n{\left(\begin{array}{c}n\\ k\end{array}\right)}^2$

Step 1. State the Theoretical Exercise 8.

According to Theoretical Exercise 8,

$\left(\begin{array}{c}n+m\\ r\end{array}\right)=\left(\begin{array}{c}n\\ 0\end{array}\right)\left(\begin{array}{c}m\\ r\end{array}\right)+\left(\begin{array}{c}n\\ 1\end{array}\right)\left(\begin{array}{c}m\\ r-1\end{array}\right)+....+\left(\begin{array}{c}n\\ r\end{array}\right)\left(\begin{array}{c}m\\ 0\end{array}\right)$...................... (1)

Step 2. Prove the given equation.

By substituting $m=n$ and $r=n$ in equation (1), we get

$\left(\begin{array}{c}n+n\\ n\end{array}\right)=\left(\begin{array}{c}n\\ 0\end{array}\right)\left(\begin{array}{c}n\\ n\end{array}\right)+\left(\begin{array}{c}n\\ 1\end{array}\right)\left(\begin{array}{c}n\\ n-1\end{array}\right)+....+\left(\begin{array}{c}n\\ n\end{array}\right)\left(\begin{array}{c}n\\ 0\end{array}\right)$

$\left(\begin{array}{c}2n\\ n\end{array}\right)=\left(\begin{array}{c}n\\ 0\end{array}\right)\left(\begin{array}{c}n\\ n\end{array}\right)+\left(\begin{array}{c}n\\ 1\end{array}\right)\left(\begin{array}{c}n\\ n-1\end{array}\right)+....+\left(\begin{array}{c}n\\ n\end{array}\right)\left(\begin{array}{c}n\\ 0\end{array}\right)$.......................... (2)

We know that,

${}^{n}C_r={}^{n}C_{n-r}$............................. (3)

Substituting (3) in (2), we get

$\left(\begin{array}{c}2n\\ n\end{array}\right)={\left(\begin{array}{c}n\\ 0\end{array}\right)}^2+{\left(\begin{array}{c}n\\ 1\end{array}\right)}^2+....+{\left(\begin{array}{c}n\\ n\end{array}\right)}^2$

Therefore, it is proved that $\left(\begin{array}{c}2n\\ n\end{array}\right)=\sum _{k=0}^n{\left(\begin{array}{c}n\\ k\end{array}\right)}^2$.