So, I was trying to solve this problem on a codechef contest that ended just now.I tried to reduce the expression of g(n).The maximum I could simplify is upto this point:
g(n) = pow(4, n) + 2*(pow(4,n)-1)/3 + Summation of (pow(4,n-k)*f(k)) where k ranges from n to 1.
But I couldn't find a way to find sum of function f upto a point.
On looking at accepted codes, I find that this question was to be done using Matrix Multiplication, kind of what we do in finding fibonacci numbers.
I want to know how do you guess the values in the matrix to be multiplied.?Is there a particular way to be followed around such questions..?
Some general explanation: http://community.topcoder.com/tc?module=Static&d1=features&d2=010408 Interesting blog: http://fusharblog.com/solving-linear-recurrence-for-programming-contest/
Thank you. That helped, especially that blog.