How to evaluate this tricky combinatorial sum?

Question

According to Mathematica,

$$\sum _{i=s}^p (-1)^i \binom{p}{i} \binom{i}{i-s}\frac{1}{2 i+1} =(-1)^s \frac{p!\,\Gamma \left(s+\frac{1}{2}\right)}{2 s! \,\Gamma \left(p+\frac{3}{2}\right)}.$$

How can we prove this? I'd especially like a solution method that can be generalized to other sums of this type.

The assumptions are that $s,p\in\mathbb N$ with $0≤s≤p.$

Answer 1

We'll make use of $$\frac 1 {n + 1} = \int_0^1 x^{n}dx$$ and the well-known relationship between the Beta function with the Gamma function: $$B(x,y)=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}$$

$$\begin{split} \sum _{i=s}^p(-1)^i\binom{p}{i}\binom{i}{i-s}\frac{1}{2i+1} &= {p \choose s}\sum_{i=s}^p {p-s \choose i-s}\frac {(-1)^i} {2i+1}\\ &=(-1)^s{p \choose s}\sum_{i=0}^{p-s} {p-s \choose i}\frac {(-1)^i} {2(i+s)+1}\\ &=(-1)^s{p \choose s}\sum_{i=0}^{p-s} {p-s \choose i}(-1)^i\int_0^1x^{2(i+s)}dx\\ &=(-1)^s{p \choose s}\int_0^1x^{2s}(1-x^2)^{p-s}dx\\ &=(-1)^s\frac 1 2 {p \choose s}\int_0^1 u^{s-\frac 1 2}(1-u)^{p-s}du\\ &=(-1)^s \frac 1 2 {p \choose s} B\left(s+\frac 1 2, p-s+1\right)\\ &= (-1)^s\frac 1 2 {p \choose s} \frac{\Gamma\left(s+\frac 1 2\right)\Gamma\left(p-s+1\right)}{\Gamma\left(p+\frac 3 2\right)}\\ &=(-1)^s \frac {p!}{2\cdot s!} \frac {\Gamma\left(s+\frac 1 2\right)}{\Gamma\left(p+\frac 3 2\right)} \end{split}$$

Answer 2

Recall that $\binom{a}{b}\binom{b}{c}=\binom{a}{c}\binom{a-c}{b-c},$ so $$\sum _{i=s}^p(-1)^i\binom{p}{i}\binom{i}{i-s}\frac{1}{2i+1}=\binom{p}{s}\sum _{i=s}^p(-1)^i\binom{p-s}{i-s}\frac{1}{2i+1}$$ $$=(-1)^s\binom{p}{s}\sum _{i=0}^{p-s}(-1)^i\binom{p-s}{i}\frac{1}{2(i+s)+1}=\frac{(-1)^s}{2s+1}\binom{p}{s}\sum _{i=0}^{p-s}(-1)^i\binom{p-s}{i}\frac{1}{\frac{2i}{2s+1}+1}$$ Using geometric sum and assuming $p<2s+1/2$(Thanks to the OP who pointed this out) $$\frac{(-1)^s}{2s+1}\binom{p}{s}\sum _{k=0}^{\infty}(\frac{-2}{2s+1})^k\sum _{i=0}^{p-s}(-1)^i\binom{p-s}{i}i^k=\frac{(-1)^s}{2s+1}\binom{p}{s}\sum _{k=0}^{\infty}(\frac{-2}{2s+1})^k(p-s)!{k\brace p-s}$$ where the last step is one of the forms of Stirling numbers of second kind $$\frac{(-1)^s(p-s)!}{2s+1}\binom{p}{s}\sum _{k=0}^{\infty}(\frac{-2}{2s+1})^k{k\brace p-s}$$ Now, recall that $\displaystyle \sum _{n=0}^{\infty}{n\brace k}x^n=\frac{1}{(k+1)!x\binom{1/x}{k+1}}$ is the generating function for Stirling numbers, so

$$=\frac{(-1)^s(p-s)!}{2s+1}\binom{p}{s}\frac{1}{(p-s+1)!(-2/(2s+1))\binom{\frac{-1}{2}(2s+1)}{p-s+1}},$$ which if I am not mistaken, should be that expression using that $\binom{n}{k}=(-1)^k\binom{-n+k-1}{k}$ for $n<0.$

Answer 3

Use the key formula $$ \sum_{k=0}^p (-1)^k \binom{p}{k} \binom{k}{s} x^k = \binom{p}{s}(-x)^s (1-x)^{p-s} $$ Multiply both sides by $\sqrt{x}$ and integrate from 0 to 1. Use the Beta integral to get an answer in a ratio of gamma functions. Keep p as as a non-integer (the sum upper limit then runs to infinity) so that you don't get contradictory factors like $1/\sin{\pi(p-s)}$ in your answer. Gamma function ID's will ultimately lead to the answer you seek.