Which of these is larger by combinatorial reasoning

Question

Determine which of the following expression's is larger using a combinatorial reasoning $$\binom{n}{k}-\binom{n-3}{k}$$ and $$\binom{n-1}{k-1}+\binom{n-2}{k-1}+\binom{n-3}{k-1}$$I can solve this algebraicly however I need to determine which is larger using combinatorial reasoning which is something I'm not very good at, If someone could provide some advice on how to approach these kind of problems, it would be greatly appreciated. Thanks in advance :)

Answer 1

As usual let $[n]=\{1,2,\ldots,n\}$.

First, $\binom{n}k-\binom{n-3}k$ is the number of $k$-element subsets of $[n]$ that are not subsets of $[n-3]$, so it’s the number of $k$-element subsets of $[n]$ that contain at least one of the numbers $n,n-1$, and $n-2$. Note that these are precisely the $k$-element subsets of $[n]$ that have one of $n,n-1$, and $n-2$ as largest element.

$\binom{n-1}{k-1}$ is the number of $(k-1)$-element subsets of $[n-1]$, so it’s the number of $k$ element subsets of $[n]$ that have $n$ as largest element. $\binom{n-2}{k-1}$ is the number of $(k-1)$-element subsets of $[n-2]$, so it’s the number of $k$-element subsets of $[n]$ that have $n-1$ as largest element. And $\binom{n-3}{k-1}$ is the number of $(k-1)$-element subsets of $[n-3]$, so it’s the number of $k$-element subsets of $[n]$ that have $n-2$ as largest element. The sum of these three binomial coefficients is therefore the number of $k$-element subsets of $[n]$ that have one of $n,n-1$, and $n-2$ as largest element, and the two expressions are equal.

Answer 2

Do you consider this cheating? First, observe that $$ \binom{m}{l}=\binom{m-1}{l}+\binom{m-1}{l-1}\tag{$*$} $$ which can be proved by a counting argument. (Let $A$ be a set of $m$ objects and fix a particular object $\spadesuit$ in $A$, then any selection of $l$ objects from $A$ either contains $\spadesuit$ or doesn't. There are $\binom{m-1}{l}$ selections of the former type and $\binom{m-1}{l-1}$ selections of the latter type.)

Now, use $(*)$ a few times \begin{aligned} \binom{n-1}{k-1}+\binom{n-2}{k-1}+\binom{n-3}{k-1}+\binom{n-3}{k}&=\binom{n-1}{k-1}+\binom{n-2}{k-1}+\binom{n-2}{k}\\ &=\binom{n-1}{k-1}+\binom{n-1}{k}\\ &=\binom{n}{k} \end{aligned} to realize that your original two expressions are equal.

Answer 3

First of all, the 2 quantities that you have written in the question are equal. $$\begin{align}\binom nk-\binom{n-3}k&=\binom{n-1}{k-1}+\binom{n-1}k-\binom{n-3}k\\&=\binom{n-1}{k-1}+\binom{n-2}{k-1}+\binom{n-2}{k}-\binom{n-3}{k}\\&=\binom{n-1}{k-1}+\binom{n-2}{k-1}+\binom{n-3}{k-1}+\binom{n-3}{k}-\binom{n-3}{k}\\&=\binom{n-1}{k-1}+\binom{n-2}{k-1}+\binom{n-3}{k-1}\end{align}$$ So algebraically we have proved that they are the same quantities.

Now to look at it in the view of combinatorics, $\binom nk$ is the number of ways of selecting a group of $k$ people out of $n$. So your first expression shows the number of ways of selecting a group of $k$ people with at least one of $3$ special people, say person $A, B, C$.

But this can be done in another way. Say you already select the person $A$ and put him into the group of $k$ people. So now you have to choose $k-1$ people out of $n-1$ people (which includes $B$ and $C$).

Then you select $B$ and put him into a group and don't put $A$ into that group. This ensures that you don't overcount the cases in which $A$ and $B$ are present in a group. So now you have to choose $k-1$ people to put in the group from $n-2$ people (which contains the person $C$ also).

Then you select $C$ and put him into the group of $k$ people and remove $A$ and $B$ from that group. This ensures that the cases of all $3$ being present in the group are not overcounted. So to form the group you need to choose $k-1$ people from the remaining $n-3$ people.

Hence if you sum up these $3$ cases, then you get the second expression in your question which is another way of forming a group of $k$ people with at least one of $3$ special people in a gathering of $n$ people.