Number of Subsets of Cardinality at most $k$ of a Finite Set

Question

Let $I$ be a finite set, $k \in \mathbb{N}$ and $2 \leq k \leq \lvert I \rvert$. Then, the number of subsets of $I$ that have cardinality at most $k$ is bounded above by $\lvert I \rvert^k$, i.e.

\begin{equation*} \sum_{S \subseteq I, \vert S \vert \leq k}1 \leq \lvert I \rvert^k. \end{equation*}

My proof considers two cases:

If $k = 2$, \begin{equation*} \sum_{S \subseteq I, \vert S \vert \leq k} = 1 + \vert I \vert + \frac{\vert I \vert(\vert I \vert-1)}{2} \leq \vert I \vert^k. \end{equation*} If $k \geq 3$, \begin{equation*} \sum_{S \subseteq I, \vert S \vert \leq k} = \sum_{i = 0}^k {\vert I \vert \choose i} < 1 + \vert I \vert + \vert I \vert^{k-1}(\vert I \vert - 1) < \vert I \vert^k. \end{equation*}

I think this proof is not very elegant. Is there a better way of doing it?

Thanks in advance!

Answer 1

Here is a combinatorial proof of your inequality. $|I|^k$ is equal to the number of sequences $(i_1,i_2,\dots,i_k)$ where $i_j\in I$ for each $j\in \{1,\dots,k\}$. Given such a sequence, if you delete duplicate elements (keeping one copy of each element that appears), and ignore order, then what remains is a nonempty subset of $i$ with size at most $k$. Since every nonempty subset with size at most $k$ can be obtained in this way, this proves that $$ \binom{|I|}1+\binom{|I|}2 + \dots+\binom{|I|}k\le |I|^k $$ This is not quite what you want, since this is missing the $\binom{|I|}0$ term on the left. Fortunately, as long as $k\ge 2$ and $|I|\ge 2$, some subsets will be obtained more than once, so you can add a $+1$ to the left hand side and still have this hold true. Note that when $k=1$, the inequality you want to prove is actually false.