10
$\begingroup$

While answering a recent question I came across the following nice-looking identity: $$ \sum_{k=1}^{n-1}\frac{\binom{k-1}{n-k-1}+\binom{k}{n-k-1}}{\binom nk}=1 $$ valid for all integer $n\ge2$.

Is there a simple algebraic proof of this identity?

$\endgroup$
  • $\begingroup$ (Yes, sorry, wrong identity.) Are the indices in the correct order on top? Looks like a lot of zero values otherwise... $\endgroup$ – abiessu May 21 at 21:08
  • 1
    $\begingroup$ @abiessu: Yes, actually series starts with $k=\lfloor n/2 \rfloor$. But I decided to use $k=1$ as start value from some beauty reasons. $\endgroup$ – user May 21 at 21:10
  • 1
    $\begingroup$ I think you mean $\lfloor n/2 \rfloor$. E.g. for $n=5$ you must start at $k=2$. $\endgroup$ – Robert Israel May 21 at 21:15
  • $\begingroup$ @RobertIsrael You are right. Was just in time to correct this. Thanks! $\endgroup$ – user May 21 at 21:16
6
$\begingroup$

The idea of this solution is due to the answer of Claude Leibovici.

Indeed the most probable reason for such simple and beautiful result is some hidden telescoping. And if one knows what one is looking for, one finds it: $$\begin{align} \frac{\binom{k-1}{n-k-1}+\binom{k}{n-k-1}}{\binom nk} &=\frac{\frac{(k-1)!}{(n-k-1)!(2k-n)!}+\frac{k!}{(n-k-1)!(2k-n+1)!}}{\frac{n!}{k!(n-k)!}}\\ &=\frac{k!(k-1)!(n-k)(3k-n+1)}{n!(2k-n+1)!}\\ &=\frac1{n!}\left[\frac{k!(k+1)!}{(2k-n+1)!}-\frac{(k-1)!k!}{(2k-n-1)!}\right]. \end{align}$$

Thus: $$ S_{nm}=\sum_{k=1}^{m-1}\frac{\binom{k-1}{n-k-1}+\binom{k}{n-k-1}}{\binom nk} =\frac1{n!}\frac{(m-1)!m!}{(2m-n-1)!}, $$ and, finally $$ S_{nn}=1, $$ as claimed.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you Markus! I should however admit that it was found by chance. I just have not come to idea to look at partial sums. $\endgroup$ – user May 23 at 13:46
  • $\begingroup$ You're welcome and I fully agree with your statement about telescoping sums. $\endgroup$ – Markus Scheuer May 23 at 14:06
5
$\begingroup$

First of all, let me precise that I am very bad with combinatorics.

Reading your post, I had the feeling that this beautiful identity holds if $n$ is an integer.

Reworking the summand in terms of the gamma function, we have

$$\frac{\binom{k-1}{n-k-1}+\binom{k}{n-k-1}}{\binom nk}=\frac{(n-k) (3 k-n+1)\, \Gamma (k) \,\Gamma (k+1)}{\Gamma (n+1)\, \Gamma (2 k-n+2)}$$ $$S_n=\sum_{k=1}^{n-1}\frac{\binom{k-1}{n-k-1}+\binom{k}{n-k-1}}{\binom nk}$$ is then given by $$S_n=\frac{n (n+1)\, \Gamma (4-n)\, \Gamma (n) \,\Gamma (n+1)-(n-2)(n-3) \,\Gamma (n+2) } {\Gamma (4-n)\, \Gamma (n+1)\, \Gamma (n+2) }$$ The numerator can be simplified as $$-(n-3) (n-2) (\pi (n-1) n \csc (\pi n)+1) \Gamma (n+2)$$ leading to $$S_n=1+\frac{\sin (\pi n)}{\pi n (n-1)}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you give more details about computation of the closed-form expression for $S_n$ in terms of $\Gamma$-functions (before final simplification)? Of course, I had in mind only integer $n$ and will now edit my question correspondingly. But your more general result is even more amazing! Thank you! $\endgroup$ – user May 22 at 7:09

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.