Question

Show that if nand kare integers with$\mathbf{1}\mathbf{\le }\mathit{k}\mathbf{\le }\mathit{n}$, then$\left(\begin{array}{l}n\\ k\end{array}\right)\mathbf{\le }{\mathit{n}}^{\mathbf{k}}\mathbf{/}{\mathbf{2}}^{\mathbf{k}\mathbf{-}\mathbf{1}}$

Short answer

$\left(\begin{array}{l}n\\ k\end{array}\right)\le n^k/2^{k-1}\text{for}n\text{and}k$are integers with$1\le k\le n$

Step-by-step solution

The given expression

n and k are integers with$1\le k\le n$

To prove:$\left(\begin{array}{l}n\\ k\end{array}\right)\le n^k/2^{k-1}$

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

$\begin{array}{r}\left(\begin{array}{l}n\\ k\end{array}\right)=\frac{n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 2\cdot 1}\\ =n\cdot \prod _{i=1}^{k-1} \frac{n-i}{k-i+1}<n\cdot \prod _{i=1}^{k-1} \frac{n}{2}\\ n\cdot \prod _{i=1}^{k-1} \frac{n}{2}=n\cdot {\left(\frac{n}{2}\right)}^{k-1}\\ =\frac{n^k}{2^{k-1}}\end{array}$

Thus,$\left(\begin{array}{l}n\\ k\end{array}\right)\le n^k/2^{k-1}\mid$