note-math

sequence-real_(tag) 实数列 := $ℕ \to ℝ$ . 通常记为 $𝑎_{𝑛}$ . 根据情况, 设置从 $0$ 开始或从 $1$ 开始

limit-sequence-real_(tag) 数列 $𝑎_{𝑛}$ 极限

lim_{𝑛 \to \infty} 𝑎_{𝑛} = 𝑎 ≔ \forall 𝜀 > 0, \exists 𝑁 \in ℕ, \forall 𝑛 \in ℕ, | 𝑎_{𝑛} - 𝑎 | < 𝜀

极限的运算

$lim_{𝑛 \to \infty} (𝑎_{𝑛} + 𝑏_{𝑛}) = lim_{𝑛 \to \infty} 𝑎_{𝑛} + lim_{𝑛 \to \infty} 𝑏_{𝑛}$
$lim_{𝑛 \to \infty} 𝑎_{𝑛} \cdot 𝑏_{𝑛} = lim_{𝑛 \to \infty} 𝑎_{𝑛} \cdot lim_{𝑛 \to \infty} 𝑏_{𝑛}$

rational-dense-in-real_(tag) $ℚ$ 在 $ℝ$ 的稠密性. $\forall 𝑥, 𝑦 \in ℝ, \exists \frac{𝑚}{𝑛} \in ℚ, 𝑥 < \frac{𝑚}{𝑛} < 𝑦$

Proof

$𝑥 < 𝑦$ #link(<order-real>)[等价于]

$\begin{matrix} ℚ_{< 𝑥} ⊊ ℚ_{< 𝑦} \\ ℚ_{> 𝑥} ⊋ ℚ_{> 𝑦} \end{matrix}$

精确到最多差一点之下, 有

$\begin{matrix} ℚ & \approx & ℚ_{< 𝑥} ⊔ ℚ_{> 𝑥} \\ \approx & ℚ_{< 𝑦} ⊔ ℚ_{> 𝑦} \end{matrix}$

so $ℚ_{> 𝑥} \cap ℚ_{< 𝑦} \neq \emptyset$

==> $\forall 𝜀 > 0, \exists \frac{𝑚}{𝑛} \in ℚ, 0 < \frac{𝑚}{𝑛} < 𝜀$

==>

$lim_{𝑛 \to \infty} \frac{𝑚}{𝑛} = 0$
$\forall 𝜀 > 0, \forall 𝑚 \in ℕ, \exists 𝑛 \in ℕ, 𝑛 𝜀 > 𝑚$ or $lim_{𝑛 \to \infty} 𝑛 𝜀 = \infty$

$𝑎 > 1 ⟹ lim_{𝑛 \to \infty} 𝑎^{𝑛} = \infty$

Proof $𝑥 > 0 ⟹ {(1 + 𝑥)}^{𝑛} = 1 + 𝑛 𝑥 + \dots > 1 + 𝑛 𝑥$ and $lim_{𝑛 \to \infty} 𝑛 𝑥 = \infty$

==> $0 < 𝑎 < 1 ⟹ lim_{𝑛 \to \infty} 𝑎^{𝑛} = 0$

geometric-series_(tag) 几何级数 $𝑥_{𝑛} = 1 + 𝑎 + 𝑎^{2} + \dots + 𝑎^{𝑛}$ . $0 < 𝑎 < 1 ⟹ lim_{𝑛 \to \infty} 𝑥_{𝑛} = \frac{1}{1 - 𝑎}$

Proof $(1 - 𝑎) (1 + 𝑎 + 𝑎^{2} + \dots + 𝑎^{𝑛}) = 1 - 𝑎^{𝑛 + 1}$ , $𝑥_{𝑛} = \frac{1 - 𝑎^{𝑛 + 1}}{1 - 𝑎}$

geometric-series-test_(tag) 几何级数收敛判别. let $𝑎_{𝑛} > 0$ . $\frac{𝑎_{𝑛 + 1}}{𝑎_{𝑛}} < 𝑞 < 1 ⟹ lim_{𝑛 \to \infty} 𝑎_{𝑛} = 0$

