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}\]
Now add the two expressions
\[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{equation} \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} \end{equation}\]
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}\]
/