Show $\binom{n}{[n/2]} = \binom{n-1}{[(n-1)/2]} + \sum_{i=0}^{[n/2] - 1} \frac{1}{i+1} \binom{2i}{i} \binom{n-2i-2}{[n/2]- i - 1}$

Question

The identity $$\binom{n}{\lfloor n/2\rfloor} = \binom{n-1}{\lfloor (n-1)/2\rfloor} + \sum_{i=0}^{\lfloor n/2\rfloor - 1} \frac{1}{i+1} \binom{2i}{i} \binom{n-2i-2}{\lfloor n/2\rfloor - i - 1}$$ came up in a certain combinatorial calculation. Here $n \in \mathbb{Z}_{\geq 0}$. Surely this must be listed in some reference work, though I didn't see it when looking through various sources (Wikpedia, Gould's combinatorial identities, MathWorld, etc.).

It looks to me like a discrete fundamental theorem of calculus identity. It may also be related to the Gamma function at half-integers, e.g. Mathematica simplifies the sum when $n=2k$ to $$2^{2k-1} \frac{\Gamma\left(\frac{1}{2} + k\right)}{k!}.$$

Answer 1

In trying to evaluate

$$\sum_{q=0}^{\lfloor n/2 \rfloor -1} \frac{1}{q+1} {2q\choose q} {n-2q-2\choose \lfloor n/2 \rfloor - q - 1}$$

we get for $n=2m$

$$\sum_{q=0}^{m -1} \frac{1}{q+1} {2q\choose q} {2m-2q-2\choose m - q - 1} \\ = [z^{m-1}] (1+z)^{2m-2} \sum_{q=0}^{m -1} \frac{1}{q+1} {2q\choose q} z^q (1+z)^{-2q}.$$

We will use formal power series throughout. Here the coefficient extractor enforces the range and we recognize the Catalan number OGF

$$C(w) = \frac{1-\sqrt{1-4w}}{2w}$$

so that we obtain

$$ [z^{m-1}] (1+z)^{2m-2}\sum_{q\ge 0} \frac{1}{q+1} {2q\choose q} z^q (1+z)^{-2q} \\ = [z^{m-1}] (1+z)^{2m-2} \frac{1-\sqrt{1-4z/(1+z)^2}}{2z/(1+z)^2} \\ = [z^{m-1}] (1+z)^{2m-1} \frac{1+z-\sqrt{(1+z)^2-4z}}{2z} \\ = [z^{m-1}] (1+z)^{2m-1} \frac{1+z-(1-z)}{2z} = [z^{m-1}] (1+z)^{2m-1} = {2m-1\choose m-1}.$$

Similarly for $n=2m+1$ we get

$$\sum_{q=0}^{m -1} \frac{1}{q+1} {2q\choose q} {2m+1-2q-2\choose m - q - 1} = {2m\choose m-1}.$$

Joining these two we get the closed form

$$\bbox[5px,border:2px solid #00A000]{ {n-1\choose \lfloor n/2 \rfloor - 1}.}$$

We still have to verify two cases, from the given formula for the sum which is

$${n\choose \lfloor n/2\rfloor}-{n-1\choose \lfloor (n-1)/2\rfloor}$$

first for $n=2m$

$${2m\choose m} - {2m-1\choose m-1} = {2m-1\choose m-1}$$

which is $\frac{2m}{m} {2m-1\choose m-1} = 2 {2m-1\choose m-1}$

and holds by inspection and second for $n=2m+1$

$${2m+1\choose m} - {2m\choose m} = {2m\choose m-1}$$

which also holds by inspection.

Answer 2

For what it's worth, here's my own generating function approach.

Let $$A(x) := \sum_{i=0}^\infty \frac{1}{i+1} \binom{2i}{i} x^{2i}$$ and $$B(x) := \sum_{j=0}^\infty \binom{j}{\lfloor j/2\rfloor} x^j = \sum_{j'=0}^\infty \binom{2j'}{j'} x^{2j'} + \sum_{j''=0}^\infty \binom{2j''+1}{j''+1} x^{2j''+1}.$$

The sum in the desired identity is $[x^{n-2}] A(x)B(x) = [x^n] x^2 A(x)B(x)$.

From the standard identity $\sum_{a=0}^\infty \binom{2i}{i} x^i = \frac{1}{\sqrt{1-4x}}$, it quickly follows that $A(x) = \frac{1-\sqrt{1-4x^2}}{2x^2}$ and $B(x) = \frac{2}{1-2x+\sqrt{1-4x^2}}$. On the other hand, $$\sum_{n=0}^\infty \left(\binom{n}{\lfloor n/2\rfloor} - \binom{n-1}{\lfloor (n-1)/2\rfloor}\right) x^n = B(x) - xB(x) - 1.$$ Thus the identity is equivalent to $$(1-x)B(x)-1 = x^2A(x)B(x),$$ which is easily checked.

(Strictly speaking, one can avoid explicitly computing $A(x)$ and $B(x)$ and just express them in terms of $f(x) := \frac{1}{\sqrt{1-4x}}$ and differential operators, and then the final identity will just be a certain differential equation satisfied by $f$.)