Proof $𝑎_{𝑛} = \frac{𝑎_{𝑛}}{𝑎_{𝑛 - 1}} \dots \frac{𝑎_{0}}{𝑎_{1}} 𝑎_{0} \dots < 𝑞^{𝑛} 𝑎_{0}$

exponential-vs-power_(tag) 指数增长快于幂. $𝑎 > 1, 𝑝 \in ℕ ⟹ lim_{𝑛 \to \infty} \frac{𝑛^{𝑝}}{𝑎^{𝑛}} = 0$

Proof define $𝑏_{𝑛} = \frac{𝑛^{𝑝}}{𝑎_{𝑛}}$

use 几何级数收敛判别 $\frac{𝑏_{𝑛 + 1}}{𝑏_{𝑛}} = {(\frac{𝑛 + 1}{𝑛})}^{𝑝} \frac{1}{𝑎} \underset{𝑛 \to \infty}{⟶} \frac{1}{𝑎} < 1$

exponential-root-of-power-function_(tag) $lim_{𝑛 \to \infty} 𝑛^{\frac{1}{𝑛}} = 1$

Proof

\begin{matrix} \forall 𝑎 > 1, lim_{𝑛 \to \infty} \frac{𝑛}{𝑎^{𝑛}} = 0 \\ \exists 𝑁 \in ℕ, \forall 𝑛 > 𝑁, 𝑛 < 𝑎^{𝑛} \\ 1 \leq 𝑛^{\frac{1}{𝑛}} < 𝑎 \end{matrix}

==> $𝑎 > 0 ⟹ lim_{𝑛 \to \infty} 𝑎^{\frac{1}{𝑛}} = 1$

Proof

$𝑎 > 1$ 时 by $lim_{𝑛 \to \infty} 𝑎^{\frac{1}{𝑛}} < lim_{𝑛 \to \infty} 𝑛^{\frac{1}{𝑛}}$

$𝑎 < 1$ 时用 $\frac{1}{𝑎} > 1$

factorial-vs-exponential_(tag) 阶乘增长快于指数. $𝑎 \in ℝ ⟹ lim_{𝑛 \to \infty} \frac{𝑎^{𝑛}}{𝑛!} = 0$

Proof define $𝑏_{𝑛} = \frac{𝑎^{𝑛}}{𝑛!}$ . use 几何级数收敛判别 $\frac{𝑏_{𝑛 + 1}}{𝑏_{𝑛}} = \frac{𝑎}{𝑛} \to 0 < 1$

$𝑛!$ 对应 ${1, \dots, 𝑛}$ 自双射数量, $𝑛^{𝑛}$ 对应 ${1, \dots, 𝑛}$ 自映射数量. $𝑛^{𝑛^{𝑛}}$ 等类似

iterated-power-vs-factorial_(tag) $lim_{𝑛 \to \infty} \frac{𝑛!}{𝑛^{𝑛}} = 0$

Proof define $𝑏_{𝑛} = \dots$ . use 几何级数收敛判别 $\frac{𝑏_{𝑛 + 1}}{𝑏_{𝑛}} = {(\frac{𝑛}{𝑛 + 1})}^{𝑛} \to \frac{1}{𝑒} < 1$

增长速度比较, 实数版本

$𝑎 > 1, 𝑝 \in ℝ_{> 0} ⟹ lim_{𝑥 \to + \infty} \frac{𝑥^{𝑝}}{𝑎^{𝑥}} = 0$
$𝑎 \in ℝ ⟹ lim_{𝑥 \to + \infty} \frac{𝑎^{𝑥}}{𝑥!} = 0$ with $𝑥! = Γ (𝑥 + 1)$
$lim_{𝑥 \to + \infty} \frac{𝑥!}{𝑥^{𝑥}} = 0$

mean-inequality_(tag) 均值不等式 alias AM-GM-inequality_(tag)

\prod_{𝑖 = 1 . . 𝑛} 𝑎_{𝑖} \leq {(\frac{1}{𝑛} \sum_{𝑖 = 1 . . 𝑛} 𝑎_{𝑖})}^{𝑛}

$\leq$ 取得 $=$ <==> $𝑎_{1} = \dots = 𝑎_{𝑛} = \frac{1}{𝑛} \sum_{𝑖 = 1 . . 𝑛} 𝑎_{𝑖}$

