2
$\begingroup$

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: enter image description here

  • 0
    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...2011-04-18

2 Answers 2

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

0

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.

  • 1
    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$.2011-04-18