Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
more dimensional linear recurrences | Reply
I was wondering for a longer time if this approach can be improved to handle also more dimensional linear recurrences.

For example A(x,y)=k*A(x-1,y)+m*A(x,y-1)+n*A(x-2,y).

Suppose that A(0,x),A(x,0) are given.

Linear recurrences depending on constant last terms can be solved also by generating functions, so I tried also this method, but I do not know what to do with product of functions, for example when:
f(x,y) = 1 - f(x,y-1)*f(x-1,y).

Anyone heard about some multidimensional matrices used for this more variables recurrences? me not, but it would be great if someone had :)
Re: more dimensional linear recurrences (response to post by rasto6sk) | Reply
I don't know of anything that handles this. It could be that tensors would be the tool for the job, but I don't know enough about them to say.

One problem I can see is that a fixed amount of local state can't so easily be extended to find future values. For example, when computing a Fibonacci-like sequence you can extrapolate forwards from any two adjacent values. With the recurrence you give, it isn't possible to extrapolate from, say, Internal Error

Your request could not be processed. Please inform TopCoder.