Estimating sum with binomial coefficients

Question

Lately when I was estimating complexity of some algorithm I came across this sum:

$$\sum_{k=0}^n \binom {n}{k} \binom {n-k}{k}$$

Is it possible to find a closed-form expression for this sum, or at least estimate this with some more known functions? I know that it is somewhere between $2^n$ and $3^n$ but I wonder if maybe some better estimation is possible.

Answer 1

I calculated the sums for $n\le6$ and plugged the sequence of values into The On-Line Encyclopedia of Integer Sequences (OEIS) It turns out to be sequence A002426, titled "Central trinomial coefficients: largest coefficient of (1+x+x^2)^n". Many interpretations, formulas, and references at the link.

Answer 2

A closed form is given by W/A as $$ \sum_{k=0}^n \binom {n}{k}\!\! \binom {n-k}{k}={}_2F_1 \left(-\frac{n-1}{2} ,-\frac{n}{2} ;1;4 \right) $$ Maybe this can help for some estimation.