# recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$

I’ve been trying to solve this recurrence relation for a week, but I haven’t come up with a solution.

$f(n)=5f(n/2)-6f(n/4) + n$

Solve this recurrence relation for $f(1)=2$ and $f(2)=1$

At first seen it looks like a divide and conquer equation, but the $6f(n/4)$ confuses me.
Kind regards,

#### Solutions Collecting From Web of "recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$"

You can only define $f(2^k)$. (Try to define $f(3)$. It is impossible.) Hence make the transformation
$$n=2^k, \quad \text{and define}\quad g(k)=f(2^k).$$
Then for $g$ you have that
$$g(0)=2, \quad g(1)=1\quad \text{and}\quad g(k+2)=5g(k+1)-6g(k)+2^{k+2}.$$
If $2^{k+2}$ was not there, then $g$ would have to be of the form $g(k)=c_12^k+c_23^k$. With this additional term the general solution of the recursive relation is of the form $g(k)=c_12^k+c_23^k+c_3k2^k$. Just find the values of the constants.

Suppose we start by solving the following recurrence:
$$T(n) = 5 T(\lfloor n/2 \rfloor) – 6 T(\lfloor n/4 \rfloor) + n$$
where $T(0) = 0.$
Now let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$
be the binary representation of $n.$
We unroll the recursion to obtain an exact formula for all $n:$
$$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1-\frac{5}{2}z+\frac{6}{4} z^2} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$
Observe that the roots of $$1-\frac{5}{2}z+\frac{6}{4} z^2 \quad\text{are}\quad\rho_0=1\quad\text{and}\quad\rho_1=\frac{2}{3}.$$
It follows that the coefficients of the rational term have the form
$$c_0 + c_1 \left(\frac{3}{2}\right)^j.$$
Actually solving for $c_{0,1}$ we obtain the formula
$$[z^j] \frac{1}{1-\frac{5}{2}z+\frac{6}{4} z^2} = 3 \left(\frac{3}{2}\right)^j – 2.$$
This gives the exact formula for $T(n):$
$$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(3 \left(\frac{3}{2}\right)^j – 2\right) \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k$$
Now for an upper bound on this consider a string of one digits, which gives
$$T(n)\le \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(3 \left(\frac{3}{2}\right)^j – 2\right) \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k = \frac{27}{2} \times 3^{\lfloor \log_2 n \rfloor} – (12+4\lfloor \log_2 n \rfloor) 2^{\lfloor \log_2 n \rfloor} -\frac{1}{2}.$$
For a lower bound consider a one followed by a string of zeros, which gives
$$T(n)\ge \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(3 \left(\frac{3}{2}\right)^j – 2\right) 2^{\lfloor \log_2 n \rfloor} = 9 \times 3^{\lfloor \log_2 n \rfloor} – (8+2\lfloor \log_2 n \rfloor) 2^{\lfloor \log_2 n \rfloor}.$$
Joining the two bounds it follows that $T(n)$ is asymptotic as follows:
$$T(n)\in\Theta\left(3^{\lfloor \log_2 n \rfloor}\right) = \Theta(2^{\log_2 n \times \log_2 3}) = \Theta(n^{\log_2 3})$$
with the leading coefficient between $9/2$ and $9.$
Now we are supposed to have $f(0)=0$, $f(1)=2$, and $f(2)=1,$ so start with
$$T(n) + \left(3 \left(\frac{3}{2}\right)^{\lfloor \log_2 n \rfloor} – 2\right) 2^{\lfloor \log_2 n \rfloor}.$$
This is equal to two at $n=1$ but equal to twelve at $n=2$, so we need an additional contribution of
$$T(n) + \left(3 \left(\frac{3}{2}\right)^{\lfloor \log_2 n \rfloor} – 2\right) 2^{\lfloor \log_2 n \rfloor} – 11 (1-d_{\lfloor \log_2 n \rfloor-1})\times \left(3 \left(\frac{3}{2}\right)^{\lfloor \log_2 n \rfloor-1} – 2\right) 2^{\lfloor \log_2 n \rfloor-1}.$$
This simplifies to (for $n\ge 2$)
$$T(n) + 3^{\lfloor \log_2 n \rfloor+1} -2^{\lfloor \log_2 n \rfloor+1} – 11 (1-d_{\lfloor \log_2 n \rfloor-1})\times \left(3^{\lfloor \log_2 n \rfloor} -2^{\lfloor \log_2 n \rfloor}\right).$$
The behavior here is highly erratic but the formula is exact and the order of growth remains the same. Here is another Master Theorem computation at MSE.