Binomial Coefficients Induction

[ifoan]

I have this new problem and I don't know where to start on it. Can anyone give me the heads up?

Let k and n be positive integers with k <= n, and let S be a set with n elements. Show (by induction) that S has \(\displaystyle ( \frac {n} {k} )\) subsets of cardinality k.

Note: \(\displaystyle ( \frac {n} {k} )\) is a binomial coefficient. I couldn't figure out how to write it without the line in the middle.

 

[galactus]

Set theory(A branch of mathematics that leaves a bad taste in my mouth) is not my strong point, but, hopefully, I can get you started with something to ponder.

First, note that:

\(\displaystyle \begin{pmatrix}0\\0\end{pmatrix}=1\)

\(\displaystyle \begin{pmatrix}n\\k\end{pmatrix}=0\), assuming \(\displaystyle k\;\ \notin\;\ {\text{0,1,2,3,...,n}}\)

\(\displaystyle \begin{pmatrix}n\\k\end{pmatrix}=\begin{pmatrix}n-1\\k\end{pmatrix}+\begin{pmatrix}n-1\\k-1\end{pmatrix}\), \(\displaystyle n\geq{1}\)

If we try n=0, we find it has as its only element, \(\displaystyle \emptyset\). The \(\displaystyle \emptyset\) is the only subset of size 0.

If \(\displaystyle n\;\ \geq\;\ {1}\), there are 2 types of subsets having k elements. Those that have 1 and those that don't.

There are as many subsets with k elements({1,....,n}) which have 1 as there are subsets of k-1 elements from({2,...,n}), \(\displaystyle \begin{pmatrix}n-1\\k-1\end{pmatrix}\).

There are as many subsets of k elements from ({1,...,n}) without 1 as there are subsets of k elements from ({2,...,n}), \(\displaystyle \begin{pmatrix}n-1\\k\end{pmatrix}\)

Ergo, the number of subsets of n which have k elements is \(\displaystyle \begin{pmatrix}n-1\\k\end{pmatrix}+\begin{pmatrix}n-1\\k-1\end{pmatrix}=\begin{pmatrix}n\\k\end{pmatrix}\)

I hope this is on the right track, at least. I had seen this proof before and dug it out of some old homework papers from the 'way back' times.

 

[pka]

Having taught logic & theory of sets many times, I do find this an oddly put problem. The direct proof by induction will be very tedious. You do realize that you will need to show that it is true for each k from 0 to n at each step in the induction.

We normally show by induction that is a set, S, has n elements then S has 2<SUP>n</SUP> subsets. That is a wonderful little proof that works quite differently from most induction proofs. Having done that we note the binomial expansion
\(\displaystyle \begin{array}{l}
\left( {x + y} \right)^n = \sum\limits_{k = 0}^n {\left( {\begin{array}{c}
n \\
k \\
\end{array}} \right)} x^k y^{n - k} \\
x = 1\quad \& \quad y = 1 \\
\Rightarrow \left( 2 \right)^n = \sum\limits_{k = 0}^n {\left( {\begin{array}{c}
n \\
k \\
\end{array}} \right)} \\
\end{array}.\)
Thus we get your result in a round about way.

BTW: In your post you want the type the binomial coefficient.
Type: \(\displaystyle {n \choose k} \)

 

[galactus]

pka, is my approach anywhere near viable?. Some friendly criticism would be welcome. I always detested set theory, but now I would like to learn more myself.