Question

Let B be set of n elements.

(a) If $\mathit{n}\mathbf{\ge }\mathbf{2}$, prove that the number of two –element subsets of B is $\mathit{n}\frac{\mathbf{(}\mathbf{n}\mathbf{-}\mathbf{1}\mathbf{)}}{\mathbf{2}}$.

(b) If $\mathit{n}\mathbf{\ge }\mathbf{3}$, prove that the number of three –element subsets of is $\mathit{n}\frac{\mathbf{(}\mathbf{n}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{(}\mathit{n}\mathbf{-}\mathbf{2}\mathbf{)}}{3!}$.

(c) Make a conjecture as to the number of K - elements subsets of B when $\mathit{n}\mathbf{\ge }\mathit{k}$. Prove your conjecture.

Short answer

(a) If $n\ge 2$then the number of two element subsets of B is $\frac{n(n-1)}{2}$.

(b) If $n\ge 3$then the number of two-element subsets of B is $\frac{n(n-1)(n-2)}{3!}$.

(c) If $n\ge k$then the number of -element subsets of B is $\frac{n(n-1)(n-2)....\left(n\right(k-1\left)\right)}{k!}$.

Step-by-step solution

(a) Step 1: Proofing the number of two element subsets of B is n(n-1)2 when n≥2

If $n\ge 2$then to prove the number of two element subsets B of is $\frac{n(n-1)}{2}$.

Use the mathematical induction,

Consider, $p\left(n\right)=\frac{n(n-1)}{2}$

Now check for base step substitute $n=2$.

$$\begin{gathered} p\left(2\right)=\frac{2(2-1)}{2} \\ =\frac{2}{2} \\ =1 \end{gathered}$$

Hence, expression is true at n = 2.

Let it is true for n = m

role="math" localid="1659160164004" $p\left(m\right)=\frac{m(m-1)}{2}$

Now, let n = m + 1 then solve as follows:

$$\begin{gathered} p(m+1)=\frac{(m+1)\left(\right(m+1)-1}{2} \\ =\frac{m(m+1)}{2} \end{gathered}$$

Therefore, it is true for n = m + 1.

Hence, if $n\ge 2$then the number of two element subsets of B is $\frac{n(n-1)}{2}$.

(b) Step 2: Proofing the number of two element subsets of B is n(n-1)(n-2)3 !when n≥3.

If $n\ge 3$then to prove the number of two element subsets B of is .

$\frac{n(n-1)\left(\right(n-2)}{3\mathit{!}}$

Use the mathematical induction,

Consider,role="math" localid="1659160846282" $p\left(n\right)=\frac{n(n-1)(n-2)}{3\mathit{!}}$

Now check for base step substitute n = 3.

$$\begin{gathered} p\left(3\right)=\frac{3(3-1)(3-2)}{3\mathit{!}} \\ =\frac{3.2.1}{3.2.1} \\ =1 \end{gathered}$$

Hence, expression is true at n = 3.

Let it is true for n = m:

$p\left(m\right)=\frac{m(m-1)(,-2)}{3\mathit{!}}$

Now, n = m + 1 let then solve as follows:

$$\begin{gathered} p(m+1)=\frac{(m+1)\left(\right(m+1)-1)\left(\right(m+1)-2}{3\mathit{!}} \\ =\frac{m(m+1)(m-1)}{3\mathit{!}} \end{gathered}$$

Therefore, it is true for n = m + 1.

Hence, $n\ge 3$if then the number of two element subsets of is $\frac{n(n+1)(n-1)}{3\mathit{!}}$.

(c) Step 3: Showing conjecture as the number of subsets of B for -elements.

Let -element subset of when $n\ge k$, the number of k -element subset of B then if $n\ge k$then the number of k-element subsets of B is .

$\frac{n(n-1)(n-2)....(n-(k-1\left)\right)}{k\mathit{}\mathit{!}}$

Hence, if $n\ge k$then the number of k -element subsets of B is .

$\frac{n(n-1)(n-2)....(n-(k-1\left)\right)}{k\mathit{}\mathit{!}}$