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.