Figuring out the formula of a recurrence relation

Question

I've got a recurrence relation which I'm stuck on figuring out the formula for:

The relation is: $T(n) = 2 T(n/4) + 1$ where $T(1) = 1$

So for my tests, I did:

$T(4) = 2 T(4/4) + 1 = 2 T(1) + 1 = 2\times1+1 = 3$

$T(16) = 2 T(16/4) + 1 = 2 T(4) + 1 = 2\times (2\times1+1) +1 = 7$

$T(64) = 2 T (64/4) + 1 = 2 T(16) + 1 = 2\times ( 2\times (2\times1+1) +1 )+1 = 15$

So I've noticed that by writing out all the multiplications, the number of $2$'s and number of $1$'s seems to be equal to the power of $4$, i.e. at $T(64)$, equivalent to $4^3$ , there are $3$ lots of $2$'s and $1$'s in the multiplication (not including the $*1$ which doesn't change the answer anyway) so I thought that the formula may then be:

$T(4^n ) = 2n + 1n$

But when I tried it out it didn't seem to work, I've also noticed the actual answers go up by the answer to the previous relation $ + 4* $the power of the previous $n$, e.g. at:

$T(16)$, the answer is $7$, answer to the previous is $3$, power of the previous is $1$ $(4^1 ) 3 + 4x1 = 7$

$T(64)$, the answer is $15$, answer to the previous is $7$, power of the previous is $2$ $(4^2 ) 7 + 4*2 = 15$

Answer 1

It should be $T(4^n ) = 2^{n+1} -1$. We have that $T(1)=T(4^0)=2^1-1=1$ and the recurrence holds: $$T(4^{n+1} )=2T(4^n )+1=2(2^{n+1} -1)+1=2^{n+2}-2+1=2^{n+2}-1.$$ More generally, if $T(n)=mT(n/r)+q$ with $m\not=1$ then $T(r^n)=Am^n+B$: $$Am^{n+1}+B=T(r^{n+1})=mT(r^n)+q=m(Am^n+B)+q\implies B=q/(1-m)$$ and $A=T(1)-B$.

Answer 2

We will develop the recurrence:

$T(n) = 2T(n/4) + 1$

$T(4n) = 2T(n) + 1$

$T(16n) = 2T(4n) + 1$ $\to T(16n) = 2[2t(n)+1] + 1 = 4T(n) + 2 + 1$

$T(64n) = 2T(16n) + 1$ $\to T(64n) = 2[4t(n)+2 + 1] + 1 = 8T(n) + 4 + 2 + 1$

$...$

$T(4^pn) = 2T(4^{p-1}n) + 1$ $\to T(4^pn) = 2^pT(n) + \sum_{i=0}^p 2^i$

$\to T(4^pn) = 2^pT(n) + 2^p - 1$

but it was given that $T(1) = 1$ so:

$\to T(4^p) = 2^p*1 + 2^p - 1$

$\to T(4^p) = 2^{p+1} - 1$ (I)

doing: $z = 4^p$ we have to:

$2p = log_2 z$ $\to p = \frac{1}{2}log_2 z $

replacing in (I) have to:

$T(z) = 2^{\frac{1}{2}log_2 z + 1} - 1$

$T(z) = 2*2^{\frac{1}{2}log_2 z} - 1$

$T(z) = 2\sqrt{z} - 1$

since z is a generic variable, we finally return to:

$T(n) = 2\sqrt{n} - 1$

I hope this may have helped.