# In Pursuit of a Broader Understanding of Complicated Binomial Coefficient Sums

$$\sum_{k=0}^{n}\binom{n}{k}\frac{k!}{(n+k+1)!}$$

The above identity was posted once before by me, however, all results were obtained numerically exploring the identity rather than understanding it combinatorially or performing explicit manipulations on it algebraically. I was hoping by posting again I might be able to entice someone a bit more capable than myself to consider again whether there might be a good combinatorial interpretation for this after all, and whether there are some general guidelines for both arriving at these interpretations, and choosing the proper algebraic manipulations where necessary to see them.

-
Are you familiar with Wilf-Zeilberger (WZ) theory (expounded in their book with Petkovsek, A=B)? –  Zev Chonoles Apr 24 '13 at 0:50
I am not unfortunately, so for purposes here it will not be immediately eye-opening. I will certainly explore it further though. –  user73041 Apr 24 '13 at 0:53
It does not seem likely to have a combinatorial interpretation, since the terms are typically non-integral. –  vadim123 Apr 24 '13 at 0:58
This is good to know as well. I am not well-read enough yet to know when a sum like this will be able to be interpreted at all. –  user73041 Apr 24 '13 at 1:01
@vadim123, it might be possible to "complete" to integers and thus get a combinatorial interpretation. But the simplest way is a factor $(2 n + 1)!$, and I don't see anything useful comming out of it. –  vonbrand Apr 25 '13 at 12:19

Let

$$f(n)=\sum_{k=0}^{n}\binom{n}{k}\frac{k!}{(n+k+1)!}\;.$$

Then

\begin{align*} \frac{(2n+1)!}{n!}f(n)&=\frac{(2n+1)!}{n!}\sum_{k=0}^n\frac{n!\,k!}{k!(n-k)!(n+k+1)!}\\\\ &=\sum_{k=0}^n\frac{(2n+1)!}{(n-k)!(n+k+1)!}\\\\ &=\sum_{k=0}^n\binom{2n+1}{n-k}\\\\ &=\sum_{k=0}^n\binom{2n+1}k\\\\ &=\frac12\sum_{k=0}^{2n+1}\binom{2n+1}k\\\\ &=2^{2n}\;, \end{align*}

so

$$f(n)=\frac{4^nn!}{(2n+1)!}=\frac{2^n}{(2n+1)!!}\;.$$

-