summation - Proof of the binomial identity $displaystylebinom{m}{n}=sum_{k=0}^{lfloor n/2 rfloor} 2^{1-delta_{k,n-k}} binom{m/2}{k} binom{m/2}{n-k}$

Trying to prove some uncorrelated things, I came across the following identity:
$$\binom{m}{n}=\sum_{k=0}^{\lfloor n/2 \rfloor} 2^{1-\delta_{k,n-k}} \binom{m/2}{k} \binom{m/2}{n-k}, $$
where $\delta_{i,j}$ is the Kronecker delta, equal to 1 if $i=j$ and vanishing otherwise.
This identity seems to hold for every $m$ and $n$ (I checked it with Mathematica for each pair of integers $n, m$ from 1 up to 100).

I've never seen such an identity, and it doesn't seem straightforward to prove.

Is this some known identity? And how could I go in proving (or disproving) it?

Answer

It's true. The number of ways we can pick $n$ things from $m$ is:

Divide the $m$ things into two half-sized chunks. Then we need to do one of the following:

• pick at most $n/2$ things out of the first chunk (say we pick $k$ from the first chunk), and the remaining $n-k$ things out of the second chunk;



• pick at most $n/2$ things out of the second chunk, and the remaining $n-k$ things out of the first chunk.

By symmetry, we take care of the second case by simply doubling all terms from the first case for which $k \not = n-k$.