Solving recurrence relations (change variable etc.) problems

Question

I have been given

$$f(1) = 3\\ f(2) = 8\\ f(n) = 6f(n/2) - 8 f(n/4) \;,\;\; n > 0$$

How would I go about solving this? I've tried working so hard to get this to no avail. If someone can give hints on how to solve relations of this type with just one constant, e.g.

$$ f(0) = 2\\ f(n) = 6f(n-1) - 5\;,\;\; n > 0$$

I would be so grateful..

Answer 1

Hint: Don't cry! Better denote $g(n)=f(n/2)-2f(n/4)$ and solve the equation $g(2n)=4g(n)$.

Answer 2

Let $T_n = f(2^n)$ and plug into your equation to get a linear equation:

$$T_n-6 T_{n-1}+8 T_{n-2}=0$$ $$T_0=3$$ $$T_1=8$$

The solution to this equation is

$$T_n = 2 (2^n)^2 + 2^n$$

Therefore

$$f(n) = 2 n^2+n$$

Answer 3

Do you want to know how fast that function grows or what do you mean by solve? If you want a fast computation of the function you can compute it with this matrix.

\begin{pmatrix} 6 & -8 \\ 1 & 0 \end{pmatrix}

with the initial vector

\begin{pmatrix} 8 \\ 3 \end{pmatrix}

(If i haven't made any mistakes, also note that you compute the $2^n$ value and not the $n$ th value.)

If you want to compute the asymptotically growth of the function, i guess you would need to compute the growth of that matrix and take it's log maybe because the matrix computes the $2^n$ value.

Answer 4

First start by solving the related recurrence for $T(n) = f(n) +1$ where $T(0)=0:$ $$ f(n)+1 = 6(f(n/2)+1) -6 - 8(f(n/4)+1) + 8 + 1$$ which gives $$ T(n) = 6 T(\lfloor n/2\rfloor) -8 T(\lfloor n/4\rfloor) + 3.$$ Now let the binary representation of $n$ be $$ n= \sum_{k=0}^{\lfloor\log_2 n\rfloor} d_k 2^k.$$ Actually the values of the individual digits don't count here (except for the next to topmost digit) as this recurrence is particularly simple. Using the same idea as here, we see that $$T(n) = 3 \sum_{j=0}^{\lfloor\log_2 n\rfloor} [z^j] \frac{1}{1-6z+8z^2} = \frac{3}{2} \sum_{j=0}^{\lfloor\log_2 n\rfloor} (4^{j+1}-2^{j+1})\\ = \frac{3}{2} \times \left(\frac{1}{3} 4^{\lfloor\log_2 n\rfloor+2} - 2^{\lfloor\log_2 n\rfloor+2} + \frac{2}{3}\right) = \frac{1}{2} 4^{\lfloor\log_2 n\rfloor+2} - 3\times 2^{\lfloor\log_2 n\rfloor+1} +1.$$ Now we still need to apply a correction to produce a recurrence $S(n)$ with initial values $S(1)=4$ and $S(2)=9.$ Since $T(1)=3,$ the first correction is $$\frac{1}{2} (4^{\lfloor\log_2 n\rfloor+1}-2^{\lfloor\log_2 n\rfloor+1}).$$ Since $T(2)+1/2\times(4^2-2^2)=27,$ the second correction is $$-9 [[d_{\lfloor\log_2 n\rfloor-1}=0]] (4^{\lfloor\log_2 n\rfloor}-2^{\lfloor\log_2 n\rfloor}).$$ This yields $$S(n) = 10\times 4^{\lfloor\log_2 n\rfloor}-7\times 2^{\lfloor\log_2 n\rfloor}+1 -9 [[d_{\lfloor\log_2 n\rfloor-1}=0]] (4^{\lfloor\log_2 n\rfloor}-2^{\lfloor\log_2 n\rfloor}).$$ The conclusion is that $$ f(n) = 10\times 4^{\lfloor\log_2 n\rfloor}-7\times 2^{\lfloor\log_2 n\rfloor} -9 [[d_{\lfloor\log_2 n\rfloor-1}=0]] (4^{\lfloor\log_2 n\rfloor}-2^{\lfloor\log_2 n\rfloor}),$$ so that $$f(n) \in \Theta\left(4^{\lfloor\log_2 n\rfloor}\right) = \Theta(n^2).$$ (The next to topmost digit does not quite cancel the dominant term.) As there was some ambiguity in the problem definition (the value at zero was not specified yet it arises during the recursion), this solution avoids the recursion reaching zero by also specifying that $f(3) = S(3)-1 = 26.$