Combinatorial identity for "half of Vandermonde identity"

62 Views Asked by At

It is known that $$\sum_{i=0}^{n}{{x\choose i}{y\choose n-i}}={x+y\choose n}$$

However, I am curious as to whether or not we can derive any identity/lower bound for the following

$$\sum_{i=0}^{n/2}{{x\choose i}{y\choose n-i}}$$

I feel that no clean identity exists in general, however at least when $x=y$ and $n=2k$, we have

$$\color{blue}{{x\choose 0}{x\choose 2k}}+\color{green}{{x\choose 1}{x\choose 2k-1}}+...+\color{red}{{x\choose k}{x\choose k}}+...+\color{green}{{x\choose 2k-1}{x\choose 1}}+\color{blue}{{x\choose 2k}{x\choose 0}}$$

where colored terms are equal. Then we have

$$A=\sum_{i=0}^{k}{{x\choose i}{x\choose 2k-i}}=\sum_{i=k}^{2k}{{x\choose i}{x\choose 2k-i}}$$

and so we have

$$2A=\sum_{i=0}^{k}{{x\choose i}{x\choose 2k-i}}+\sum_{i=k}^{2k}{{x\choose i}{x\choose 2k-i}}=\color{red}{{x\choose k}{x\choose k}}+{2x\choose 2k}$$

However when $x\not=y$ it is not so nice since it appears we no longer have this symmetry. Therefore, I am interested in a lower bound for this identity.

1

There are 1 best solutions below

0
On BEST ANSWER

If you enjoy hypergeometric functions (this is given by a CAS) $$S(n,x,y)=\sum_{i=0}^{\frac n2}{{x\choose i}{y\choose n-i}}=\binom{y}{n} \, _2F_1(-n,-x;-n+y+1;1)-$$ $$\binom{x}{\frac{n+2}{2}} \binom{y}{\frac{n-2}{2}} \, _3F_2\left(1,\frac{2-n}{2},\frac{n+2-2x}{2};\frac{n+4}{2},\frac{4-n+2y}{2};1 \right)$$ $$S(2k,x,y)=\binom{y}{2 k} \, _2F_1(-2 k,-x;-2 k+y+1;1)-$$ $$\binom{x}{k+1} \binom{y}{k-1} \, _3F_2(1,1-k,k-x+1;k+2,-k+y+2;1)$$

which reduces to your (nice) last formula when $y=x$.

I did not find other simplication.