<s>[INST] Figuring out the formula of a recurrence relation 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$
 [/INST] 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.
</s>