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:

-
There was a small "algebra" slip in your calculation above, in addition to the missing the power of $2$ stuff. If you have the recurrence $h_{k}=5h_{k-1}-4h_{k-2}$, this turns into $h_{k}-5h_{k-1}+4h_{k-2}=0$, and the characteristic equation is $a^2-5a+4=0$. (You had a sign error, and wrote $a^2-5a-4=0$.) –  André Nicolas Apr 18 '11 at 13:19
There is a (huge) problem of definition in the example you are trying to solve and in the one for which you reproduce a "solution", which is, for what $n$ is $f(n)$ defined? If one wants to define $f(n)$ for every positive integer $n$, then one has to also define it for every $n=p/2^q$ with $p$ and $q$ positive integers. Based on the given recurrence relation and initial conditions, one can deduce $f(n)$ for every $n=2^k$ and $k$ nonnegative integer but there is no way to compute $f(n)$ for other values of $n$. So, $f(3)$, $f(5)$, $f(6)$, $f(7)$ etc., are free parameters. –  Did Apr 18 '11 at 13:52
As an aside, I very much hope that the "solution" you reproduce does not end there and that its authors mention that the only possible sequence $(f_k)$ is $f_k=2^k$, that is $f(n)=n$ for every $n$ positive integer and power of $2$... –  Did Apr 18 '11 at 14:42
That's true. They have mentioned that. They have simplified for learning purposes. However, I am not sure how to solve the recurrence relation after identifying the characteristic equation since, the example has repeated roots and the relation I am solving doesn't... –  user9492 Apr 18 '11 at 14:54

• 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).

-

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.

-
what is the correct characteristic equation for the above relation? How do I arrive at it? –  user9492 Apr 18 '11 at 12:10
The example you posted gives the right explanation but is a bit confusing because it misuses $f$ instead of giving it a new name $g$. –  lhf Apr 18 '11 at 12:15