Algorithm for k-Fibonacci

Question

We all know fibonacci series, when k = 2.

I.e.: 1,1,2,3,5,8,13

But this is the 2-fibonacci. Like this, I can count the third-fibonacci:

1,1,2,4,7,13,24

And the 4-fibonacci:

1,1,2,4,8,15,29

...and so goes on

What I'm asking is an algorithm to calculate an 'n' element inside a k-fibonacci series.

Like this: if I ask for fibonacci(n=5,k=4), the result should be: 8, i.e. the fifth element inside the 4-fibonacci series.

I didn't found it anywhere web. A resouce to help could be mathworld

Anyone? And if you know python, I prefer. But if not, any language or algorithm can help.

Tip I think that can help: Let's analyze the k-fibonacci series, where k will go from 1 to 5

k    fibonacci series

1    1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, ...
2    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
3    1, 1, 2, 4, 7, 13, 24, 44, 81, ...
4    1, 1, 2, 4, 8, 15, 29, 56, 108, ...
5    1, 1, 2, 4, 8, 16, 31, 61, 120, ...

Analyzing this, we can see that the array [0:k] on the k-fibonacci series is equal to the previous fibonacci series, and it goes on till the k=1

i.e. (I'll try to show, but I'm not finding the right way to say it):

k    fibonacci series

1    1, 
2    1, 1, 
3    1, 1, 2, 
4    1, 1, 2, 4, 
5    1, 1, 2, 4, 8, 

Hope I've helped somehow to solve this.

[SOLUTION in python (if anyone needs)]

class Fibonacci:

    def __init__(self, k):
        self.cache = []
        self.k = k

        #Bootstrap the cache
        self.cache.append(1)
        for i in range(1,k+1):
            self.cache.append(1 << (i-1))

    def fib(self, n):
        #Extend cache until it includes value for n.
        #(If we've already computed a value for n, we won't loop at all.)
        for i in range(len(self.cache), n+1):
            self.cache.append(2 * self.cache[i-1] - self.cache[i-self.k-1])

        return self.cache[n]


#example for k = 5
if __name__ == '__main__':
    k = 5
    f = Fibonacci(k)
    for i in range(10):
        print f.fib(i),

Answer 1

As with 2-fibonacci, dynamic programming is the way to go. Memoize the values of earlier ks to quickly compute the later ones, in O(n) time.

Another optimization that you can use to improve speed for large values of k is instead adding f(n-k) through f(n-1) to get f(n), instead just use (2*f(n-1)) - f(n-k-1). Since this only uses 2 lookups, 2 adds, and a multiply, it's vastly superior to k lookups and k adds when k becomes large (but it's still O(n), just a smaller constant multiplier).