0

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).

JnxF
  • 1,277
  • 5
    Take the log (to the base $b$) of both sides. – André Nicolas Aug 02 '16 at 21:48
  • 1
    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 02 '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 02 '16 at 21:53
  • @WillJagy I -really- wonder what's the relation between logarithms and Marvel... – JnxF Aug 02 '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 02 '16 at 22:30
  • @BrevanEllefsen that was it. Well, no, I just find the phrase Master Theorem funny. However, in this case and that of Ramanujan (about the Mellin Transform), it seems that people who came up with the name are not the people who described or proved the theorem. – Will Jagy Aug 02 '16 at 22:34

3 Answers3

2

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)}$$

Simply Beautiful Art
  • 74,685
2

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.

Zain Patel
  • 16,802
1

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*}

Ng Chung Tak
  • 18,990