5
$\begingroup$

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.

  • 0
    $1 \leq n \leq 1000000000$ and the answer is mod $1000000007$.2012-07-03

1 Answers 1

1

Hint: If you compute five or six terms you can find at simpler expression at OEIS.

  • 0
    Extremely helpful site! Great thanks.2012-07-03