# A nice combinatorial identity: $\sum_{k=1}^{n-1}\frac{\binom{k-1}{n-k-1}+\binom{k}{n-k-1}}{\binom nk}=1$

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?

• (Yes, sorry, wrong identity.) Are the indices in the correct order on top? Looks like a lot of zero values otherwise... May 21, 2020 at 21:08
• @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.
– user
May 21, 2020 at 21:10
• I think you mean $\lfloor n/2 \rfloor$. E.g. for $n=5$ you must start at $k=2$. May 21, 2020 at 21:15
• @RobertIsrael You are right. Was just in time to correct this. Thanks!
– user
May 21, 2020 at 21:16

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.

• 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.
– user
May 23, 2020 at 13:46
• You're welcome and I fully agree with your statement about telescoping sums. May 23, 2020 at 14:06

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)}$$

• 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!
– user
May 22, 2020 at 7:09

Write this as $$\sum_{k=1}^{n-1}\frac{\binom{k}{n-k-1}\left(\frac{2k+n-1}{k}+1\right)}{\binom{n}k}=\frac{\binom{k}{n-k-1}(3k+n-1)}{\binom{n}kk}$$ Now this is written as a hypergeometric series. There are several ways to do this, but I have carefully chosen the way so that no division by zero occurs in the range $$1\le k\le n-1$$.

We can now use Zeilberger's algorithm to find a recurrence this sum satisfies. Doing so, we find that when \begin{align} F(n,k)&=\frac{\binom{k}{n-k-1}(3k+n-1)}{\binom{n}kk}, \\ R(n,k)&=\frac{(2k+1-n)(2k-n)}{(n-k)(3k+1-n)}, \\ G(n,k) &= F(n,k)R(n,k), \end{align} we have $$F(n,k)=G(n,k+1)-G(n,k)$$ This is actually better than what Zeilberger's usually gives us. We have found an anti-difference for $$F(n,k)$$, allowing us to compute $$\sum_{k=a}^bF(n,k)$$. In particular, $$\sum_{k=1}^{n-1}F(n,k)=G(n,n)-G(n,1)$$ It is not hard to see that $$G(n,1)=0$$, either because of the factors $$(2k+1-n)(2k-n)$$ when $$n\in\{2,3\}$$, or because of the $$\binom{k}{n-k-1}$$ factor when $$n\ge 4$$. However, $$G(n,n)$$ is an indeterminate form $$0/0$$. Let us look carefully at $$G(n,k)$$: $$G(n,k)=\frac{\binom{k}{n-k-1}(3k+n-1)}{\binom{n}kk}\cdot \frac{(2k+1-n)(2k-n)}{(n-k)(3k+1-n)}\\=\frac{\color{red}{\binom{k}{n-k-1}}(2k+1-n)(2k-n)}{\color{red}{(n-k)}\binom{n}kk}$$ The problem factors are in red. However, we can rewrite $$\binom{k}{n-k-1}\frac{1}{n-k}=\binom{k+1}{n-k}\frac1{k+1}$$, and the problem disappears. Doing so, we find $$G(n,n)=1$$, and we are done.

Note that you can avoid all of these division by zero considerations if you write everything in terms of Gamma functions, and take limits if the singularities of $$\Gamma$$ get involved.