Second Order Homogeneous Recurrence Relation Question I am revising for an exam in a few weeks and I have the following recurrence relation:
f(1) = 1
f(2) = 2
f(n) = 5f(n/2) - 4f(n/4), n > 2

My lecture notes are confusing me and I was hoping to get some help on how to solve this...
I get the characteristic equation:
a^2 - 5a + 4 = 0

EDIT: Not sure if this is right?
Therefore:
p1 = 1 and p2 = 4
I now need to form a general solution for 'f' in terms of k...
I'm not sure how to do this...
I am following the example below:

 A: *

*yes, you got the right characteristic equation.

*yes, the roots are 1 and 4

*presumably you are doing linear recurrence relations, for which you know how to solve. This problem (and the example given) have an extra things to do which is dealing with the $n = 2^k$ transformation.


So the solution method for the whole problem is: do the transformation first, solve the transformed problem, then transform back.
The general solution of the transformed problem involves the roots 1 and 4 so something like $c_1 4^k + c_2 1^k = c_1 4^k + c_2$. You already know how to solve for $c_1$ and $c_2$ (use a linear system with the base cases (but that's the fun part...what are the base cases -in the transformed system-)).
So now transform back? How do you do that? How do you get a function of $n$ using one that's already in $k$? (you have a relation between $n$ and $k$, use that and simplify).
A: The characteristic equation you gave is not for this recurrence. It's for $f(n+2)=5f(n+1)-4f(n)$. Now, if you restrict $n$  to be a power of $2$, then you can write $g(n)=f(2^n)$ and get $g(n+2)=5g(n+1)-4g(n)$. The solution is $g(n)=a 1^n + b4^n$, for some $a$ and $b$ depending on the initial conditions.
