# Is there a closed form to this expression?

Consider $$2^{n-1} + 2^{n-2}\dfrac{(n - 1)!}{1!(n - 2)!} + 2^{n-3}\dfrac{(n - 2)!}{2!(n - 2 \cdot 2)!} + 2^{n-4}\dfrac{(n - 3)!}{3!(n - 2 \cdot 3)!} + 2^{n-5} \dfrac{(n - 4)!}{4!(n - 2 \cdot 4)!} + \ldots$$

Until $(n - 2 \cdot k)$ equals to either $0$ or $1$ (even/odd). In other words: $$k = \lfloor \dfrac{n}{2} \rfloor$$

This expression comes from a programming puzzle, and it runs extremely slow when $n$ is large, so I try to find its closed form. Any idea or suggestion would be greatly appreciated.

-
$$\sum_{k=0}^{\lfloor n/2 \rfloor} 2^{n-k-1} \dfrac{(n-k)!}{k!(n-2k)!} = \sum_{k=1}^{\lfloor n/2 \rfloor} 2^{n-k} \dbinom{n-k}{k}$$ and you can write this in terms of Hypergeometric function. en.wikipedia.org/wiki/Hypergeometric_function – user17762 Jul 3 '12 at 0:58
Thanks. However, it will be not fast enough to pass all test cases due to the computation time of $2^n$ and $\dbinom{n}{k}$ – Chan Jul 3 '12 at 1:06
I'm surprised that $2^n$ would be that intensive computationally. Because $n$ is an integer, you may want to program your own POW(x, y) method with a loop for speed. The binomial coefficients are a bit harder, but may be done recursively. How long do you have for execution and what language are you using? – Argon Jul 3 '12 at 1:11
and how large is $n$? – lhf Jul 3 '12 at 1:12
$1 \leq n \leq 1000000000$ and the answer is mod $1000000007$. – Chan Jul 3 '12 at 2:05