How to prove the following combinatorial identity?
$$\sum_{k=2}^n {k+1\choose3}{2n-2-k\choose n-2}2^k= \frac{1}{3}\cdot\frac{(2n)!}{(n-2)!n!}$$
My attempt:
The LHS is equal to the coefficient of $x^{n-2}$ in $\frac{1}{(1-x)^4\cdot(1-2x)^{n-1}}$. But this doesn't help. I don't see any other approaches right now to tackle this problem.
This is an identity I need to prove to solve another problem, which goes as follows:
Select $n$ intervals uniformly at random from the range $\left[0,1\right]$. Show that the probability that at least one interval intersects every other interval, is equal to $\frac{2}{3}$. The jump from this problem to this identity is non-trivial, but this is basically the background of the problem.
Best Answer
We seek to prove that
$$\sum_{k=2}^n {k+1\choose 3} {2n-2-k\choose n-2} 2^k = \frac{1}{3} \frac{(2n)!}{(n-2)! \times n!}.$$
The LHS is
$$4\sum_{k=0}^{n-2} {k+3\choose 3} {2n-4-k\choose n-2} 2^k = 4\sum_{k=0}^{n-2} {k+3\choose 3} {2n-4-k\choose n-2-k} 2^k.$$
Writing
$$4 \sum_{k=0}^{n-2} 2^k [w^k] \frac{1}{(1-w)^4} [w^{n-2-k}] \frac{1}{(1-w)^{n-1}} = 4 [w^{n-2}] \frac{1}{(1-2w)^4} \frac{1}{(1-w)^{n-1}}$$
we find
$$4 \;\underset{w}{\mathrm{res}} \; \frac{1}{w^{n-1}} \frac{1}{(1-w)^{n-1}} \frac{1}{(1-2w)^4}.$$
Next we put $w=(1-\sqrt{1-4v})/2$ so that $w(1-w)=v$ and $dw = 1/\sqrt{1-4v} \; dv$ to get
$$4 \;\underset{v}{\mathrm{res}} \; \frac{1}{v^{n-1}} \frac{1}{\sqrt{1-4v}^4} \frac{1}{\sqrt{1-4v}} = 4 \;\underset{v}{\mathrm{res}} \; \frac{1}{v^{n-1}} \frac{1}{(1-4v)^{5/2}}.$$
Extracting the coefficient we find
$$4 [v^{n-2}] (1-4v)^{-5/2} = 4^{n-1} (-1)^n {-5/2\choose n-2} \\ = 4^{n-1} (-1)^n \frac{n(n-1)}{(-1/2)\times(-3/2)} {-1/2\choose n} \\ = 4^n (-1)^n \frac{1}{3} n(n-1) [z^n] \frac{1}{\sqrt{1+z}} = \frac{1}{3} n(n-1) [z^n] \frac{1}{\sqrt{1-4z}} \\ = \frac{1}{3} n(n-1) {2n\choose n} = \frac{1}{3} \frac{(2n)!}{(n-2)! \times n!}.$$
This is the claim.