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

Question

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.

Answer 1

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.

Answer 2

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.