I'm currently studying recurrence relations, and we had a question where we had to solve the recurrence
$$\ T(n) = nT(n/2)^2 $$
Where $\ T(1) = 6 $
When solving, i came up with the answer
$$\ T(n) = \frac{n^{n-1} 6^n}{2^{n(log_2n - 2)+2}} $$
However, the solution that was given was $$\ T(n) = \frac{6^n4^{n-1}}{n} $$
Curious, i plotted both function on desmos, only to find that they overlap.
Why is this the case? How are these two seemingly different functions giving the same plot, and how is it that we arrive at this other answer?
I have seen a similar question asked here Solve the recurrence relation $T(n) = nT^2(n/2)$ however, what i'm more curious about is why the two graphs come out to be the same.
Apply the arithmetic rules for powers, exponents and logarithms to find for the denominator $$2^{n(\log_2n - 2)+2}=(2^{\log_2n})^n\cdot 2^{-2n}\cdot 2^2=\frac{4n^n}{4^n}$$
You can also transform the given equation to $$ 4nT(n)=\left(4\frac{n}2T\left(\frac n2\right)\right)^2=...=\left(4\frac{n}{2^k}T\left(\frac n{2^k}\right)\right)^{\large2^k} $$ so that for dyadic powers $n=2^k$ you get $$ 4nT(n)=(4T(1))^n. $$