Prove that ${n\choose 2}2^{n-2}=\sum\limits_{k=2}^{n}{n\choose k}{k\choose 2}$ for all $n\geq 2$
Answer
Assume that there if going to be a party and you have $n$ friends, and $2$ out of your $n$ friends will go and bring pizza. The remaining $n-2$ may or may not go to the party. The total number of ways that your friends may go to the party and bring pizza is
\[{n \choose2}2^{n-2}.\]
Indeed there are ${n \choose2}$ ways to choose the two friends who would bring pizza, and the remaining $(n-2)$ each have 2 options i.e. they may or may not go to the party which gives $2^{n-2}$ possibilities.
We can count the total number of ways that your friends may go to the party and bring pizza in a different way. A total number k, $k\geq 2$, may attend the party and two of them will bring pizza. The number of possibilities are
\[{n \choose k}{k \choose2}.\]
Summing over $k$ we get
\[\sum_{k=2}^{n}{n \choose k}{k \choose2}.\]
Hence
\[{n \choose2}2^{n-2}=\sum_{k=2}^{n}{n \choose k}{k \choose2}.\]
Indeed there are ${n \choose k}$ ways to choose $k$ friends who would go to the party, and we can choose $2$ poeple from the $k$ people who are going to the party in ${k \choose 2}$ ways to bring pizza.
\[{n \choose2}2^{n-2}.\]
Indeed there are ${n \choose2}$ ways to choose the two friends who would bring pizza, and the remaining $(n-2)$ each have 2 options i.e. they may or may not go to the party which gives $2^{n-2}$ possibilities.
We can count the total number of ways that your friends may go to the party and bring pizza in a different way. A total number k, $k\geq 2$, may attend the party and two of them will bring pizza. The number of possibilities are
\[{n \choose k}{k \choose2}.\]
Summing over $k$ we get
\[\sum_{k=2}^{n}{n \choose k}{k \choose2}.\]
Hence
\[{n \choose2}2^{n-2}=\sum_{k=2}^{n}{n \choose k}{k \choose2}.\]
Indeed there are ${n \choose k}$ ways to choose $k$ friends who would go to the party, and we can choose $2$ poeple from the $k$ people who are going to the party in ${k \choose 2}$ ways to bring pizza.
443
The answer is accepted.
Join Matchmaticians Affiliate Marketing
Program to earn up to a 50% commission on every question that your affiliated users ask or answer.
- answered
- 6268 views
- $8.00
Related Questions
- Integral of trig functions
- Custom Solutions to Stewart Calculus Problems, 9th Edition
- Algebra Question
- Foreign Carnival Systems Algebra Problem
- 10 questions Differential Equations
- Given that $-6x \equiv -8 \pmod{7}$, show that $x \equiv 6 \pmod{7}$
- There are two questions about calculus
- highschool class help