Question

Show that $\left(\begin{array}{l}n\\ k\end{array}\right)\mathbf{\le }{\mathbf{2}}^{\mathbf{n}}$for all positive integers nand all integers kwith $\mathbf{0}\mathbf{\le }\mathit{k}\mathbf{\le }\mathit{n}$.

Short answer

For all positive integers n and all integers k it's proven that$\left(\begin{array}{l}n\\ k\end{array}\right)\le 2^n$ .

Step-by-step solution

Use Binomial theorem

Binomial theorem: binomial theorem, statement that for any positive integer n, the nth power of the sum of two numbers x and y may be expressed as the sum of n + 1 terms of the form.

$\mathbf{(}\mathit{x}\mathbf{+}\mathit{y}{\mathbf{)}}^{\mathbf{n}}\mathbf{=}\mathbf{\sum }_{\mathbf{j}\mathbf{=}\mathbf{0}}^{\mathbf{n}}\mathbf{ }\left(\begin{array}{l}n\\ j\end{array}\right){\mathit{x}}^{\mathbf{n}\mathbf{-}\mathbf{j}}{\mathit{y}}^{\mathbf{j}}$

To proof:

$\left(\begin{array}{l}n\\ k\end{array}\right)\le 2^n$

For all positive integers  and all integers  with 0≤k≤n

Let n be a positive integer and an k integer with$0\le k\le n$

$\begin{array}{r}{2}^n=(1+1{)}^n\\ =\sum _{j=0}^n \left(\begin{array}{c}n\\ j\end{array}\right)\left(1{)}^{n-j}\right(1{)}^j\\ =\sum _{j=0}^n \left(\begin{array}{c}n\\ j\end{array}\right)\left(1\right)\left(1\right)\\ =\sum _{j=0}^n \left(\begin{array}{c}n\\ j\end{array}\right)\\ \ge \left(\begin{array}{c}n\\ k\end{array}\right)\end{array}$

Thus, .$\left(\begin{array}{l}n\\ k\end{array}\right)\le 2^n$