I am trying to prove the following equality $$ \sum_{r=k}^{n}\binom{2n+1}{2r+1}\binom{r}{k}=\binom{2n-k}{k}2^{2n-2k}~~;~k\le n. $$ I noticed that for $k=0$ it becomes $$ \sum_{r=0}^{n}\binom{2n+1}{2r+1}=2^{2n}, $$ which is well known equality. Also have I tried to use the equality $$ \sum_{r=k}^{n}\binom{n}{r}\binom{r}{k}=\binom{n}{k}2^{n-k}, $$ but with no success.
Any hints and suggestions would be appreciated.
Thanks!
On
This one can also be done using complex variables. We will use a different generating function than in the accepted answer.
Suppose we are trying to evaluate $$\sum_{r=k}^n {2n+1\choose 2r+1} {r\choose k}.$$
Introduce the integral representation $${2n+1\choose 2r+1} = \frac{1}{2\pi i} \int_{|z|=3/2} \frac{(1+z)^{2n+1}}{z^{2r+2}} \;dz.$$ We will use the annulus $1<|z|<\infty$ with this integral.
This integral sets the range of the sum so we can let $r$ go to infinity to obtain $$\frac{1}{2\pi i} \int_{|z|=3/2} \frac{(1+z)^{2n+1}}{z^2} \sum_{r=k}^\infty {r\choose k} z^{-2r} \;dz.$$
Observe that the sum term only converges when $|z|>1.$ This does not pose a problem however as it is contained in the chosen annulus.
The inner sum is $$\sum_{r=k}^\infty {r\choose k} z^{-2r} = \sum_{r=0}^\infty {r+k\choose k} z^{-2r-2k} = z^{-2k} \sum_{r=0}^\infty {r+k\choose k} z^{-2r} \\ = z^{-2k} \frac{1}{(1-1/z^2)^{k+1}} = z^2 \times z^{-2(k+1)} \frac{1}{(1-1/z^2)^{k+1}} \\ = \frac{z^2}{(z^2-1)^{k+1}}.$$
Substitute this into the sum to get $$\frac{1}{2\pi i} \int_{|z|=3/2} \frac{(1+z)^{2n+1}}{z^2} \frac{z^2}{(z^2-1)^{k+1}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=3/2} \frac{(1+z)^{2n-k}}{(z-1)^{k+1}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=3/2} \frac{(2+z-1)^{2n-k}}{(z-1)^{k+1}} \; dz \\ = \frac{2^{2n-k}}{2\pi i} \int_{|z|=3/2} \frac{(1+(z-1)/2)^{2n-k}}{(z-1)^{k+1}} \; dz.$$
We thus have from the pole at $z=1$ $$2^{2n-k} [(z-1)^k] (1+(z-1)/2)^{2n-k} \\ = 2^{2n-k} {2n-k\choose k} 2^{-k} = 2^{2n-2k} {2n-k\choose k}.$$
We have: $$ \sum_{r=0}^{n}\binom{2n+1}{2r+1}z^{2r} = \frac{(1+z)^{2n+1}-(1-z)^{2n+1}}{2z}\tag{1}$$ so the given identity can be proved by replacing $z$ with $\sqrt{w}$: $$ \sum_{r=0}^{n}\binom{2n+1}{2r+1}w^{r} = \frac{(1+\sqrt{w})^{2n+1}-(1-\sqrt{w})^{2n+1}}{2\sqrt{w}}\tag{2}$$ and differentiating $k$ times both sides of $(2)$, then evaluating in $w=1$. Notice that the RHS of $(2)$ is someway related to Fibonacci-like numbers; if we set: $$ A_{2n+1}(w)\triangleq\frac{(1+\sqrt{w})^{2n+1}-(1-\sqrt{w})^{2n+1}}{2\sqrt{w}} $$ we have: $$ A_0(w)=0,\qquad A_1(w)=1,\qquad A_{n+2}(w) = 2\cdot A_{n+1}(w)-(1-w)\cdot A_n(w).\tag{3}$$