## Proof of Binomial Identity

To prove
$S= \begin{pmatrix}n\\1\end{pmatrix}+2 \begin{pmatrix}n\\2\end{pmatrix}+...+k \begin{pmatrix}n\\k\end{pmatrix}+...+n \begin{pmatrix}n\\n\end{pmatrix}$

Write the sum as
$S= 0 \begin{pmatrix}n\\0\end{pmatrix}+1 \begin{pmatrix}n\\1\end{pmatrix}+2 \begin{pmatrix}n\\2\end{pmatrix}+...+k \begin{pmatrix}n\\k\end{pmatrix}+...+n \begin{pmatrix}n\\n\end{pmatrix}$
.
Reverse the order and add the two expressions.
$S= n \begin{pmatrix}n\\n\end{pmatrix}+...+k \begin{pmatrix}n\\k\end{pmatrix}+...+2 \begin{pmatrix}n\\2\end{pmatrix}+1 \begin{pmatrix}n\\1\end{pmatrix}+0 \begin{pmatrix}n\\0\end{pmatrix}$

$2S=(0 \begin{pmatrix}n\\0\end{pmatrix}+ n \begin{pmatrix}n\\1\end{pmatrix})+...+((n-k) \begin{pmatrix}n\\n-k\end{pmatrix}+k \begin{pmatrix}n\\k\end{pmatrix})+...+((n-2)\begin{pmatrix}n\\n-2\end{pmatrix}+ 2 \begin{pmatrix}n\\2\end{pmatrix})+...+((n-1) \begin{pmatrix}n\\q\end{pmatrix}+1 \begin{pmatrix}n\\1\end{pmatrix})+(n \begin{pmatrix}n\\q\end{pmatrix}+0 \begin{pmatrix}n\\0\end{pmatrix}$

Use
$\begin{pmatrix}n\\m\end{pmatrix}=\frac{n!}{m!(n-m)!}=\frac{n!}{(n-m)!m!}=\begin{pmatrix}n\\n-m\end{pmatrix}$
.
Then
\begin{aligned} 2S &= n \begin{pmatrix}n\\n\end{pmatrix}+...+n \begin{pmatrix}n\\k\end{pmatrix}+...+n\begin{pmatrix}n\\2\end{pmatrix}+n \begin{pmatrix}n\\1\end{pmatrix}+n \begin{pmatrix}n\\0\end{pmatrix} \\ &= n(\begin{pmatrix}n\\n\end{pmatrix}+...+ \begin{pmatrix}n\\k\end{pmatrix})+...+\begin{pmatrix}n\\2\end{pmatrix}+ \begin{pmatrix}n\\1\end{pmatrix})+ \begin{pmatrix}n\\0\end{pmatrix}) \end{aligned}

Now use the identity
$\begin{pmatrix}n\\n\end{pmatrix}+...+ \begin{pmatrix}n\\k\end{pmatrix})+...+\begin{pmatrix}n\\2\end{pmatrix}+ \begin{pmatrix}n\\1\end{pmatrix})+ \begin{pmatrix}n\\q\end{pmatrix}=2^n$
. Hence
$2S=n2^n \rightarrow S=n2^{n-1}$
/