3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Why the downvotes? $\endgroup$ Feb 21 at 16:49
  • 1
    $\begingroup$ People want you to show what you have tried and where you got stuck. $\endgroup$ Feb 21 at 16:53
  • 1
    $\begingroup$ I think people want to see you do more work. Clearly its a non trivial question but for consistency's sake its best to show work. I too get down votes if i ask an interesting question but fail to show work (alternatively it might be because we are both named Sid(d)harth) $\endgroup$ Feb 21 at 16:55
  • 1
    $\begingroup$ For all we know, you received this on a homework problem, copied it, and posted it to MSE without attempting it at all. MSE users do not like answering such questions. The burden is on you to prove otherwise (either that you indeed have put some effort in, or that this arose in some applied context). $\endgroup$ Feb 21 at 16:57
  • 1
    $\begingroup$ Dividing by 4 yields oeis.org/A002802, so you might find something useful there. $\endgroup$
    – RobPratt
    Feb 21 at 17:25

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks. Could you please clarify what does Res stand for? I've never come across this technique before $\endgroup$ Feb 22 at 17:20
  • 1
    $\begingroup$ This is the residue operator from the Egorychev text Combinatorial Sums. $\endgroup$ Feb 22 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.