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..?