Solving a recurrence relation with two recursions I have the following function $r(n)$ where $n\in Z$ defined by:
$$
r(1) = 3
$$
$$
r(2) = 15 
$$
$$
r(n) = 5 \times r(\frac{n}{2}) - 4 \times r(\frac{n}{4})
$$
I am trying to turn that into a non-recursive expression.
Change of variable ($n\rightarrow 2^m$)
$
R(m) = r(n)
$
$
R(m) = 5R(m-1) - 4R(m-2) 
$
Change of function:
$
R(m) = 5^m h(m)
$
$
\implies 5^m h(m) = 5\times5^{m-1} h(m-1) - 4\times5^{m-2}h(m-2)
$
Then dividing by $5^m$
$
\implies h(m) = h(m-1) - \frac{1}{25}h(m-2)
$ 
This is where I am stuck - how can I finish this to get a non-recursive form of this algorithm? Did I do something wrong or miss something?
 A: You have a linear difference equation, and as described in the given link, we just notice the following:
$$R(m+2)=5R(m+1)-4R(m)$$
$$R^2=5R-4\implies R_+=4,R_-=1$$
Thus,
$$R(m)=a4^m+b$$
Plug $m=0,1$ to then find $a,b$, which finally give
$$R(m)=4^{m+1}-1$$
A: 
$R(m) = 5R(m-1) - 4R(m-2)$

At this point you got a linear recurrence, which can be solved the standard way using its characteristic polynomial, as noted already. For an alternative approach, write the recurrence as:
$$
R(m)-R(m-1)=4\big(R(m-1)-R(m-2)\big)
$$
With $\,S(m)=R(m)-R(m-1)\,$ the above telescopes to:
$$
S(m)=4 \cdot S(m-1) = 4^2 \cdot S(m-2) = \cdots = 4^{m-1} \cdot S(1)
$$
Since $\,S(1) = R(1)-R(0) = r(2)-r(1)=15-3=12\,$, this gives:
$$
R(m)-R(m-1) = S(m) = 4^{m-1} \cdot 12 = 3 \cdot 4^{m}
$$
Adding the equalities up, and telescoping again:
$$\require{cancel}
R(m)-R(0) = 3\cdot\left(4^{m}+4^{m-1}+\cdots+4^2+4\right) = \cancel{3} \cdot 4 \cdot \frac{4^m-1}{\cancel{4-1}} = 4^{m+1} - 4
$$
So in the end $R(m) = R(0) +4^{m+1} - 4=r(1) +4^{m+1} - 4=3 +4^{m+1} - 4=4^{m+1}-1\,$.
