Prove $\sum_{k=0}^{58}\binom{2017+k}{58-k}\binom{2075-k}{k}=\sum_{k=0}^{29}\binom{4091-2k}{58-2k}$
Show that :
$$\sum_{k=0}^{58}\binom{2017+k}{58-k}\binom{2075-k}{k}=\sum_{k=0}^{29}\binom{4091-2k}{58-2k}$$
It seems interesting, but how to prove?
Solution 1:
We are interested in verifying that
$$\sum_{k=0}^{2n} {m+k\choose 2n-k} {m+2n-k\choose k} = \sum_{k=0}^n {2m+2n-1-2k\choose 2n-2k}.$$
Starting with the RHS we introduce
$${2m+2n-1-2k\choose 2n-2k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n-2k+1}} (1+z)^{2m+2n-1-2k} \; dz.$$
Note that this vanishes when $k\gt n$ so we may extend $k$ to infinity and obtain
$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n+1}} (1+z)^{2m+2n-1} \sum_{k\ge 0} \frac{z^{2k}}{(1+z)^{2k}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n+1}} (1+z)^{2m+2n-1} \frac{1}{1-z^2/(1+z)^2} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n+1}} (1+z)^{2m+2n+1} \frac{1}{1+2z} \; dz.$$
For the LHS we introduce
$${m+2n-k\choose k} = {m+2n-k\choose m+2n-2k} \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+2n-2k+1}} (1+z)^{m+2n-k} \; dz$$
as well as
$${m+k\choose 2n-k} = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n-k+1}} (1+w)^{m+k} \; dw.$$
This last one vanishes when $k\gt 2n$ so it controls the range and we may extend $k$ to infinity and obtain
$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n+1}} (1+w)^{m} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+2n+1}} (1+z)^{m+2n} \sum_{k\ge 0} \frac{z^{2k} w^k (1+w)^k}{(1+z)^k} \; dz \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n+1}} (1+w)^{m} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+2n+1}} (1+z)^{m+2n} \frac{1}{1-z^2 w(1+w)/(1+z)} \; dz \; dw \\ = -\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n+1}} (1+w)^{m} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+2n+1}} (1+z)^{m+2n+1} \frac{1}{(z(1+w)+1)(wz-1)} \; dz \; dw.$$
We will evaluate the inner integral using the fact that residues at the poles sum to zero. Fortunately the residue at infinity is zero, which can be seen by inspection, or more formally through
$$\mathrm{Res}_{z=\infty} \frac{1}{z^{m+2n+1}} (1+z)^{m+2n+1} \frac{1}{(z(1+w)+1)(wz-1)} \\ = - \mathrm{Res}_{z=0} \frac{1}{z^2} z^{m+2n+1} (1+1/z)^{m+2n+1} \frac{1}{((1+w)/z+1)(w/z-1)} \\ = - \mathrm{Res}_{z=0} (z+1)^{m+2n+1} \frac{1}{((1+w)+z)(w-z)} = 0.$$
To facilitate extraction of residues we write the integral as
$$-\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n+2}} (1+w)^{m-1} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+2n+1}} (1+z)^{m+2n+1} \frac{1}{(z+1/(1+w))(z-1/w)} \; dz \; dw.$$
Flipping the sign we get from the residue at $-1/(1+w)$
$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n+2}} (1+w)^{m-1} \\ \times (-1)^{m+2n+1} (1+w)^{m+2n+1} \frac{w^{m+2n+1}}{(1+w)^{m+2n+1}} \frac{1}{-1/(w+1)-1/w} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n+2}} (1+w)^{m-1} \\ \times (-1)^{m+2n+1} w^{m+2n+1} \frac{w(w+1)}{-w-(1+w)} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} (1+w)^{m} (-1)^{m+2n} w^{m} \frac{1}{1+2w} \; dw = 0.$$
Once more flipping the sign we get from the residue at $z=1/w$
$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n+2}} (1+w)^{m-1} \\ \times w^{m+2n+1} \frac{(1+w)^{m+2n+1}}{w^{m+2n+1}} \frac{1}{1/w+1/(1+w)} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n+2}} (1+w)^{2m+2n} \frac{w(1+w)}{1+w+w} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n+1}} (1+w)^{2m+2n+1} \frac{1}{1+2w} \; dw.$$
We have obtained exactly the same integral as for the RHS and this concludes the argument. If a closed form for easy computation is desired then it would be
$$\sum_{q=0}^{2n} {2m+2n+1\choose q} (-1)^{2n-q} 2^{2n-q}$$
or at last
$$\bbox[5px,border:2px solid #00A000]{ 2^{2n} \sum_{q=0}^{2n} {2m+2n+1\choose q} \frac{(-1)^q}{2^q}.}$$
Remark. Considering the origins of this problem as listed in the comments we suspect that an elementary proof or at any rate one using formal power series is certain to appear in addition to the Egorychev method which is what I have above.
Solution 2:
Note: This is a merely a variation of @MarkoRiedel's nice answer which was a pleasure to analyse. It's based upon the same technique, but uses another notation which might also be convenient. In order to ease comparison I use the same variables.
We use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series. This way we can write e.g. \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}
The following generalisation of OPs identity is valid for $m,n\geq 0$ \begin{align*} \sum_{k=0}^{2n} {m+k\choose 2n-k} {m+2n-k\choose k} = \sum_{k=0}^n {2m+2n-1-2k\choose 2n-2k}\tag{1} \end{align*}
$$ $$
We start with the RHS of (1) and obtain \begin{align*} \sum_{k=0}^n {2m+2n-1-2k\choose 2n-2k}&=\sum_{k=0}^\infty[z^{2n-2k}](1+z)^{2m+2n-1-2k}\tag{2}\\ &=[z^{2n}](1+z)^{2m+2n-1}\sum_{k=0}^\infty\left( \frac{z}{1+z}\right)^{2k}\tag{3}\\ &=[z^{2n}](1+z)^{2m+2n-1}\cdot\frac{1}{1- \frac{z^2}{(1+z)^2}}\tag{4}\\ &=[z^{2n}]\frac{(1+z)^{2m+2n+1}}{1-2z}\tag{5} \end{align*}
Comment:
In (2) we apply the coefficient of operator once and change the upper limit of the sum to $\infty$ without changing anything since we adding zeros only.
In (3) we use the linearity of the coefficient of operator and apply the rule $[z^{p-q}]A(z)]=[z^p]z^qA(z)$.
In (4) we use the geometric series expansion formula.
In (5) we do some simplifications and represent the RHS as coefficient of $z^{2n}$ of a rational function.
The goal is to transform the LHS of (1) also to (5) and show this way equality.
We obtain \begin{align*} \sum_{k=0}^{2n}&\binom{m+k}{2n-k}\binom{m+2n-k}{k}\\ &=\sum_{k=0}^{2n}\binom{m+k}{2n-k}\binom{m+2n-k}{m+2n-2k}\tag{6}\\ &=\sum_{k=0}^\infty[w^{2n-k}](1+w)^{m+k}[z^{m+2n-2k}](1+z)^{m+2n-k}\\ &=[w^{2n}](1+w)^{m}[z^{m+2n}](1+z)^{m+2n}\sum_{k=0}^\infty\left(\frac{z^2w(1+w)}{1+z}\right)^k\\ &=[w^{2n}](1+w)^{m}[z^{m+2n}](1+z)^{m+2n}\cdot\frac{1}{1-\frac{z^2w(1+w)}{1+z}}\tag{7}\\ &=-[w^{2n}](1+w)^{m}[z^{m+2n}](1+z)^{m+2n}\cdot\frac{\frac{1+z}{w(1+w)}}{\left(z-\frac{1}{w}\right)\left(z+\frac{1}{1+w}\right)}\tag{8}\\ &=-[w^{2n+1}](1+w)^{m-1}[z^{-1}]\underbrace{\frac{z^{-m-2n-1}(1+z)^{m+2n+1}}{\left(z-\frac{1}{w}\right)\left(z+\frac{1}{1+w}\right)}}_{f(z)}\tag{9}\\ &=-[w^{2n+1}](1+w)^{m-1} \left(-\operatorname{res}_{z=\infty}f(z)-\operatorname{res}_{z=\frac{1}{w}}f(z)-\operatorname{res}_{z=-\frac{1}{1+w}}f(z)\right)\tag{10}\\ &=[w^{2n+1}](1+w)^{m-1}\\ &\qquad\cdot\left([z^{-1}]\left(-\frac{1}{z^2}\cdot \frac{\left(\frac{1}{z}\right)^{-m-2n-1}\left(1+\frac{1}{z}\right)^{m+2n+1}} {\left(\frac{1}{z}-\frac{1}{w}\right)\left(\frac{1}{z}+\frac{1}{1+w}\right)}\right)\right.\\ &\qquad\qquad+\frac{\left(\frac{1}{w}\right)^{-m-2n-1}\left(1+\frac{1}{w}\right)^{m+2n+1}}{\frac{1}{w}+\frac{1}{1+w}}\\ &\qquad\qquad\left.+\frac{\left(-\frac{1}{1+w}\right)^{-m-2n-1}\left(1-\frac{1}{1+w}\right)^{m+2n+1}}{-\frac{1}{1+w}-\frac{1}{w}}\right)\tag{11}\\ &=[w^{2n+1}](1+w)^{m-1}\left([z^{-1}]\left(-\frac{(1+z)^{m+2n+1}}{\left(\frac{1}{z}-\frac{1}{w}\right)\left(\frac{1}{z}+\frac{1}{1+w}\right)}\right)\right.\\ &\qquad\qquad\qquad+\frac{w(1+w)^{m+2n+2}}{1+2w}+(-1)^m\frac{w^{m+2n+2}(1+w)}{1+2w}\Bigg)\tag{12}\\ &=[w^{2n}]\frac{(1+w)^{2m+2n+1}}{1+2w}\tag{13} \end{align*} and the claim follows.
Comment:
In (6) we use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.
In (7) and the lines before we do the same steps as we already did for the RHS.
In (8) we observe that we have a rational function in $z$ with simple poles at $z=\frac{1}{w}$ and $z=-\frac{1}{1+w}$.
In (9) we write the $z$-part of the expression as residue of a function $f(z)$.
In (10) we use the fact that computing the residue of $f$ at zero is minus the sum of the residuals of $f$ at the poles and infinity.
In (11) we use for the residue at infinity the formula \begin{align*} \operatorname{res}_{z=\infty}f(z)=\operatorname{res}_{z=0}\left(-\frac{1}{z^2}f\left(\frac{1}{z}\right)\right) =[z^{-1}]\left(-\frac{1}{z^2}f\left(\frac{1}{z}\right)\right) \end{align*} and for a simple pole $ a\in\mathbb{C}$ we use \begin{align*} \operatorname{res}_{z=a}f(z)=\lim_{z\to a}(z-a)f(z) \end{align*}
In (12) we see the three residuals after some simplifications and observe that only the residue at $z=\frac{1}{w}$ has a contribution not equal to zero.
In (13) we finally have the same situation as in (5).
Note: Don Knuth et al. tell us in section 5.5 of Concrete Mathematics: Binomial coefficients are like chameleons, changing their appearance easily.
In agreement with this statement we rewrite identity (1) putting emphasis on symmetry. The following is valid for $m,n\geq 0$ \begin{align*} \sum_{k=-n}^n\binom{n+m+k}{n-k}\binom{n+m-k}{n+k}=\sum_{k=0}^n\binom{-2m}{2n-2k} \end{align*}
Here we shift the index $k$ of the LHS of (1) by $n$ to start from $-n$. On the other side we use the binomial identity $ \binom{-p}{q}=\binom{p+q-1}{q}(-1)^q $.
Maybe someone could derive some other insight from this more symmetrical representation.
Solution 3:
Imagine having $N+2m$ boxes in a row. We need to pick $N$ boxes to be special, but in such a way that we can choose an $s$ such that of the first $m+s$ boxes, there are exactly $N-s$ boxes special.
This is quite a strange property, so let's see where this can go wrong. What are ways to pick the boxes that do not satisfy the property? Let's just loop through $s$ to see what's going on. We start with $s=0$. The property now says that of the first $m$ boxes, $N$ need to be special. Let's assume this is not true; there are less than $N$ boxes special in the first $m$ boxes. Then we increase $s$ by one; now there need to be $N-1$ boxes special in the first $m+1$ boxes. If there are more boxes special, then this means there were $N-1$ boxes of the first $m$ special, and the $m+1$'th box was special. We know now that there are no other $s$'s for which this can go right, since of the first $m+s$ boxes, there will be $N$ special (not $N-s$, as we should have).
if there are less than $N-s$ boxes special of the first $m+s$ boxes, but more than $N-s-1$ out of the first $m+s+1$, then of the first $m+s$ boxes there are exactly $N-s-1$ special ones, furthermore, the $m+s+1$'st box is special. This results in an invalid way to pick our boxes (note that this only makes sense when $0\leq s<N$).
So the number of ways we can pick boxes in an invalid way, is
$$\sum_{k=0}^{N-1}{m+k\choose N-k-1}{m+N-k-1\choose k}$$
since we pick the $m+k+1$'th box to be special, and then pick $N-k-1$ boxes before that, and $k$ boxes after that.
The number of ways to pick boxes in a valid way, is of course
$$\sum_{k=0}^{N}{m+k\choose N-k}{m+N-k\choose k}$$
Notice that the number of ways to pick boxes in an invalid way, is the same as picking $N-1$ boxes out of $2m+N-1$, but in such a way that we can choose an $s$ such that of the first $m+s$, there are exactly $N-1-s$ boxes special. Can you hear induction screaming to be used?
Let's write $S_{2m}(N)$ to mean the number of ways that we can choose $N$ boxes out of $2m+N$, but in such a way that we can choose an $s$ (between $0$ and $N$) such that of the first $m+s$, there are exactly $N-s$ boxes special. Then, as noted above, we know that the number of ways to not do this, is $S_{2m}(N-1)$. Thus,
$${2m+N\choose N}=S_{2m}(N)+S_{2m}(N-1)$$
We will now use induction to prove
$$S_{2m}(N)=\sum_{k=0}^N(-1)^{N-k}{2m+k\choose k}$$
We know that $S_{2m}(0)=1$, and so $S_{2m}(0)={m+0\choose 0}$ is indeed true. Now, assume the expression is true for $N$. Then: \begin{align} S_{2m}(N+1)&={2m+N+1\choose N+1}-S_{2m}(N)\\ &={2m+N+1\choose N+1}-\sum_{k=0}^N(-1)^{N-k}{2m+k\choose k}\\ &=(-1)^{N+1-(N+1)}{2m+N+1\choose N+1}+\sum_{k=0}^N(-1)^{N+1-k}{2m+k\choose k}\\ &=\sum_{k=0}^{N+1}(-1)^{N+1-k}{2m+k\choose k}\\ \end{align} and so we can conclude that the expression must be true for all $N\geq0$.
So far, we've proven that
$$\sum_{k=0}^{N}{m+k\choose N-k}{m+N-k\choose k}=\sum_{k=0}^N(-1)^{N-k}{2m+k\choose k}$$
Let's now set $2n$, so that we get
$$\sum_{k=0}^{2n}{m+k\choose 2n-k}{m+2n-k\choose k}=\sum_{k=0}^{2n}(-1)^k{2m+k\choose k}$$
And now we just mess around a little bit with the right-hand side (I use ${a\choose-1}=0$ here):
\begin{align} \sum_{k=0}^{2n}(-1)^k{2m+k\choose k}&=\\ \sum_{k=0}^{n}{2m+2k\choose 2k}-\sum_{k=1}^{n}{2m+2k-1\choose 2k-1}&=\\ \sum_{k=0}^{n}\left({2m+2k-1\choose 2k}+{2m+2k-1\choose 2k-1}\right)-\sum_{k=0}^{n}{2m+2k-1\choose 2k-1}&=\\ \sum_{k=0}^{n}{2m+2k-1\choose 2k}&=\\ \sum_{k=0}^{n}{2m+2(n-k)-1\choose 2(n-k)}&=\\ \sum_{k=0}^{n}{2m+2n-2k-1\choose 2n-2k} \end{align}
so finally, we can conclude
$$\sum_{k=0}^{2n}{m+k\choose 2n-k}{m+2n-k\choose k}=\sum_{k=0}^{n}{2m+2n-2k-1\choose 2n-2k}$$
(and the requested result is obtained by setting $n=29$ and $m=2017$).