# How do we prove that ((n),(k))=sum_(l=k)^n((l-1),(k-1))?

Dec 27, 2016

Use the identity $\left(\begin{matrix}n \\ k\end{matrix}\right) = \left(\begin{matrix}n - 1 \\ k\end{matrix}\right) + \left(\begin{matrix}n - 1 \\ k - 1\end{matrix}\right)$. See below for details.

#### Explanation:

Recall the identity $\left(\begin{matrix}n \\ k\end{matrix}\right) = \left(\begin{matrix}n - 1 \\ k\end{matrix}\right) + \left(\begin{matrix}n - 1 \\ k - 1\end{matrix}\right)$

To prove this as ((n),(k))=(n!)/(k!(n-k)!)

=(nxx(n-1)!)/(kxx(k-1)!(n-k)(n-k-1)!)

=((n-1)!)/((k-1)!(n-k-1)!)[n/(k(n-k))]

=((n-1)!)/((k-1)!(n-k-1)!)[((n-k)+k)/(k(n-k))]

=((n-1)!)/((k-1)!(n-k-1)!)[1/k+1/(n-k)]

=((n-1)!)/(k(k-1)!(n-k-1)!)+((n-1)!)/(k(k-1)!(n-k)(n-k-1)!)

=((n-1)!)/(k!(n-k-1)!)+((n-1)!)/(k!(n-k)!)=((n-1),(k))+((n-1),(k-1))

Hence $\left(\begin{matrix}n \\ k\end{matrix}\right) = \left(\begin{matrix}n - 1 \\ k\end{matrix}\right) + \left(\begin{matrix}n - 1 \\ k - 1\end{matrix}\right)$, bur from this we get

$\left(\begin{matrix}n - 1 \\ k - 1\end{matrix}\right) = \left(\begin{matrix}n - 2 \\ k - 1\end{matrix}\right) + \left(\begin{matrix}n - 2 \\ k - 2\end{matrix}\right)$

Hence $\left(\begin{matrix}n \\ k\end{matrix}\right) = \left(\begin{matrix}n - 1 \\ k\end{matrix}\right) + \left(\begin{matrix}n - 2 \\ k - 1\end{matrix}\right) + \left(\begin{matrix}n - 2 \\ k - 2\end{matrix}\right)$

Now similarly split $\left(\begin{matrix}n - 2 \\ k - 2\end{matrix}\right)$ into

$\left(\begin{matrix}n - 2 \\ k - 2\end{matrix}\right) = \left(\begin{matrix}n - 3 \\ k - 2\end{matrix}\right) + \left(\begin{matrix}n - 3 \\ k - 3\end{matrix}\right)$ and

$\left(\begin{matrix}n \\ k\end{matrix}\right) = \left(\begin{matrix}n - 1 \\ k\end{matrix}\right) + \left(\begin{matrix}n - 2 \\ k - 1\end{matrix}\right) + \left(\begin{matrix}n - 3 \\ k - 2\end{matrix}\right) + \left(\begin{matrix}n - 3 \\ k - 3\end{matrix}\right)$

Going on similarly, we get

$\left(\begin{matrix}n \\ k\end{matrix}\right) = {\sum}_{l = k}^{n} \left(\begin{matrix}l - 1 \\ k - 1\end{matrix}\right)$