 # how to solve this equation efficiently?

1<=n<=10^18

equation:

(n-1) + (n-2)(n-3)/2! + (n-3)(n-4)(n-5)/3! + (n-4)(n-5)(n-6)(n-7)/4! +…+ (n-(n/2))(n-(n/2+1))(n-(n-1))/(n/2)!

or this eqvivalent combinatric equation

sum of C(n-k,k) for all 1<=k<=floor(n/2)

1 Like

Is n even ??

1 Like

not necessary.

let dp[n] be ans for n

this is recurrence

dp[n]=dp[n-1]+dp[n-2]+1;

dp=1
dp=2

calculate using expo…

1 Like

Think about what C(n-k,k) looks like in Pascal’s triangle. The sums you have are essentially (barring a leading term C(n,0)) sums along diagonals of Pascal’s triangle

\begin{array}{ccccccccc} & & & & {\color{red}1}\\ & & & {\color{green}1} & & {\color{blue}1}\\ & & {\color{blue}1} & & {\color{magenta}2} & & {\color{orange}1}\\ & {\color{magenta}1} & & {\color{orange}3} & & 3 & & 1\\ {\color{orange}1} & & 4 & & 6 & & 4 & & 1\\ \end{array}

which turns out to be Fibonacci numbers

{\color{red}1}, {\color{green}1}, {\color{blue}2}, {\color{magenta}3}, {\color{orange}5}, \ldots

for which you can apply the usual fast techniques for calculating Fibonacci numbers (like matrix exponentiation).

2 Likes

shouldn’t the sequence be like 1,1,2,4,…

As for n=4:-it is 3C1+2C2=4?

1 Like

Like I wrote, the sum asked about is essentially Fibonacci numbers. However it’s missing the leading term C(n,0). Without the leading term the sequence is just Fibonacci numbers minus one: 0,0,1,2,4,7,12,\ldots.

Compare (python code, implement choose yourself)

[sum(choose(n-k,k) for k in range(1,n//2+1)) for n in range(0,10)]
-> [0, 0, 1, 2, 4, 7, 12, 20, 33, 54]


with

[sum(choose(n-k,k) for k in range(0,n//2+1)) for n in range(0,10)]
-> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
1 Like

yeah yeah right… 1 Like

thank you… got it.

@algmyr
@vivek_1998299
can you help me solve this question?