How to solve linear recurrences involving two functions?
- by Aditya Bahuguna
Actually I came across a question in Dynamic Programming where we need to find the number of ways to tile a 2 X N area with tiles of given dimensions..
Here is the problem statement
Now after a bit of recurrence solving I came out with these.
F(n) = F(n-1) + F(n-2) + 2G(n-1), and
G(n) = G(n-1) + F(n-1)
I know how to solve LR model where one function is there.For large N as is the case in the above problem we can do the matrix exponentiation and achieve O(k^3log(N)) time where k is the minimum number such that for all km F(n) does not depend on F(n-k). The method of solving linear recurrence with matrix exponentiation as it is given in that blog.
Now for the LR involving two functions can anyone suggest an approach feasible enough for large N.
