Using computer, I saw that the following identity seems to be true. Let $n$ be an integer. Let $0\leq s\leq n$. $$\sum\limits_{k=0}^s{{2n+1}\choose{2k}}{{n-k}\choose{s-k}}=4^s{{n+s}\choose{n-s}}.$$
I tried many techniques including direct compuations, generating functions, combinatorial tools, etc. However, everything failed. Perhaps there is a link with hypergeometric functions but it is not clear for me. Does any one know how to prove it?
We use generating functions to get a different formula for the LHS, and then a simple counting argument gives the right side.
The left side can be seen as the coefficient of $x^{2s}$ in:
$$\frac{(1+x)^{2n+1}}{(1-x^2)^{n-s+1}}=\frac{(1+x)^{n+s}}{(1-x)^{n-s+1}}$$
And that coefficient of $x^{2s}$ in the right formula is:
$$\sum_{k=0}^{2s}\binom{n+s}{k}\binom{n+s-k}{2s-k}$$
This in turn counts the number of ways to pick $(A,B)$ with $A\subseteq B\subseteq \{1,2,\dots,n+s\}$ with $|B|=2s.$ $k$ here represents $|A|.$ There aree $\binom{n+s}{k}$ ways to choose $A$ and $\binom{n+s-k}{2s-k}$ ways to pick the rest of $B.$
But we can also count the number of $(A,B)$ by picking $B$ first in $\binom{n+s}{2s}$ ways and then choose $A$ in $2^{2s}$ ways.
The key motivation here is that the left side looked like a Cauchy product. We just had to figure out what. Here, $$(1+x)^{2n+1}=\sum_{k=0}^\infty \binom{2n+1}{k}x^k\\\frac1{(1-x^2)^{n-s+1}}=\sum_{k=0}^\infty \binom{n-s+k}{k}x^{2k}$$
We get a general result from:
$$\frac{(1+x)^{a+b+1}}{(1-x^2)^{a+1}}=\frac{(1+x)^b}{(1-x)^{a+1}}$$
the coefficient of $x^c$ on the left side is:
$$\sum_{k=0}^{\lfloor c/2\rfloor}\binom{a+b+1}{c-2k}\binom{k+a}{k}\tag1$$
The coeficient of $x^c$ on the right side is:
$$\sum_{j=0}^c \binom{b}{c-j}\binom{a+j}j\tag2$$
So $(1)$ is equal to $(2)$.
You were right, the identity is true. Set $S_s = \sum_{k=0}^s \binom{2n+1}{2k} \binom{n-k}{s-k}$. We want to prove $S_s = 4^s\binom{n+s}{n-s}=4^s\binom{n+s}{2s}$ by induction on $s$.
For $s = 0$, $S_0 = \binom{2n+1}{0} \binom{n}{0} = 1$ so the right-hand side is $4^0 \binom{n+0}{0} = 1\implies$ The base case holds.
Now assume $S_{s-1} = 4^{s-1} \binom{n+s-1}{2s-2}$. We want to prove $S_s$ satisfies this recurrence: $$s(2s-1) S_s - 2(n+s)(n-s+1) S_{s-1} = 0$$
Let $F(s,k) = \binom{2n+1}{2k}\binom{n-k}{s-k}$. Using $\binom{n-k}{s-1-k} = \frac{s-k}{n-s+1}\binom{n-k}{s-k}$, we can express the recurrence as a single sum $\sum_{k=0}^s T_k = 0$, where: $$T_k = s(2s-1)F(s,k) - 2(n+s)(s-k)F(s,k) = [2k(n+s) - s(2n+1)]F(s,k)$$
Now to prove that $\sum_{k=0}^s T_k = 0$, we define the telescoping sequence: $$H_k = -(2n-2k+1)(s-k) F(s,k)$$
By expanding the binomial coefficients, we can verify that: $$H_k - H_{k-1} = [2k(n+s) - s(2n+1)] F(s,k) = T_k$$
Summing $T_k$ from $k=0$ to $s$ telescopes the series: $$\sum_{k=0}^s T_k = H_s - H_{-1}$$ Because $H_s$ contains the factor $(s-s) = 0$ and $H_{-1}$ contains the term $\binom{2n+1}{-2} = 0$, both evaluate to $0$. Thus, $\sum_{k=0}^s T_k = 0$, and our recurrence is verified.
Now we just substitute the inductive hypothesis into our recurrence: $$S_s = \frac{2(n+s)(n-s+1)}{s(2s-1)} \left[ 4^{s-1} \frac{(n+s-1)!}{(2s-2)!(n-s+1)!} \right]$$
Simplifying the factorials yields: $$S_s = 4^{s-1} \frac{2(n+s)!}{s(2s-1)(2s-2)!(n-s)!} = 4^s \frac{(n+s)!}{(2s)!(n-s)!}$$
Therefore, $$S_s = 4^s \binom{n+s}{2s}$$ and our induction is complete.
The telescoping idea is the Wilf-Zeilberger method and is really useful for proving things like this.
WLOG, we can change upper limits of $k$ to $\infty$. We use $\binom{n-k}{s-k} = \binom{n-k}{n-s} = [x^{n-s}](1+x)^{n-k}$, then $$ \sum\limits_{k}{{2n+1}\choose{2k}}{{n-k}\choose{s-k}}=[x^{n-s}]\sum\limits_{k}{{2n+1}\choose{2k}}(1+x)^{n-k}=[x^{n-s}]\sum\limits_k \binom{2n+1}{2k+1} (1+x)^{k} $$ At this stage, let us substitute $m=2n+1$, and sum this up over $m \geq 0$ marking each summand with $y^{m}$: $$ [x^{n-s}y^{2n+1}] \sum\limits_{k}(1+x)^k \sum\limits_{n} \binom{m}{2k+1} y^m = [x^{n-s}y^{2n+1}] \sum\limits_k (1+x)^k \frac{y^{2k+1}}{(1-y)^{2(k+1)}} $$ Here, we used $\sum\limits_{n} \binom{n}{k} x^n = \frac{x^k}{(1-x)^{k+1}}$. Now, the sum simplifies into $$ [x^{n-s}y^{2n+1}] \frac{y}{(1-y)^2}\sum\limits_k\frac{(1+x)^k y^{2k}}{(1-y)^{2k}} $$ We use $\sum\limits_k x^k = \frac{1}{1-x}$ to turn this into $$ [x^{n-s}y^{2n+1}] \frac{y}{(1-y)^2-y^2(1+x)}=[x^{n-s}y^{2n}]\frac{1}{1-2y-y^2x} $$ We can now factor out the part relying on $x$ as follows: $$ [y^{2n}] \frac{1}{1-2y} [x^{n-s}] \frac{1}{1-\frac{y^2}{1-2y}x}=[y^{2n}] \frac{1}{1-2y} \frac{y^{2(n-s)}}{(1-2y)^{n-s}}=[y^{2s}]\frac{1}{(1-2y)^{n-s+1}} $$ From $\frac{1}{(1-x)^{n+1}} = \sum\limits_k \binom{n+k}{k} x^n$, this turns into $2^{2s}\binom{n+s}{n-s}$. $\square$
