# Estimating sum with binomial coefficients

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.

• @bof: aah, you're right. Apologies. But what is $C^{1}_{n-1}$ supposed to mean (second term when $k=n-1$) ? – Alexandre Halm Oct 1 '14 at 7:55
• @AlexH. I guess it's zero. $\binom xk=x(x-1)(x-2)\cdots(x-k+1)/k!$ is zero for $x=0,1,2,\dots,k-1$. – bof Oct 1 '14 at 8:03
• I suppose what the OP wants is the total number of ways to pick 2k objects from n objects by first picking k objects from n and then picking k objects from the remaining. – Gautam Shenoy Oct 1 '14 at 8:05
• Looks like you got a couple of pretty good answers to your question. What don't you like about them? – bof Oct 7 '14 at 2:57

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.
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.
For every positive integer $$n$$, $$\sum_{k=0}^n \binom {n}{k} \binom {n-k}{k} = \biggl\lfloor\Bigl(1+3^n+\frac{1}{3^n}\Bigl)^n \biggr\rfloor - 3^n \biggl\lfloor\Bigl(\frac{1}{3}+3^{n-1}+\frac{1}{3^{n+1}}\Bigl)^n \biggr\rfloor$$