• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q15E

Expert-verified Found in: Page 421 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Show that $\left(\begin{array}{l}n\\ k\end{array}\right){\mathbf{\le }}{{\mathbf{2}}}^{{\mathbf{n}}}$ for all positive integers n and all integers k with $\mathbf{0}\mathbf{\le }\mathbit{k}\mathbf{\le }\mathbit{n}$ .

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}$ .

See the step by step solution

## Step 1: 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{\left(}}{\mathbit{x}}{\mathbf{+}}{\mathbit{y}}{\mathbf{\right)}}^{\mathbf{n}}{\mathbf{=}}\mathbf{\sum }_{\mathbf{j}\mathbf{=}\mathbf{0}}^{\mathbf{n}}{\mathbf{ }}\left(\begin{array}{l}n\\ j\end{array}\right){{\mathbit{x}}}^{\mathbf{n}\mathbf{-}\mathbf{j}}{{\mathbit{y}}}^{{\mathbf{j}}}$

To proof:

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

## Step 2: 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}=\left(1+1{\right)}^{n}\\ =\sum _{j=0}^{n} \left(\begin{array}{c}n\\ j\end{array}\right)\left(1{\right)}^{n-j}\left(1{\right)}^{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}$ ### Want to see more solutions like these? 