Solving a recurrence relation with two recursions

Question

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?

Answer 1

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$$

Answer 2

$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\,$.