Recurrence relation practice problem that I can't figure out

Question

Thanks for taking the time to look at this problem. I'm trying to prepare for a test on Monday by doing some extra odd numbered problems from my textbook. I'm having a lot of trouble trying to solve one of these problems involving recurrence relations:

s(n) = s(n/2) + 3, where s(1) = 3 and n=2^m.
* n=2^m implies that n must be even *

This isn't a homogeneous recurrence relation, so I'll have to find the associated homogeneous relation and then solve for the remaining term using the 'best guess technique'.

Thanks a lot!

Answer 1

It looks like this sequence is only defined on terms with power-of-$2$ indices, on those indices, it's basically an arithmetic sequence, with initial term $3$ and common difference also $3$. That means $s(n)=3+3\log_2n$, again with $n=2^m$

Answer 2

Let's write the recurrence differently. Since the exponent is decreasing by $1$ on each recursive call, let's just write $s(m) = s(m-1) + 3$, with $s(0) = 3$.

So $s(1) = s(0) + 3 = 6$. We have $s(2) = s(1) + 3 = 9$. $s(3) = s(2) + 3 = 12$. Do you see the pattern? The general form is $s(n) = (log_{2}(n) + 1) * 3$.