Recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$ I have been trying to solve this recurrence relation for a week, but I haven't come up with a solution.
$$f(n)=5f\left(\frac n2\right)-6f\left(\frac n4\right) + 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.
Please help me find a solution.
Kind regards.
 A: 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.
A: 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.
