Combinatorial proof of an identity involving binomial coefficients $\sum_{k=3}^n {k \choose 3} = {n +1\choose4}$

Question

My problem is that I need to give a combinatorial proof to show both sides are equal for this equation:

$\sum_{k=3}^n {k \choose 3} = {n +1\choose4}$

I have simplified it into: $\sum_{k=3}^{n} \frac{k!}{3!(k-3)!} = \frac{(n+1)!}{4!(n-3)!}$

I understand that (especially when summed) $k! = (n+1)!$ and $(k-3)(n-3)!$ but I don't understand how to show that these two equal each other and what to do with the $4!$.

Answer 1

@robjohn already provided one most adequate link to Wikipedia's article on the identity. Still, I wanted to provide some ways in which one can try to come up with such combinatorial proofs.

When we look at the right side of the identity and we will see only one combinatorial number, which is counting the ways in which we can choose $4$ elements from $n+1$. Now we can try to interpret the left side of the identity as another way of counting how to choose $4$ elements from $n+1$.

Look at the left side of the identity, and you will find:

1. a summation, which indicates that while counting we have decided to separate in different cases, and
2. combinatorial numbers, which suggest that we are choosing from $k$ elements subsets of $3$.

Can you now come up with an explanation of how the left side of the identity counts the ways of choosing $4$ elements from $n+1$?

As provided by @robjohn, one proof these tips may have made us suspect existed.