please help me solve this equation in O(1) or O(logn) time. 1<=n<=10^18 equation: (n1) + (n2)(n3)/2! + (n3)(n4)(n5)/3! + (n4)(n5)(n6)(n7)/4! +......+ (n(n/2))(n(n/2+1))..(n(n1))/(n/2)! or this eqvivalent combinatric equation sum of C(nk,k) for all 1<=k<=floor(n/2) asked 14 Oct '18, 16:58

Think about what $C(nk,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). answered 15 Oct '18, 02:59
1
shouldn't the sequence be like 1,1,2,4,.. As for n=4:it is 3C1+2C2=4?
(15 Oct '18, 11:45)
1
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)
with
(15 Oct '18, 15:11)
1
yeah yeah right... :)
(15 Oct '18, 15:47)
@algmyr @vivek_1998299 can you help me solve this question? problem link: https://www.hackerrank.com/contests/moodysanalytics2018womeninengineering/challenges/combinationofdigits i have try lot but did't got correct formula. please help me.
(15 Oct '18, 21:42)

let dp[n] be ans for n this is recurrence dp[n]=dp[n1]+dp[n2]+1; dp[2]=1 dp[3]=2 calculate using expo... answered 15 Oct '18, 00:25

Is n even ??
not necessary.