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
As usual let $[n]=\{1,2,\ldots,n\}$.
First, $\binom{n}k-\binom{n-3}k$ is the number of $3$-element subsets of $[n]$ that are not subsets of $[n-3]$, so it’s the number of $3$-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.
No comments:
Post a Comment