$\sum\limits_{k=5}^n {k-1 \choose 4}=\sum\limits_{m=3}^{n-2} {m-1 \choose 2}{n-m \choose 2}$ combinatorial proof

71 Views Asked by At

$\sum\limits_{k=5}^n {k-1 \choose 4}=\sum\limits_{m=3}^{n-2} {m-1 \choose 2}{n-m \choose 2}$

Attempt: left side is choosing 4 balls from each group of 4 to n-1 balls, and right side I don't know

I just got started on combinatorial proofs. I seem pretty clueless on how to start this question, could I get some hint please?

1

There are 1 best solutions below

0
On BEST ANSWER

Both sides yield ${n \choose 5}$.

To choose 5 items from $\{1,\dots,n\}$, you can enumerate over the location $k \in [5,n]$ of the fifth item chosen, then you get the LHS, since you still need to choose 4 items from $\{1,\dots,k-1\}$.

Alternatively, you can enumerate over the location $m \in [3,n-2]$ of the third item chosen, then you get the RHS.