Chapter 2.2, Problem 40E

Exercise $37-39$ can be generalized as follows: If $0\le k\le n$ and the set $A$ has $n$ elements, then the number of elements of the power set $P(A)$ containing exactly $k$ elements is $\left(\begin{array}{l}n\\ k\end{array}\right)$.

Use this result to write an expression for the total number of elements in the power set $P(A)$.

Use the binomial theorem as stated in Exercise 25 to evaluate the expression in part a and compare this result to exercise 27 and 37. (Hint: set $a=b=1$ in the binomial theorem.)

If $n$ is a nonnegative integer and the set $A$ has $n$ elements, then the power set $P(A)$ has $2^n$

If $n\ge 2$ and the set $A$ has $n$ elements, then the number of elements of the power set $P(A)$ containing exactly two elements is $\left(\begin{array}{l}n\\ 2\end{array}\right)=\frac{n(n-1)}{2}$.

If $n\ge 3$ and the set $A$ has $n$ elements, then the number of elements of the power set $P(A)$ containing exactly three elements is $\left(\begin{array}{l}n\\ 3\end{array}\right)=\frac{n(n-1)(n-2)}{3!}$.

Let $a$ and $b$ be a real number, and let $n$ be integers with $0\le r\le n$. The binomial theorem states that

${\left(a+b\right)}^n=\left(\begin{array}{l}n\\ 0\end{array}\right)a^n+\left(\begin{array}{l}n\\ 1\end{array}\right)a^{n-1}b+\left(\begin{array}{l}n\\ 2\end{array}\right)a^{n-2}{b}^2+\mathrm{...}+\left(\begin{array}{l}n\\ r\end{array}\right)a^{n-r}{b}^r+\mathrm{.......}+\left(\begin{array}{l}n\\ n-2\end{array}\right)a^2{b}^{n-2}+\left(\begin{array}{c}n\\ n-1\end{array}\right)a{b}^{n-1}+\left(\begin{array}{c}n\\ n\end{array}\right)b^n$

$={\displaystyle \underset{r=0}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ r\end{array}\right)}{a}^{n-r}{b}^r$

Where the binomial coefficients $\left(\begin{array}{l}n\\ r\end{array}\right)$ are defined by

$\left(\begin{array}{l}n\\ r\end{array}\right)=\frac{n!}{(n-r)!r!}$,

With $r!=r(r-1)\mathrm{.........}(2)(1)$ for $r\ge 1$ and $0!=1$. Prove that the binomial coefficients satisfy the equation

$\left(\begin{array}{l}n\\ r-1\end{array}\right)+\left(\begin{array}{l}n\\ r\end{array}\right)=\left(\begin{array}{l}n+1\\ r\end{array}\right)$ for $1\le r\le n$