Why can this recurrence relation be rewritten like this?

Question

I have the recurrence relation: $a(n)= a(\lfloor n/2 \rfloor)+a(\lceil n/2 \rceil)+3n+1$ with $a_1 =3$. This can be solved to have the explicit formula: $\frac{3\cdot log_2(n)\cdot n+4\cdot log_2(2)\cdot n - log_2(2)}{log_2(2)}$. I was just "playing around" with this recurrence relation in maple and found this to be its explicit formula. I then wondered for quite some time about how or why this was its explicit formula. So can anyone show me the steps to get to that result?

Answer 1

Let $n=2^m$, then $a(2^m)= a(2^{m-1})+a(2^{m-1})+3·2^m+1$

Define $b(m)=a(2^m)$, so we have $b(m)=2b(m-1)+3·2^m+1$

This is an inhomogeneous linear recurrence law. This kind of sequences have as explicit formula the sum of a general solution for the homogeneous law and a particular solution for the inhomogeneous one.

Let's try $b(m)=Ar^m$, for some $A$ and $r$, for the homogeneous:

$Ar^m=2Ar^{m-1}$ only possible if $r=2$

For the inhomogeneous, let's try $b(m)=Dm2^m+E$. Substituting in the recurrence relation we get $D=3$ and $E=-1$. So,

$b(m)=A2^m+3m2^m-1$

Now, with the condition $b(0)=3$ (because $a(2^0)=3$), we can find $A$: $3=A-1$ or $A=4$

$b(m)=4·2^m+3m2^m-1$

$a(n)=b(\log_2n)=4n+3n\log_2n-1$

as expected.