无量纲

Proof

<==> $\prod_{𝑖 = 1 . . 𝑛} {(𝑎_{𝑖})}^{\frac{1}{𝑛}} \leq \frac{1}{𝑛} \sum_{𝑖 = 1 . . 𝑛} 𝑎_{𝑖}$

<==> $\prod_{𝑖 = 1 . . 𝑛} 𝑎_{𝑖} \leq \frac{1}{𝑛} \sum_{𝑖 = 1 . . 𝑛} {(𝑎_{𝑖})}^{𝑛}$

用微分方法计算最值. 考虑函数

(𝑎_{1}) + \dots + {(𝑎_{𝑛})}^{𝑛} - 𝑛 𝑎_{1} \dots 𝑎_{𝑛}

一阶微分

\partial_{𝑖} = 𝑛 (𝑎_{𝑖}^{𝑛 - 1} - 𝑎_{1} \dots 𝑎_{𝑛} ∖ 𝑎_{𝑖})

一阶微分等于零, 解方程得到

\partial_{1} = \dots = \partial_{𝑛} = 0 ⟹ 𝑎_{1} = \dots = 𝑎_{𝑛}

二阶微分

\begin{matrix} \partial_{𝑖} \partial_{𝑖} & = & 𝑛 (𝑛 - 1) 𝑎_{𝑖}^{𝑛 - 2} \\ \partial_{𝑖} \partial_{𝑗} & = & - 𝑛 𝑎_{1} \dots 𝑎_{𝑛} ∖ 𝑎_{𝑖} 𝑎_{𝑗} \end{matrix}

判断二次型 $\partial_{𝑖} \partial_{𝑗}$ 的正定性

$𝑛$ 乘法因子可以提取出来

都是 $𝑎_{1}, \dots, 𝑎_{𝑛}$ 的 $𝑛 - 2$ 阶项多项式, 且一阶微分零使得 $𝑎_{1} = \dots = 𝑎_{𝑛}$ 所以对于判断正定性来说只需考虑 $𝑎_{1} = \dots = 𝑎_{𝑛} = 1$ , 二次型

(\begin{matrix} \partial_{1} \partial_{1} & \dots & \partial_{1} \partial_{𝑛} \\ ⋮ & ⋱ & ⋮ \\ \partial_{𝑛} \partial_{1} & \dots & \partial_{𝑛} \partial_{𝑛} \end{matrix}) = (\begin{matrix} 𝑛 - 1 & - 1 & \dots & - 1 \\ - 1 & 𝑛 - 1 & \dots & - 1 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ - 1 & - 1 & \dots & 𝑛 - 1 \end{matrix})

\begin{matrix} {(\begin{matrix} 𝑏_{1} \\ ⋮ \\ 𝑏_{𝑛} \end{matrix})}^{⊺} (\begin{matrix} 𝑛 - 1 & - 1 & \dots & - 1 \\ - 1 & 𝑛 - 1 & \dots & - 1 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ - 1 & - 1 & \dots & 𝑛 - 1 \end{matrix}) (\begin{matrix} 𝑏_{1} \\ ⋮ \\ 𝑏_{𝑛} \end{matrix}) & = & (𝑛 - 1) (𝑏_{1}^{2} + \dots + 𝑏_{𝑛}^{2}) - 2 \sum_{𝑖 < 𝑗} 𝑏_{𝑖} 𝑏_{𝑗} \\ = & \sum_{𝑖 < 𝑗} (𝑏_{𝑖}^{2} + 𝑏_{𝑗}^{2}) - 2 \sum_{𝑖 < 𝑗} 𝑏_{𝑖} 𝑏_{𝑗} \\ = & \sum_{𝑖 < 𝑗} {(𝑏_{𝑖} - 𝑏_{𝑗})}^{2} \end{matrix}

所以 $𝑎_{1} = \dots = 𝑎_{𝑛}$ 处一阶微分零 and 二阶微分正定, 函数在附近不会变小, 所以那里是最小值, 且是 $0$

best-multiplication-decomposition_(tag) 最优乘法分解

