2 added 213 characters in body

I'm surprised no one has posted a proof by double counting yet. First, I will rewrite the sum as $$F(n,k)=\sum_{j=0}^k\binom{2n+1}{2n-2j+1}\binom{n-j}{n-k}.$$ This counts the number of ways I can pick $2n-2j+1$ squares out of a $1\times (2n+1)$ grid, color them alternately black, white, black... etc. and then place a mark on $n-k$ white squares.

By deleting the first square as well as any immediate square following a marked white square we end up with a sequence of $n+k$ squares, $n-k$ of which are marked white squares and several others are colored.

Another way to count this is to choose the marked white squares first. This can be done in $\binom{n+k}{n-k}$ ways. And then specify the unmarked colored squares, this can be done in $2^{2k}$ ways. We get that $$F(n,k)=2^{2k}\binom{n+k}{n-k}$$ which is what we wanted.

Notice that I've left it as an exercise to show that deleting the squares is actually a bijection between the two sets, but this is quite easy to show. Indeed you only have to worry about adding back a square and deciding whether it should be colored or not. This can be done with a parity check on the number of colored boxes between consecutive marked boxes.

1

I'm surprised no one has posted a proof by double counting yet. First, I will rewrite the sum as $$F(n,k)=\sum_{j=0}^k\binom{2n+1}{2n-2j+1}\binom{n-j}{n-k}.$$ This counts the number of ways I can pick $2n-2j+1$ squares out of a $1\times (2n+1)$ grid, color them alternately black, white, black... etc. and then place a mark on $n-k$ white squares.

By deleting the first square as well as any immediate square following a marked white square we end up with a sequence of $n+k$ squares, $n-k$ of which are marked white squares and several others are colored.

Another way to count this is to choose the marked white squares first. This can be done in $\binom{n+k}{n-k}$ ways. And then specify the unmarked colored squares, this can be done in $2^{2k}$ ways. We get that $$F(n,k)=2^{2k}\binom{n+k}{n-k}$$ which is what we wanted. Notice that I've left it as an exercise to show that deleting the squares is actually a bijection between the two sets, but this is quite easy to show.