Solve the recurrence relation $T(n)^2 = T(n/2)T(2n) - T(n)T(n/2)$ Assume $T(n)$ is positive and non-decreasing function of $n$. Find the recurrence relation:
$$T(n)^2 = T(n/2)T(2n) - T(n)T(n/2).$$
I want to solve this by giving tight $\Theta$-notation bounds in terms of $n$.
Let $S(n)=T(2n)/T(n)$ for $n>2$, then $S(n) = S(n/2) + 1.$ By Master's theorem we have $S(n) = \Theta(\log(n)).$ How to transform this into $T(n)$?
 A: First, lets rearrange the equation:
$$ T(2n) = T(n) \left ( 1 + \frac{T(n)}{T(n/2)} \right )$$
Then we substitute $n \to 2n$ to see:
$$ 
T(n) = 
T \left ( \frac{n}{2} \right ) 
\left ( 
1 + \frac{T \left ( \frac{n}{2} \right )}{T(\frac{n}{4})} 
\right )
$$
Then, putting $n = 2^k$, and setting $S(k) = T(2^k)$, we see
$$
S(k) = S(k-1) \left ( 1 + \frac{S(k-1)}{S(k-2)} \right )
$$
Finally, $S(k) \in \Theta(k!)$, since
$$k! = (k-1)! \left (1 + \frac{(k-1)!}{(k-2)!} \right )$$
Thus $T(2^k) \in \Theta(k!)$, or equivalently, $T(n) \in \Theta((\log n)!)$

Hope this helps ^_^
A: You have already made a lot of progress.  Let $S(n)=\frac{T(n)}{T(n/2)}$ for even $n$, similarly to what you defined.  If $n=2^kp$ where $p$ is odd, then
$$\frac{T(n)}{T(p)}=S\left(2^{k}p\right)S\left(2^{k-1}p\right)\cdots S(2p).$$
It can be easily seen that $S(2^lp)=l+S(2p)-1$, so
$$T(n)=T(p)\big(k+S(2p)-1\big)\big(k+S(2p)-2\big)\cdots S(2p)=T(p)\frac{\big(k+S(2p)-1\big)!}{\big(S(2p)-1\big)!}.$$
If the recursion only works for even values of $n$, then this is the only thing we can say.  That is, for each odd number $p$, $T(p)$ and $S(2p)$ must be known.  However, for a fixed $p$, we can already see that
$$T(2^kp)\in\Theta(k!).$$
But I would be cautious and not write $T(n)\in \Theta\big(\log_2(n)!\big)$, because you can define $T(p)$ and $S(2p)$ for each odd $p$ so that $T(n)\notin \Theta\big(\log_2(n)!\big)$.
Suppose now that the recursion is to be interpreted as
$$T\big(\lfloor n/2\rfloor \big)^2=T\big(\lfloor n/4\rfloor\big)T(n)-T\big(\lfloor n/2\rfloor\big)T\big(\lfloor n/4\rfloor\big)$$
for all positive integers $n\ge 4$.  We set $S(n)=\frac{T(n)}{T\big(\lfloor n/2\rfloor\big)}$ for $n\ge 2$, so $S(n)=S\big(\lfloor n/2\rfloor\big)+1$ for $n\geq 4$.  Then we can show by induction that $$S(n)=\left\{\begin{array}{ll}S\big(2^{k}\big)=k+S(2)-1&\text{if }2^k\leq n < 3\cdot 2^{k-1}\\
S\big(3\cdot 2^{k-1}\big)=k+S(3)-1&\text{if }3\cdot 2^{k-1}\leq n<2^{k+1}.\end{array}\right.$$  This means
$$T(n)=\left\{\begin{array}{ll}T(1)\frac{\big(k+S(2)-1\big)!}{\big(S(2)-1\big)!}&\text{if }2^k\leq n < 3\cdot 2^{k-1}\\
T(1)\frac{\big(k+S(3)-1\big)!}{\big(S(3)-1\big)!}&\text{if }3\cdot 2^{k-1}\leq n<2^{k+1} \end{array}\right\}\in\Theta(k!)=\Theta\big(\log_2(n)!\big).$$
A: Hint.
Calling
$$
G(n)=\frac{T(n)}{T(\frac n2)}
$$
we have
$$
G(n) = G(2n)-1
$$
giving $G(n) = C_1 + \log_2 n$ then
$$
T(n) = (C_1+ \log_2 n)T\left(\frac n 2\right)
$$
equivalent to
$$
\mathcal{T}(z) = \left( C_1 + z\right)\mathcal{T}(z-1)
$$
with $z = \log_2 n$
giving
$$
\mathcal{T}(z) = C_2 \left(C_1+2\right)_{z-1} \ \ \text{(Pochhammer symbol)}
$$
The conversion to $T(n)$ is left to the reader.