forall $𝑛$ 固定 $𝑎 = \sum_{𝑖 = 1 . . 𝑛} 𝑎_{𝑖} \in ℝ$

question: which $𝑛$ 使得 $\prod_{𝑖 = 1 . . 𝑛} 𝑎_{𝑖}$ 取最大?

对每个 $𝑛 \in ℕ$ , 根据均值不等式, 应该用加法等分 $\frac{𝑎}{𝑛}$ 取得 $\prod_{𝑖 = 1 . . 𝑛} 𝑎_{𝑖}$ 最大

等分次数 $𝑛$ 取什么时, ${(\frac{𝑎}{𝑛})}^{𝑛}$ 有最大值?

$𝑔 : 𝑛 ⇝ \frac{{(𝑛 + 1)}^{𝑛 + 1}}{𝑛^{𝑛}}$ 单调递增

Proof $\frac{𝑔 (𝑛 + 1)}{𝑔 (𝑛)} > 1$

函数 $𝑓 : 𝑛 ⇝ {(\frac{𝑎}{𝑛})}^{𝑛}$

在 $𝑛 \in ℕ : \frac{{(𝑛 + 1)}^{𝑛 + 1}}{𝑛^{𝑛}} \leq 𝑎$ 时递增
在 $𝑛 \in ℕ : \frac{{(𝑛 + 1)}^{𝑛 + 1}}{𝑛^{𝑛}} \geq 𝑎$ 时递减

所以 ${(\frac{𝑎}{𝑛})}^{𝑛}$ 在 $𝑛 : \frac{{(𝑛 + 1)}^{𝑛 + 1}}{𝑛^{𝑛}} = 𝑎$ 附近取最大

Proof of $𝑓$ 单调性质

\begin{matrix} \frac{𝑓 (𝑛 + 1)}{𝑓 (𝑛)} = 𝑎 \cdot \frac{{(𝑛 + 1)}^{𝑛 + 1}}{𝑛^{𝑛}} \\ 𝑓 (𝑛 + 1) \geq 𝑓 (𝑛) ⟺ \frac{𝑓 (𝑛 + 1)}{𝑓 (𝑛)} \geq 1 ⟺ 𝑎 \geq \frac{{(𝑛 + 1)}^{𝑛 + 1}}{𝑛^{𝑛}} \end{matrix}

Example $𝑔 (𝑛) \geq 𝑔 (1) = 4$ . 所以 $𝑎 \leq 4$ 时, $1$ 等分是最佳

$\frac{{(𝑛 + 1)}^{𝑛 + 1}}{𝑛^{𝑛}} \sim 𝑒 \cdot (𝑛 + 1)$ i.e. $lim_{𝑛 \to \infty} \frac{\frac{{(𝑛 + 1)}^{𝑛 + 1}}{𝑛^{𝑛}}}{𝑛 + 1} = lim_{𝑛 \to \infty} {(\frac{𝑛 + 1}{𝑛})}^{𝑛} = 𝑒$

natural-constant_(tag) 自然常数 $𝑒$

𝑒 = lim_{𝑛 \to \infty} {(\frac{𝑛 + 1}{𝑛})}^{𝑛} = \sum_{𝑛 = 0}^{\infty} \frac{1}{𝑛!}

Proof

二项式展开

{(1 + \frac{1}{𝑛})}^{𝑛} = 1 + (\binom{𝑛}{1}) \frac{1}{𝑛} + (\binom{𝑛}{2}) \frac{1}{𝑛^{2}} + \dots + (\binom{𝑛}{𝑛}) \frac{1}{𝑛^{𝑛}}

固定 $𝑘$ 时, 有

lim_{𝑛 \to \infty} (\binom{𝑛}{𝑘}) \frac{1}{𝑛^{𝑘}} = lim_{𝑛 \to \infty} \frac{1}{𝑘!} \frac{𝑛 \cdot (𝑛 - 1) \dots (𝑛 - 𝑘 + 1)}{𝑛^{𝑘}} = \frac{1}{𝑘!}

对每个 $𝑘 \in ℕ$

