Prove that :$$\sum_{k=0}^{58}C_{2017+k}^{58-k}C_{2075-k}^{k}=\sum_{p=0}^{29}C_{4091-2p}^{58-2p}$$
Problem
Source: China TST 4 Problem 1
Tags: TST, combinatorics, equation, China, generating functions
22.03.2017 19:13
perfect equality any ideas
23.03.2017 01:38
HuangZhen wrote: Prove that :$$\sum_{k=0}^{58}C_{2017+k}^{58-k}C_{2075-k}^{k}=\sum_{p=0}^{29}C_{4091-2p}^{58-2p}$$
02.03.2018 17:14
Here's the solution to the generalized identity mentioned above by Tintarn: Tintarn wrote: $$\sum_{k=0}^n \binom{a+k}{n-k} \binom{b-k}{k}=\sum_{k\geqslant 0} \binom{a+b-2k-1}{n-2k}$$ For $(a,b,n)\in \mathbb{Z}_+^3$, let $P(a,b,n)= \sum_{k=0}^{n}{\binom{a+k}{n-k} \binom{b-k}{k}}$ and let $Q(a,b,n)$ denote the statement $$P(a,b,n)=\sum_{k\geqslant 0}{\binom{a+b-2k-1}{n-2k}}.$$Let $\mathcal{S}$ denote the set of string of positive integers $x_{n+1}x_n\cdots x_1$ that $x_1,x_2,\dotsc ,x_{n+1}\in \{ 1,2,\dotsc ,a+b+1\}$ and $x_{n+1}<x_n<\cdots <x_1$. Not hard to see that $P(a,b,n)$ count the number of pairing $$(i+1,S)$$where $i\in \{ 0,1,2,\dotsc ,n\}$ and $S=x_{n+1}x_n\cdots x_1\in \mathcal{S}$ satisfy $x_{i+1}=a+i+1$. Note that for any string $S\in \mathcal{S}$, there exists at most one $i\in \{ 0,1,2,\dotsc ,n\}$ that $x_{i+1}=a+i+1$. Hence, $P(a,b,n)=|\mathcal{S}|-|\mathcal{K}|$ where $\mathcal{K}$ is the set of string $S\in \mathcal{S}$ that there's no such $i$. For convenient, always denote $x_{n+2}=0$ and $x_0=a+b+1$. For each string $x_{n+1}x_n\cdots x_1\in \mathcal{K}$, there exists exactly one $j$ that $a+b+1\geqslant x_j>a+j$ and $x_{j+1}<a+j+1$. For each $j$, the number of string $x_{n+1}x_n\cdots x_1\in \mathcal{K}$ that $a+b+1\geqslant x_j>a+j$ and $x_{j+1}<a+j+1$ is equal to $$\binom{b-j+1}{j}\binom{a+j}{n+1-j}.$$So, $$P(a,b,n)=|\mathcal{S}|-|\mathcal{K}| =\binom{a+b+1}{n+1}-\sum_{j=0}^{n+1}{\binom{b-j+1}{j}\binom{a+j}{n+1-j} }=\binom{a+b+1}{n+1}-P(a,b+1,n+1).$$Now, for any $(a,b,n)\in \mathbb{Z}_+^3$ that $Q(a,b,n)$ is true, we get that \begin{align*} P(a,b+1,n+1) &=\binom{a+b+1}{n+1}-P(a,b,n) \\ &=\binom{a+b+1}{a+b-n}-\sum_{k\geqslant 0}{\binom{a+b-2k-1}{a+b-n-1}} \\ & =\sum_{k\geqslant 0}{\binom{a+b+1-k}{a+b-n-1}} -\sum_{k\geqslant 0}{\binom{a+b-2k-1}{a+b-n-1}} \\ & =\sum_{k\geqslant 0}{\binom{a+b-2k}{a+b-n-1}} \\ & =\sum_{k\geqslant 0}{\binom{a+(b+1)-2k-1}{(n+1)-2k}}. \end{align*}In other words, $Q(a,b+1,n+1)$ is true. So, we conclude that $Q(a,b,n)$ implies $Q(a,b+1,n+1)$ for all $a,b,n\in \mathbb{Z}_+^3$. Hence, we only need to prove that $Q(a,b,n)$ is true when $b=1$ or $n=1$. Both cases are easy, done.
19.05.2024 10:24
Can we use generating function to calculate the value of the coefficient.