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