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

chatgpt：

\begin{aligned}
c^{\frac{\log_a b}{\log_a c}} &= c^{\log_c b} \
&= b
\end{aligned}

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

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

chatgpt：

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

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

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

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

\begin{aligned}
\frac{(n + 1)!}{n!} &= n + 1 \
&> 2
\end{aligned}

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

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

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

(=￣ω￣=)··· 暂无内容！

337

14

27

12