# Logarithms equality

I'm trying to understand a "subproof" of the divisor Master Theorem (Cormen et al., Introduction to Algorithms, page 99), and in some point they state:

$$\Large a^{\log_b n} = n^{\log_b a}$$

where $a\geq 1$, $b > 1$ and $n = b^i$, for some $i$. That is, $n \in \{1, b, b^2, ...\}$

I would appreciate a simple explanation of this equality (just OK for a CS undergraduate).

• Take the log (to the base $b$) of both sides. – André Nicolas Aug 2 '16 at 21:48
• Alternatively, write out both sides using the rule that $s^t = e^{t \ln s}$, and recall that $\log_a x = \frac{\ln x}{\ln a}$. – John Hughes Aug 2 '16 at 21:51
• Black Bolt is capable of channeling all available energy into one devastating punch called his Master Blow, which renders him extremely vulnerable subsequently. – Will Jagy Aug 2 '16 at 21:53
• @WillJagy I -really- wonder what's the relation between logarithms and Marvel... – JnxF Aug 2 '16 at 22:06
• @WillJagy are you proposing we use the Master Blow to prove the Master Theorem? I feel like this is the best approach I've ever heard. Only problem is that it might leave a major singularity where the blow occurred, but it should be removable XD – Brevan Ellefsen Aug 2 '16 at 22:30

Let us start here:

$$\log_b(a)\log_b(n)=\log_b(n)\log_b(a)$$

$$b^{\left(\log_b(a)\log_b(n)=\log_b(n)\log_b(a)\right)}$$

$$b^{\log_b(a)\log_b(n)}=b^{\log_b(n)\log_b(a)}$$

$$\left(b^{\log_b(a)}\right)^{\log_b(n)}=\left(b^{\log_b(n)}\right)^{\log_b(a)}$$

Recall that $x^{\log_x(y)}=y$, so

$$a^{\log_b(n)}=n^{\log_b(a)}$$

For this particular nut, since $n =b^i$ your equality is just $$a^{\displaystyle \log_b b^i} = a^{\displaystyle i} = b^{\displaystyle \log_b a^i}$$

and so it holds. It's also true for a more general $n$, as the comments explain.

It's true for all $a,b,n>0$

\begin{align*} \large \frac{\log a}{\log b} \times \log n &= \large \frac{\log n}{\log b} \times \log a \\[5pt] \large \log_{b} a \times \log n &= \large \log_{b} n \times \log a \\[5pt] \large \log \left( n^{\log_{b} a} \right) &= \large \log \left( a^{\log_{b} n} \right) \\[5pt] \large n^{\log_{b} a} &= \large a^{\log_{b} n} \end{align*}