3b

The Fibonacci k-step numbers are a generalization of the Fibonacci and Tetranacci sequences, where F_i = 0 for i 0, F1 = 1, F₂ = 1, and for every j 3:

F_j = F_j-1 + F_j-2 + + F_j-k,

i.e. Fj is the sum of the k previous numbers in the sequence. You will implement an OCaml function fib k step : int -> int -> int for computing these numbers efficiently.

TODO: Implement an OCaml function fib_k_step : int -> int -> int, which accepts two integers n and k and, for a fixed k, computes in time linear in n the nth Fibonacci k-step number.2