<s>[INST] Solving recurrence relation: $ f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3$ 
$f(n) = 3f(n/2) - 2f(n/4)  |  f(2) = 5, f(1) = 3$

I have attempted to solve it by letting 

$n = 2^k$
$f(2^k) = 3f(2^{k-1}) - 2f(2^{k-2})$

Then set 

$S(k) = f(2^k)$
$S(k) = 3*S(k-1) - 2*S(k-2)$
let S(k) = $x^k$
$x^k = 3x^{k-1} - 2x^{k-2} $ (divide by $x^{k-2}$ and
  rearrange)
$x^2 - 3x + 2 = 0$
solving for $(x-1)(x-2)$


Here I get a bit stuck as I try to proceed with the following:

$S(k) = c_1\times 1^k + c_2 \times 2^k$

But cannot go further on my own. Any advice as the substitutions have confused me!
 [/INST] The reader may  be interested to note that there  is a closely related
recurrence that  we can solve exactly  and not just  for powers of
two.
Suppose we put
$$f(n) = 3 f(\lfloor n/2 \rfloor) - 2 f(\lfloor n/4 \rfloor).$$
This requires a value for $f(0)$ so we set
$$f(n) = 2n+1 \quad\text{when} \quad n<3.$$
Now    observe    that    the    generating    function    $$g(z)    =
\frac{1}{1-(3z-2z^2)}$$ encodes the tree  of values visited during the
computation of $f(n)$ in a natural way.
Let  $$n =  \sum_{k=0}^{\lfloor \log_2  n  \rfloor} d_k  2^k$$ be  the
binary representation of $n$. We  now compute a closed form expression
for $f(n)$ when $n\ge 2.$
Case  A.   The  leading  digits   are  two  one   digits,  i.e.
$(d_{\lfloor  \log_2 n  \rfloor} d_{\lfloor  \log_2 n  \rfloor-1})_2 =
(11)_2.$ Then the two terminal  values for the recursion are $n=3$ and
$n=1$.
The case $n=3$ has $f(n)=7$ and thus gives the contribution
$$7\times 
[z^{\lfloor \log_2  n  \rfloor - 1}] \frac{1}{1-(3z-2z^2)}.$$
The case $n=1$ has $f(n)=3$ but the last step must have been on the
$\lfloor n/4 \rfloor$ branch so as not to be routed through $n=3$,
giving
$$3\times (-2)\times 
[z^{\lfloor \log_2  n  \rfloor - 2}] \frac{1}{1-(3z-2z^2)}.$$
Case B. The  leading digits are a one digit  followed by a zero
digit  i.e.   $(d_{\lfloor  \log_2  n  \rfloor}  d_{\lfloor  \log_2  n
\rfloor-1})_2 =  (10)_2.$ Then the  terminal values for  the recursion
are $n=2$ and $n=1$.
The case $n=2$ has $f(n)=5$ and thus gives the contribution
$$5\times 
[z^{\lfloor \log_2  n  \rfloor - 1}] \frac{1}{1-(3z-2z^2)}.$$
The case $n=1$ has $f(n)=3$ but the last step must have been on the
$\lfloor n/4 \rfloor$ branch so as not to be routed through $n=2$,
giving
$$3\times (-2)\times 
[z^{\lfloor \log_2  n  \rfloor - 2}] \frac{1}{1-(3z-2z^2)}.$$

Evaluation. Note that by partial fractions we have that
$$[z^q] \frac{1}{1-(3z-2z^2)} = 2^{q+1}-1$$
so that we get for case A
$$ 7 \times 2^{\lfloor \log_2  n  \rfloor} - 7
- 6 \times 2^{\lfloor \log_2  n  \rfloor-1} + 6
= (14-6) \times 2^{\lfloor \log_2  n  \rfloor-1} - 1
= 2^{\lfloor \log_2  n  \rfloor+2} - 1$$
and for case B
$$ 5 \times 2^{\lfloor \log_2  n  \rfloor} - 5
- 6 \times 2^{\lfloor \log_2  n  \rfloor-1} + 6
= (10-6) \times 2^{\lfloor \log_2  n  \rfloor-1} + 1
= 2^{\lfloor \log_2  n  \rfloor+1} + 1 $$
This produces the sequence for $n\ge 2$
$$5, 7, 9, 9, 15, 15, 17, 17, 17, 17, 31, 31, 31, 31, 33,\ldots$$
which perfectly matches $f(n).$

Observe  that we  may  say that  $f(n)\in\Theta(n)$  in certain  sense
($2^{\lfloor \log_2 n \rfloor}\in\Theta(n).$)

This MSE link shows a more sophisticated application of the trick with the generating function.
</s>