8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ with those divisions it is not really a recurrence relation. are you sure they should not be minus signs, i.e. the problem is: $f_n = 5f_{n-2} - 6f_{n-4} +n$? that would make more sense. $\endgroup$ – David Holden Dec 22 '13 at 14:07
  • $\begingroup$ the question is exactly same as I wrote up. I got this question from my dicrete lecturer and I search entire book (which is Kenneth Rosen)and I couldnt come up with any identical question with this question. Thats why I havent come up with solution. $\endgroup$ – zerre Dec 22 '13 at 14:16
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thak you yiorgos $\endgroup$ – zerre Dec 22 '13 at 15:11
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.