# 二、證明等式（3.16）：a ^ {\log_b c} = c ^ {\log_b a}。

文心一言：


chatgpt：

我們需要證明的等式為：$a^{\log_b c} = c^{\log_b a}$。

首先，將 $\log_b c$ 看作一個(gè)變量 $x$，那么原式可表示為 $a^x = c^{\frac{\log_a b}{\log_a c}}$。

然后，我們將 $c^{\frac{\log_a b}{\log_a c}}$ 進(jìn)一步拆分，得到：

$$

\begin{aligned}

c^{\frac{\log_a b}{\log_a c}} &= c^{\log_c b} \\

?&= b

\end{aligned}

$$

最后，將上述結(jié)果代入原式中，有：

$$

\begin{aligned}

a^{\log_b c} &= a^x \\

?&= c^{\frac{\log_a b}{\log_a c}} \\

?&= b^{\log_c b} \\

?&= c^{\log_b a}

\end{aligned}

$$

因此，我們證明了等式 $a^{\log_b c} = c^{\log_b a}$ 成立。


# 三、證明等式（3.19）：\lg(n!) = \Theta(n \lg n)。并證明 n! = \omega(2 ^ n) 且 n! = o(n^n)。

文心一言：


chatgpt：

首先，我們證明等式 $\lg(n!) = \Theta(n \lg n)$。

由斯特林公式（Stirling's formula），可得：

$$

\ln n! = n \ln n - n + \mathcal{O}(\ln n)

$$

兩邊同時(shí)取以 2 為底的對(duì)數(shù)，則有：

$$

\begin{aligned}

\log_2 n! &= \frac{\ln n!}{\ln 2} \\

&= \frac{n \ln n - n + \mathcal{O}(\ln n)}{\ln 2} \\

&= n \frac{\ln n}{\ln 2} - \frac{n}{\ln 2} + \mathcal{O}\left(\frac{\ln n}{\ln 2}\right)

\end{aligned}

$$

因?yàn)?$\frac{\ln n}{\ln 2}$ 等于 $\Theta(\log n)$，所以可得：

$$

\log_2 n! = \Theta(n \log n)

$$

因此，$\lg(n!) = \Theta(n \lg n)$ 得證。

接下來(lái)，我們證明 $n! = \omega(2^n)$。根據(jù)定義，需要證明：

$$

\lim_{n\to\infty} \frac{n!}{2^n} = \infty

$$

考慮到：

$$

\begin{aligned}

\frac{(n + 1)!}{n!} &= n + 1 \\

&> 2

\end{aligned}

$$

因此，$n!$ 至少每乘以 2 次就要增長(zhǎng)一倍，即：

$$

\begin{aligned}

n! &= 1 \times 2 \times 3 \times \cdots \times n \\

&> 2 \times 2 \times 2 \times \cdots \times 2 \\

&= 2^n

\end{aligned}

$$

因此，$n! = \omega(2^n)$ 成立。

最后，我們證明 $n! = o(n^n)$。根據(jù)定義，需要證明：

$$

\lim_{n\to\infty} \frac{n!}{n^n} = 0

$$

將 $n!$ 展開(kāi)，則有：

$$

\begin{aligned}

n! &= 1 \times 2 \times 3 \times \cdots \times n \\

&< n \times n \times n \times \cdots \times n \\

&= n^n

\end{aligned}

$$

因此，$\frac{n!}{n^n} < 1$，即 $\frac{n!}{n^n} \to 0$ 當(dāng) $n \to \infty$。因此，$n! = o(n^n)$ 成立。

綜上所述，我們證明了等式 $\lg(n!) = \Theta(n \lg n)$，以及 $n! = \omega(2^n)$ 和 $n! = o(n^n)$。