I need to prove: $$\sum_{k=0}^{n} {k\choose 2}\cdot{{n-k}\choose 2} = \sum_{k=0}^{n} {k\choose 3}\cdot(n-k).$$
I wasn't able to have any progress with algebra, I tried to think about a combinatorical proof:
Let's imagine there are $n$ people in a row and we need to choose $4.$ One way will be to take the $k$ "leftest" people, choose $2$ of them, and choose $2$ from the $n-k$ left. That way we get the left sum.
The second way will be similar, look at the "leftest" $k$ people and choose $3$ of them, and then choose $1$ from the $n-k$ left. That gives the right side of the equation.
The only problem with this proof is that some of the options are counted twice and more, so it is not equal to ${n\choose 4.}$
Can someone help please? I would love to see both algebric and combinatorical proofs.
Pick five people from a row of $n+1$. The first sum counts the possibilities based on the position of the middle person. The second counts them based on the position of the fourth person.