Calculating nCr in 3 seconds

Calculating nCr in 3 seconds

I have to write a piece of code and I need to calculate sum over (n-i) C
(i). [n-i choose i] (i running from 0 to n/2 ). Where n is in the order of
10^6. The time limit is 3 seconds. Please help