\begin{matrix} lim_{𝑛 \to \infty} {(1 + \frac{1}{𝑛})}^{𝑛} & \geq & \frac{1}{0!} + \frac{1}{1!} + \dots + \frac{1}{𝑘!} \\ lim_{𝑛 \to \infty} {(1 + \frac{1}{𝑛})}^{𝑛} & \geq & lim_{𝑘 \to \infty} \frac{1}{0!} + \frac{1}{1!} + \dots + \frac{1}{𝑘!} \end{matrix}

also

{(1 + \frac{1}{𝑛})}^{𝑛} < \frac{1}{0!} + \frac{1}{1!} + \dots + \frac{1}{𝑛!}

by $(\binom{𝑛}{𝑘}) \frac{1}{𝑛^{𝑘}} = \frac{1}{𝑘!} \frac{𝑛 \cdot (𝑛 - 1) \dots (𝑛 - 𝑘 + 1)}{𝑛^{𝑘}} < \frac{1}{𝑘!}$

所以 $lim_{𝑛 \to \infty} {(1 + \frac{1}{𝑛})}^{𝑛} = lim_{𝑛 \to \infty} \frac{1}{0!} + \frac{1}{1!} + \dots + \frac{1}{𝑛!} = \sum_{𝑛 = 0}^{\infty} \frac{1}{𝑛!}$

$\sum_{𝑛 = 0}^{\infty} \frac{1}{𝑛!}$ 收敛. $𝑎 > 1, lim_{𝑛 \to \infty} \frac{𝑎^{𝑛}}{𝑛!} = 0$ ==> 在尾部 $\frac{1}{𝑛!} < \frac{1}{𝑎^{𝑛}}$ 几何级数控制

iterated-power-vs-factorial-more_(tag) 阶乘与叠幂的增长速度比较 $𝑒^{𝑛} \sim \frac{𝑛^{𝑛}}{𝑛!}$ or $𝑒 = lim_{𝑛 \to \infty} \frac{𝑛}{{(𝑛!)}^{\frac{1}{𝑛}}}$

so ${𝑛!}^{\frac{1}{𝑛}} \sim \frac{1}{𝑒} \cdot 𝑛$ , so $lim_{𝑛 \to \infty} {𝑛!}^{\frac{1}{𝑛}} = \infty$

Proof of $𝑒 = lim_{𝑛 \to \infty} \frac{𝑛}{{(𝑛!)}^{\frac{1}{𝑛}}}$

def $𝑓 (𝑛) = \frac{𝑛^{𝑛}}{𝑛!}$

$\begin{matrix} \frac{𝑓 (𝑛 + 1)}{𝑓 (𝑛)} = {(\frac{𝑛 + 1}{𝑛})}^{𝑛} \to 𝑒 \\ 𝑓 (𝑛) = \frac{𝑓 (𝑛)}{𝑓 (𝑛 - 1)} \dots \frac{𝑓 (2)}{𝑓 (1)} 𝑓 (1) \\ 𝑓 (1) = 1 \end{matrix}$

def $𝑎_{𝑛} = \frac{𝑓 (𝑛 + 1)}{𝑓 (𝑛)} = {(\frac{𝑛 + 1}{𝑛})}^{𝑛}$

$\frac{𝑛}{{𝑛!}^{\frac{1}{𝑛}}} = {(𝑎_{1} \dots 𝑎_{𝑛 - 1})}^{\frac{1}{𝑛}} = {(𝑎_{1} \dots 𝑎_{𝑛})}^{\frac{1}{𝑛}} \cdot \frac{1}{{(𝑎_{𝑛})}^{\frac{1}{𝑛}}} = {(𝑎_{1} \dots 𝑎_{𝑛})}^{\frac{1}{𝑛}} \frac{𝑛}{𝑛 + 1}$

sequence-multiplication-mean-limit_(tag) 乘法平均不改变极限

$(𝑎_{𝑛} > 0) \land (lim_{𝑛 \to \infty} 𝑎_{𝑛} = 𝑎) ⟹ lim_{𝑛 \to \infty} {(𝑎_{1} \dots 𝑎_{𝑛})}^{\frac{1}{𝑛}} = 𝑎$

Proof

