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.

  • 2
    $$\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. http://en.wikipedia.org/wiki/Hypergeometric_function2012-07-03
  • 0
    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}$2012-07-03
  • 0
    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?2012-07-03
  • 0
    and how large is $n$?2012-07-03
  • 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