Combinatorial proofs of the following identities
Solution 1:
Suppose we seek to show that
$${2m\choose 2n} = \sum_{k=0}^n {2n+1\choose 2k+1} {m+k\choose 2n}.$$
where $m\ge n.$ We introduce
$${2n+1\choose 2k+1} = {2n+1\choose 2n-2k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n-2k+1}} (1+z)^{2n+1} \; dz.$$
Observe that this vanishes when $k\gt n$ so that we may use it to control the range and extend $k$ to infinity. We also use
$${m+k\choose 2n} = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n+1}} (1+w)^{m+k} \; dw.$$
We thus obtain
$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{2n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{m}}{w^{2n+1}} \sum_{k\ge 0} z^{2k} (1+w)^k \; dw\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1} }{z^{2n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{m}}{w^{2n+1}} \frac{1}{1-(1+w)z^2} \; dw\; dz.$$
Evalute the inner integral using the negative of the residue at the pole at $$w=\frac{1-z^2}{z^2}$$ (residues sum to zero) as in
$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1} }{z^{2n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{m}}{w^{2n+1}} \frac{1}{1-z^2 - wz^2} \; dw\; dz \\ = - \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1} }{z^{2n+3}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{m}}{w^{2n+1}} \frac{1}{w-(1-z^2)/z^2} \; dw\; dz.$$
The negative of the residue is
$$\frac{1}{z^{2m}} \frac{z^{4n+2}}{(1-z^2)^{2n+1}} = \frac{1}{z^{2m-4n-2}} \frac{1}{(1-z^2)^{2n+1}}$$
and we obtain from the outer integral
$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1} }{z^{2n+3}} \frac{1}{z^{2m-4n-2}} \frac{1}{(1-z^2)^{2n+1}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2m-2n+1}} \frac{1}{(1-z)^{2n+1}} \; dz \\ = {2m-2n+2n\choose 2n} = {2m\choose 2n}.$$
This is the claim.
Remark. We also need to show that the contribution from the residue at infinity of the inner integral is zero. We get
$$\mathrm{Res}_{w=\infty} \frac{(1+w)^{m}}{w^{2n+1}} \frac{1}{1-(1+w)z^2} \\ = - \mathrm{Res}_{w=0} \frac{1}{w^2} (1+1/w)^{m} w^{2n+1} \frac{1}{1-z^2-z^2/w} \\ = - \mathrm{Res}_{w=0} (1+w)^{m} w^{2n-m} \frac{1}{w(1-z^2)-z^2}.$$
No contribution when $2n\ge m.$ Otherwise,
$$\frac{1}{z^2} \mathrm{Res}_{w=0} (1+w)^{m} \frac{1}{w^{m-2n}} \frac{1}{1-w(1-z^2)/z^2} \\ = \frac{1}{z^2} \sum_{q=0}^{m-2n-1} {m\choose m-2n-1-q} \frac{(1-z^2)^q}{z^{2q}} \\ = \frac{1}{z^2} \sum_{q=0}^{m-2n-1} {m\choose 2n+1+q} \left(\frac{1}{z^2}-1\right)^q$$
Combining this with the integral in $z$ yields
$$\sum_{q=0}^{m-2n-1} {m\choose 2n+1+q} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1} }{z^{2n+1}} \frac{1}{z^2} \sum_{p=0}^q {q\choose p} (-1)^{q-p} \frac{1}{z^{2p}} \; dz.$$
The contribution from the residue is
$$[z^{2n+2+2p}] (1+z)^{2n+1} = 0.$$
We can express this verbally by saying that the term from the integral is $[z^{2n}] (1+z)^{2n+1} = 0 $ and the sum only contributes negative powers of $z$ with exponent starting at two.
Remark, II. From the convergence we require that $|z^2(1+w)| < 1$ in the double integral and must choose our contours appropriately. We must also verify that $(1-z^2)/z^2$ is outside the contour $|w|=\gamma.$ This is $1/z^2-1$ i.e. a circle of radius $1/\epsilon^2$ shifted by one to the left. Therefore when $\epsilon < 1/\sqrt{2}$ the pole is outside the contour.
Solution 2:
To get you started, here’s a HINT for the first identity:
Show that $\binom{n-1-i}{k-i}2^i$ is the number of subsets $A$ of $[n]=\{1,\ldots,n\}$ of cardinality at most $k$ such that $i+1\notin A$, and $|A\setminus[i]|=k-i$. That is $i+1$ is not in $A$, and $A$ has $k-i$ elements bigger than $i$.
Suppose that $A\subseteq[n]$ has at most $k$ elements, and let $d=k-|A|$. Let $i$ be the largest integer such that $|[i]\setminus A|=d$. If $d=0$, for example, this means that $i+1$ is the smallest member of $[n]$ not in $A$. If $d=1$, $i+1$ is the second-smallest member of $[n]$ not in $A$. Show that such $i$ always exists. (Clearly it’s uniquely determined by $A$ if it does exist.)
I’ll have to think further about the second one.