How to prove $3^{\log_4n} = n^{\log_43}$?

Question

I got this from "4.4 The recursion-tree method for solving recurrences" in book "Introduction to Algorithms"

The recurrence that try to use recursion-tree to solve is: $T(n) = 3T(n/4) + cn^2$

Answer 1

$$\Large{3^{\log_4n}=e^{\ln3\frac{\ln n}{\ln4}}=e^{\ln n\frac{\ln 3}{\ln4}}=n^{\log_43}}$$

Answer 2

Let $\log_4n=y\implies4^y=n$

Now $n^{\log_43}=4^{y\log_43}=(4^{\log_43})^y=3^y$

as for if $\log_43=z,3=4^z=4^{\log_43}$

Alternatively,

if $3^{\log_4n}=y,\log_4y=\log_43\log_4n$

and if $n^{\log_43}=z,\log_4z=\log_4n\log_43$

$$\implies\log_4y=\log_4z\implies y=z$$

Answer 3

Take the log base 3 of both sides. You get $log_4(n) \stackrel{?}{=} log_4(3) * log_3(n)$

Then, note that $ log_3(n) *log_4(3) = log_4(3^{log_3(n)}) = log_4(n)$

Answer 4

Let, $\log_4{n}=p$, then $n=4^p$ from definition of $\log$. Now, $n^{\log_4{3}}=4^{p\log_4{3}}=(4^{log_4{3}})^p=3^p=3^{\log_4{n}}$.

Also you can do like this:

Use , $3=4^{\log_4{3}}$, then $3^{\log_4{n}}=(4^{\log_4{3}})^{\log_4{n}}=(4^{\log_4{n}})^{\log_4{3}}=n^{\log_4{3}}$

Answer 5

You have $\log_4$ here, so write both numbers as powers of $4$, and we see immediately that $$ (4^{\log_43})^{\log_4n}=(4^{\log_4n})^{\log_43} $$ Alternatively (or rather equivalently), take $\log_4$ of both numbers, and the numbers are clearly seen as equal.