Reduce the sequenceor how to calculate it efficiently

[kuldeepfouzda]

Sequence is
(in Summation notation)
SUMMATION[from k=0 to k=floor(n/2)] ^(n-k)C_(k) * 2^(n-k-1)
refer to this image
http://i.snag.gy/tFI7e.jpg
after expanding it becomes
⁽ⁿ⁾C₍₀₎*2^(n-1) + ^(n-1)C₍₁₎*2^(n-2) + ^(n-2)C₍₂₎ * 2^(n-3) +...
I want to calculate the value of function for a large value of n(up to
10¹⁰, and ans is to be found MODULUS to some prime number..like
10¹⁰+7).

Please simplify the series if possible or let me know the way how to
solve it efficiently.

 

[issacnewton]

Mathematica code

Sum[Binomial[n - k, k]*2^(n - k - 1), {k, 0, Floor[n/2]}]

you can use wolfram alpha to evaluate the exact form, if you don't have mathematica installed.

answer is attached