StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q15E

Expert-verifiedFound in: Page 421

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}\mathit{k}\mathbf{\le}\mathit{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}$ .

**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{\u200a}}{\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}$

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}\u200a\left(\begin{array}{c}n\\ j\end{array}\right)\left(1{)}^{n-j}\right(1{)}^{j}\\ =\sum _{j=0}^{n}\u200a\left(\begin{array}{c}n\\ j\end{array}\right)\left(1\right)\left(1\right)\\ =\sum _{j=0}^{n}\u200a\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}$

94% of StudySmarter users get better grades.

Sign up for free