Question Number 4092 by Filup last updated on 28/Dec/15
$$\mathrm{Prove}: \\ $$$$\underset{{k}=\mathrm{1}} {\overset{{n}} {\sum}}\frac{{n}!}{\left({n}−{k}\right)!\:{k}!}=\mathrm{2}^{{n}} −\mathrm{1} \\ $$
Answered by Yozzii last updated on 28/Dec/15
$${According}\:{to}\:{the}\:{Binomial}\:{Theorem}, \\ $$$${for}\:{a},{b}\:{being}\:{numbers}\:{of}\:{any}\:{kind} \\ $$$$\left(\Rightarrow{a},{b}\in\mathbb{C}\right)\:{and}\:{n}\in\mathbb{N}+\left\{\mathrm{0}\right\}, \\ $$$$\left({a}+{b}\right)^{{n}} =\underset{{k}=\mathrm{0}} {\overset{{n}} {\sum}}\left\{\begin{pmatrix}{{n}}\\{{k}}\end{pmatrix}{a}^{{n}−{k}} {b}^{{k}} \right\}\:\:\:\:\:\:\left(\ast\right) \\ $$$${where}\:\begin{pmatrix}{{n}}\\{{k}}\end{pmatrix}=\frac{{n}!}{\left({n}−{k}\right)!{k}!},\:\left(\mathrm{0}\leqslant{k}\leqslant{n}\right). \\ $$$${Observe}\:{that}\:\begin{pmatrix}{{n}}\\{\mathrm{0}}\end{pmatrix}=\begin{pmatrix}{{n}}\\{{n}}\end{pmatrix}=\mathrm{1}. \\ $$$${Suppose}\:{a}={b}=\mathrm{1}.\Rightarrow{a}^{{n}−{k}} =\mathrm{1}^{{n}−{k}} =\mathrm{1} \\ $$$${and}\:{b}^{{k}} =\mathrm{1}^{{k}} =\mathrm{1}.\:\therefore\:{a}^{{n}−{k}} {b}^{{k}} =\mathrm{1}×\mathrm{1}=\mathrm{1} \\ $$$${Also},\:{a}+{b}=\mathrm{1}+\mathrm{1}=\mathrm{2}.\:{Subsituting}\:{this} \\ $$$${information}\:{into}\:\left(\ast\right)\:{we}\:{obtain}\: \\ $$$$\mathrm{2}^{{n}} =\underset{{k}=\mathrm{0}} {\overset{{n}} {\sum}}\left\{\begin{pmatrix}{{n}}\\{{k}}\end{pmatrix}×\mathrm{1}\right\}=\begin{pmatrix}{{n}}\\{\mathrm{0}}\end{pmatrix}+\underset{{k}=\mathrm{1}} {\overset{{n}} {\sum}}\left\{\begin{pmatrix}{{n}}\\{{k}}\end{pmatrix}\right\} \\ $$$$\Rightarrow\underset{{k}=\mathrm{1}} {\overset{{n}} {\sum}}\left\{\begin{pmatrix}{{n}}\\{{k}}\end{pmatrix}\right\}=\mathrm{2}^{{n}} −\mathrm{1}. \\ $$$${Equivalently},\:{we}\:{can}\:{write} \\ $$$$\:\:\:\:\:\:\underset{{k}=\mathrm{1}} {\overset{{n}} {\sum}}\left\{\frac{{n}!}{\left({n}−{k}\right)!{k}!}\right\}=\mathrm{2}^{{n}} −\mathrm{1}.\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\blacksquare \\ $$$$ \\ $$$$ \\ $$$$ \\ $$
Commented by Yozzii last updated on 28/Dec/15
$${Proof}\:{of}\:{Binomial}\:{Theorem}: \\ $$$${Let}\:{P}\left({n}\right)\:{be}\:{the}\:{proposition}\:{that},\forall{n}\in\mathbb{N}+\left\{\mathrm{0}\right\}, \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\left({a}+{b}\right)^{{n}} =\underset{{k}=\mathrm{0}} {\overset{{n}} {\sum}}\begin{pmatrix}{{n}}\\{{k}}\end{pmatrix}{a}^{{n}−{k}} {b}^{{k}} \:\:\:\:\:\:\:\:\:\:\:\:\:\:\left(\ast\right) \\ $$$${where}\:{a},{b}\in\mathbb{C}\:{and}\:\begin{pmatrix}{{n}}\\{{k}}\end{pmatrix}=\frac{{n}!}{\left({n}−{k}\right)!{k}!}\:\:\left(\mathrm{0}\leqslant{k}\leqslant{n}\right). \\ $$$${Let}\:{n}=\mathrm{0}.\Rightarrow{l}.{h}.{s}\:{of}\:\left(\ast\right)=\left({a}+{b}\right)^{\mathrm{0}} =\mathrm{1}. \\ $$$${r}.{h}.{s}=\underset{{k}=\mathrm{0}} {\overset{\mathrm{0}} {\sum}}\begin{pmatrix}{\mathrm{0}}\\{{k}}\end{pmatrix}{a}^{\mathrm{0}−{k}} {b}^{{k}} =\begin{pmatrix}{\mathrm{0}}\\{\mathrm{0}}\end{pmatrix}{a}^{\mathrm{0}−\mathrm{0}} {b}^{\mathrm{0}} =\begin{pmatrix}{\mathrm{0}}\\{\mathrm{0}}\end{pmatrix} \\ $$$$\because\:\begin{pmatrix}{\mathrm{0}}\\{\mathrm{0}}\end{pmatrix}=\frac{\mathrm{0}!}{\left(\mathrm{0}−\mathrm{0}\right)!\mathrm{0}!}=\frac{\mathrm{1}}{\mathrm{0}!×\mathrm{1}}=\frac{\mathrm{1}}{\mathrm{1}}=\mathrm{1} \\ $$$$\Rightarrow{r}.{h}.{s}=\mathrm{1}={l}.{h}.{s}. \\ $$$${Hence},\:{P}\left({n}\right)\:{is}\:{true}\:{when}\:{n}=\mathrm{0}. \\ $$$${Assume}\:{P}\left({n}\right)\:{is}\:{true}\:{when}\:{n}={j}\:\left(>\mathrm{0}\right) \\ $$$$\Rightarrow\left({a}+{b}\right)^{{j}} =\underset{{k}=\mathrm{0}} {\overset{{j}} {\sum}}\begin{pmatrix}{{j}}\\{{k}}\end{pmatrix}{a}^{{j}−{k}} {b}^{{k}} . \\ $$$${For}\:{n}={j}+\mathrm{1}, \\ $$$$\left({a}+{b}\right)^{{j}+\mathrm{1}} =\left({a}+{b}\right)\left({a}+{b}\right)^{{j}} =\left({a}+{b}\right)\left(\underset{{k}=\mathrm{0}} {\overset{{j}} {\sum}}\left\{\begin{pmatrix}{{j}}\\{{k}}\end{pmatrix}{a}^{{j}−{k}} {b}^{{k}} \right\}\right) \\ $$$$\left.\left({a}+{b}\right)^{{j}+\mathrm{1}} =\underset{{k}=\mathrm{0}} {\overset{{j}} {\sum}}\left\{\begin{pmatrix}{{j}}\\{{k}}\end{pmatrix}{a}^{{j}+\mathrm{1}−{k}} {b}^{{k}} \right\}+{b}\underset{{k}=\mathrm{0}} {\overset{{j}} {\sum}}\begin{pmatrix}{{j}}\\{{k}}\end{pmatrix}{a}^{{j}−{k}} {b}^{{k}} \right\} \\ $$$$ \\ $$$${We}\:{acknowledge}\:{the}\:{following}\:{identity} \\ $$$${for}\:\begin{pmatrix}{{j}+\mathrm{1}}\\{{k}}\end{pmatrix}. \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\begin{pmatrix}{{j}+\mathrm{1}}\\{{k}}\end{pmatrix}=\begin{pmatrix}{{j}}\\{{k}}\end{pmatrix}+\begin{pmatrix}{{j}}\\{{k}−\mathrm{1}}\end{pmatrix} \\ $$$${Proof}:\: \\ $$$${The}\:{definition}\:{of}\:\begin{pmatrix}{{n}}\\{{k}}\end{pmatrix}\:{is}\:{used}. \\ $$$$\begin{pmatrix}{{j}}\\{{k}}\end{pmatrix}+\begin{pmatrix}{{j}}\\{{k}−\mathrm{1}}\end{pmatrix}=\frac{{j}!}{\left({j}−{k}\right)!{k}!}+\frac{{j}!}{\left({j}−{k}+\mathrm{1}\right)!\left({k}−\mathrm{1}\right)!} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:=\frac{{j}!}{\left({j}−{k}\right)!\left({k}−\mathrm{1}\right)!}\left\{\frac{\mathrm{1}}{{k}}+\frac{\mathrm{1}}{{j}−{k}+\mathrm{1}}\right\} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:=\frac{{j}!}{\left({j}−{k}\right)!\left({k}−\mathrm{1}\right)!}\left(\frac{{j}+\mathrm{1}−{k}+{k}}{{k}\left({j}+\mathrm{1}−{k}\right)}\right)\: \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:=\frac{{j}!\left({j}+\mathrm{1}\right)}{\left({j}−{k}+\mathrm{1}\right)!{k}!} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:=\frac{\left({j}+\mathrm{1}\right)!}{\left(\left\{{j}+\mathrm{1}\right\}−{k}\right)!{k}!} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:=\begin{pmatrix}{{j}+\mathrm{1}}\\{{k}}\end{pmatrix}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\Box \\ $$$${Note}\:{that}\:\begin{pmatrix}{{n}}\\{{k}}\end{pmatrix}=\mathrm{0}\:{for}\:{k}<\mathrm{0}\: \\ $$$$\therefore\:\left({a}+{b}\right)^{{j}+\mathrm{1}} =\underset{{k}=\mathrm{0}} {\overset{{j}} {\sum}}\left\{\left(\begin{pmatrix}{{j}+\mathrm{1}}\\{{k}}\end{pmatrix}−\begin{pmatrix}{{j}}\\{{k}−\mathrm{1}}\end{pmatrix}\right){a}^{{j}+\mathrm{1}−{k}} {b}^{{k}} +{b}\left({a}+{b}\right)^{{n}} \right. \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:=\underset{{k}=\mathrm{0}} {\overset{{j}} {\sum}}\begin{pmatrix}{{j}+\mathrm{1}}\\{{k}}\end{pmatrix}{a}^{{j}+\mathrm{1}−{k}} {b}^{{k}} +{b}\left({a}+{b}\right)^{{j}} −\underset{{k}=\mathrm{0}} {\overset{{j}} {\sum}}\begin{pmatrix}{{j}}\\{{k}−\mathrm{1}}\end{pmatrix}{a}^{{j}+\mathrm{1}−{k}} {b}^{{k}} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:=\underset{{k}=\mathrm{0}} {\overset{{j}+\mathrm{1}} {\sum}}\left\{\begin{pmatrix}{{j}+\mathrm{1}}\\{{k}}\end{pmatrix}{a}^{{j}+\mathrm{1}−{k}} {b}^{{k}} \right\}−{b}^{{j}+\mathrm{1}} +{b}^{{j}+\mathrm{1}} +\underset{{k}=\mathrm{0}} {\overset{{j}−\mathrm{1}} {\sum}}\left\{\begin{pmatrix}{{j}}\\{{k}}\end{pmatrix}{a}^{{j}−{k}} {b}^{{k}+\mathrm{1}} \right\}−\left(\begin{pmatrix}{{j}}\\{−\mathrm{1}}\end{pmatrix}{a}^{{j}+\mathrm{1}} +\underset{{k}=\mathrm{1}} {\overset{{j}} {\sum}}\left\{\begin{pmatrix}{{j}}\\{{k}−\mathrm{1}}\end{pmatrix}{a}^{{j}+\mathrm{1}−{k}} {b}^{{k}} \right\}\right) \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:=\underset{{k}=\mathrm{0}} {\overset{{j}+\mathrm{1}} {\sum}}\left\{\begin{pmatrix}{{j}+\mathrm{1}}\\{{k}}\end{pmatrix}{a}^{{j}+\mathrm{1}−{k}} {b}^{{k}} \right\}+\mathrm{0}+\begin{pmatrix}{{j}}\\{\mathrm{0}}\end{pmatrix}{a}^{{j}} {b}−\begin{pmatrix}{{j}}\\{\mathrm{0}}\end{pmatrix}{a}^{{j}} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:+\begin{pmatrix}{{j}}\\{\mathrm{1}}\end{pmatrix}{a}^{{j}−\mathrm{1}} {b}^{\mathrm{2}} −\begin{pmatrix}{{j}}\\{\mathrm{1}}\end{pmatrix}{a}^{{j}−\mathrm{1}} {b}^{\mathrm{2}} +\begin{pmatrix}{{j}}\\{\mathrm{2}}\end{pmatrix}{a}^{{j}−\mathrm{2}} {b}^{\mathrm{3}} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:−\begin{pmatrix}{{j}}\\{\mathrm{2}}\end{pmatrix}{a}^{{j}−\mathrm{2}} {b}^{\mathrm{3}} +…+\begin{pmatrix}{{j}}\\{{j}−\mathrm{2}}\end{pmatrix}{a}^{\mathrm{2}} {b}^{{j}−\mathrm{1}} −\begin{pmatrix}{{j}}\\{{j}−\mathrm{2}}\end{pmatrix}{a}^{\mathrm{2}} {b}^{{j}−\mathrm{1}} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:+\begin{pmatrix}{{j}}\\{{j}−\mathrm{1}}\end{pmatrix}{ab}^{{j}} −\begin{pmatrix}{{j}}\\{{j}−\mathrm{1}}\end{pmatrix}{ab}^{{j}} \\ $$$$\Rightarrow\left({a}+{b}\right)^{{j}+\mathrm{1}} =\underset{{k}=\mathrm{0}} {\overset{{j}+\mathrm{1}} {\sum}}\begin{pmatrix}{{j}+\mathrm{1}}\\{{k}}\end{pmatrix}{a}^{{j}+\mathrm{1}−{k}} {b}^{{k}} \\ $$$${Hence},{P}\left({j}+\mathrm{1}\right)\:{is}\:{true},{assuming}\:{P}\left({j}\right) \\ $$$${is}\:{true}.\:{Since}\:{P}\left(\mathrm{0}\right)\:{is}\:{true}\:{then},\:{by}\:{the} \\ $$$${principle}\:{of}\:{mathematical}\:{induction}, \\ $$$${P}\left({n}\right)\:{is}\:{true}\:\forall{n}\in\mathbb{N}+\left\{\mathrm{0}\right\}. \\ $$$$ \\ $$$$ \\ $$$$ \\ $$$$ \\ $$