# Fast computation of k-fibonacci numbers

Let's define the sequence of $k$-Fibonacci numbers as $$F_i = 2^i, ~~ 0 \leq i \leq k-1$$ $$F_i = F_{i-1} + \dots + F_{i-k}, ~~ i \geq k$$

I have a problem which requires to compute $n$-th $k$-Fibonacci number modulo $10^9 + 7$ efficiently. $n$ can be as large as $10^6$, $k$ can have any value between $1$ and $n$, time limit is $1$ second.

When $k$ is small enough i can use matrix-power approach for computing $n$-th members of linear recurrent sequences. This requires $O(k^3 \log(n)$ operations which is not feasible when $k > 250$ since takes more than one second.

When $k$ is large but $n$ is small i can compute this exactly by definition with $O(nk)$ operations. This approach is also not feasible when $k,n \approx 10^5$ or larger.

So how can i compute them faster? I neither derived nor found on the web any useful formulas which allow to represent this recurrence with smaller depth. Thus i believe that it's more an algorithmic than combinatorial question.

## 1 Answer

It's trivial to do in O (n), using the obvious formula $F_{i+1} = 2F_i - F_{i-k}$. Just write down the definition of $F_{i+1}$ and note that it is mostly (but not quite) the same as the definition of $F_i$.

• Thank you. Very cool and indeed trivial. I'm sad not to notice this fact myself. – Igor Mar 11 '18 at 18:17
• It's easy for problems from problem websites because you know it can be done. You know there is a trick, and the question is just which one? – gnasher729 Mar 11 '18 at 19:29
• You also know it can be done in one second, which means it can be done in 0.1 seconds with micro-optimisations, so for k, n ≈ 10^6 it can be done in less than 100n operations. Which means calculating F_n+1 should be quite simple. – gnasher729 Mar 12 '18 at 0:20