Suppose that $A$ is an $n$-set. How many subsets does $A$ have that exist of exactly $k$ elements, where $0\leq k\leq n$?

Question

Suppose that $A$ is an $n$-set. How many subsets does A have that exist of exactly k elements, where $0\leq k\leq n$?

I found the answer to be $\frac{n-k}{k+1}$

For this problem I have to prove that my answer is true.

I tried a proof by induction but I have no clue how I would write the Inductive case.

For the base case I let $n=1$ and $k=1$ and I got $0$ because $\frac{0}{1} = 0$

Answer 1

What you need to do is choose k elements from your n-set. For each choice, you have a different subset of A. You start of by choosing k elements. To know how many different choices you have, look at the number of possibilities for each element:

To choose the first one, you have n possibilities

For the second, you have n-1 possibilities,

...

For the k-th element, you have n-k+1 possibilities

Therefore, the number of possibilities you have is:

$n*(n-1)*(n-2)*...*(n-k+1) = \frac{n!}{(n-k)!}$,

Where $n! = n*(n-1)*...*3*2*1 = \prod_{k=1}^n k$

Now, because order does not matter in a set, you have to take all the permutations out of your k-sets. You do that by dividing your total amount by the permutation of k distinct elements, which is $k!$ Therefore, the number of subsets of A with k elements is given by:

$\frac{n!}{k!(n-k)!}$

Answer 2

By definition, the answer is just $n \choose k$. It can also be proven that this is equal to $\frac{n!}{k!(n-k)!}$, and of course the triangle of such numbers is known as Pascal's triangle.