$\forall 𝜀 \geq 0, \exists 𝑁 \in ℕ, \forall 𝑛 > 𝑁, 𝑎 - 𝜀 \leq 𝑎_{𝑛} \leq 𝑎 + 𝜀$

$𝑎_{1} \dots 𝑎_{𝑛} = (𝑎_{1} \dots 𝑎_{𝑁}) \cdot (𝑎_{𝑁 + 1} \dots 𝑎_{𝑛})$

${(𝑎_{1} \dots 𝑎_{𝑁})}^{\frac{1}{𝑛}} {(𝑎 - 𝜀)}^{1 - \frac{𝑁}{𝑛}} \leq {(𝑎_{1} \dots 𝑎_{𝑛})}^{\frac{1}{𝑛}} \leq {(𝑎_{1} \dots 𝑎_{𝑁})}^{\frac{1}{𝑛}} {(𝑎 + 𝜀)}^{1 - \frac{𝑁}{𝑛}}$

$lim_{𝑛 \to \infty} {(𝑎_{1} \dots 𝑎_{𝑁})}^{\frac{1}{𝑛}} = 1$

$lim_{𝑛 \to \infty} 1 - \frac{𝑁}{𝑛} = 1$

sequence-addition-mean-limit_(tag) 加法平均 $lim_{𝑛 \to \infty} 𝑎_{𝑛} = 𝑎 ⟹ lim_{𝑛 \to \infty} \frac{1}{𝑛} (𝑎_{1} + \dots + 𝑎_{𝑛}) = 𝑎$

harmonic-series-diverge_(tag) 调和级数发散 $lim_{𝑛 \to \infty} 1 + \frac{1}{2} + \dots + \frac{1}{𝑛} = + \infty$

Proof $𝑎_{𝑛} = 1 + \frac{1}{2} + \dots + \frac{1}{𝑛}$ 发散 by 它不是 #link(<Cauchy-completeness-real>)[limit-distance-vanish]. e.g.

\forall 𝑛 \in ℕ, 𝑎_{2 𝑛} - 𝑎_{𝑛} = \frac{1}{𝑛 + 1} + \dots + \frac{1}{2 𝑛} \geq 𝑛 \cdot \frac{1}{2 𝑛} = \frac{1}{2}

Euler-constant_(tag) $lim_{𝑛 \to \infty} 1 + \frac{1}{2} + \dots + \frac{1}{𝑛} - log 𝑛 = 𝛾$ 收敛 as 加法渐进. $lim_{𝑛 \to \infty} \frac{exp (1 + \frac{1}{2} + \dots + \frac{1}{𝑛})}{𝑛} = 𝑒^{𝛾}$ as 乘法渐进

Proof

let $𝑎_{𝑛} = 1 + \frac{1}{2} + \dots + \frac{1}{𝑛} - log 𝑛$

$log 𝑛 = log \frac{𝑛}{𝑛 - 1} \dots \frac{2}{1} \cdot 1 = log (\frac{𝑛}{𝑛 - 1}) + \dots + log (\frac{2}{1}) + log (1)$

积分估计

\frac{1}{𝑛} < \int_{𝑛 - 1}^{𝑛} \frac{1}{𝑥} = log (\frac{𝑛}{𝑛 - 1}) < \frac{1}{𝑛 - 1}

$𝑎_{𝑛}$ 有界

\begin{matrix} \frac{1}{2} + \dots + \frac{1}{𝑛} & > & log (𝑛) & > & 1 + \dots + \frac{1}{𝑛 - 1} \\ - (\frac{1}{2} + \dots + \frac{1}{𝑛}) & > & - log 𝑛 & > & - (1 + \dots + \frac{1}{𝑛 - 1}) \\ 1 & > & 1 + \frac{1}{2} + \dots + \frac{1}{𝑛} - log 𝑛 & > & \frac{1}{𝑛} \end{matrix}

$𝑎_{𝑛}$ 单调减

\begin{matrix} 𝑎_{𝑛 + 1} - 𝑎_{𝑛} & = & \frac{1}{𝑛 + 1} - log (\frac{𝑛 + 1}{𝑛}) \\ < & \frac{1}{𝑛 + 1} - \frac{1}{𝑛 + 1} \\ = & 0 \end{matrix}