Here's my version of the proof (and where it arose in the context). You have a cyclic graph of size $n$, which is essentially $n$ vertices and a loop passing through them, so that you can think of them as the roots of unity on a circle (I don't want to draw because it would take a lot of time, but it really helps).
You want to count the number of subsets of size $k$ ($0 \le k \le n$) of this graph which contain 3 consecutive vertices (for some random reason that actually makes sense to me, but the rest is irrelevant).
You can fix 3 consecutive vertices, assume that the two adjacent vertices to those 3 are not in the subset, and then place the $k-3$ remaining anywhere else. Or you can fix $4$ consecutive vertices, assume again that the two adjacent vertices to those $4$ are not in the subset, and then place the $k-4$ remaining anywhere else. Or you can fix $5$, blablabla, etc. If you assume $n$ is prime, every rotation of the positions you've just counted gives you a distinct subset of the graph, so that the number of such subsets would be
On the other hand, if you look at it in another way : suppose there is $\ell$ consecutive vertices in your subset. Look at the $3$ vertices in the $\ell$ consecutive ones that are adjacent to a vertex not in your subset, and place the remaining ones everywhere else. Again, the number of such subsets is
If $n$ is not prime, my computations are not accurate (they don't count well what I want to count in my context, but that's another question I'm trying to answer for myself), but I do precisely the same mistakes in both computations! So the two are actually equal. Removing the $n$'s on both lines, replacing $n-5$ and $k-3$ by $N$ and $m$, we get the identity.