Σ ~ Hₙ O( )
数学之旅 · CHAPTER 14 · Part III 开篇

求和与渐近

Sums and Asymptotics

彩票的"百万大奖"现值其实只有五十几万;一摞书能悬出桌沿任意远,但要 227 本才悬出 3 本长。闭式、扰动法、几何级数、积分包围与 Big-O——算法分析的数学语言从本章开始。

⏱ 约 60 分钟🧩 9 个互动装置📖 原书第 547–596 页
14.1

年金:今天的百万 vs 每年的五万

The Value of an Annuity

彩票给你两个选择:今天拿 100 万,或未来 20 年每年拿 5 万。直觉说后者总数更多?货币有时间价值:利率 p = 8% 时,一年后的 10 元今天只值 10/(1+p) ≈ 9.26 元。n 年 m 元年金的真实价值 V 是一串几何和,用扰动法(S 与 xS 相减,中间大规模抵消)可推出闭式:

V = m·(1 − xⁿ) / (1 − x),其中 x = 1/(1+p)  无限年期:V = m(1+p)/p

代入 5 万、20 年、8%:V ≈ $530,180——"百万大奖"现值只有半百万。永不停止的版本也只有 $675,000(银行里躺着 100 万本来就每年能花 8 万到永远)。

互动 ①

🏦 年金现值计算器

n 年年金现值 V = —
永续年金 V∞ = m(1+p)/p = —
名义总额 = m·n = —
调一调 n 和 p:年数越多、利率越低,年金越接近名义总额——但 8% 利率下"百万彩票"永远追不上现款。
互动 ②

🌀 扰动法步进器:看中间项大规模抵消

选一个 x,然后一步步"扰动"S:乘 x、错位、相减——中间项成对湮灭,闭式自己掉出来。
S = ?(点"下一步"开始扰动)

14.1.2扰动法:自己发现闭式

Perturbation Method

对 S = 1 + x + x² + ⋯ + xⁿ:写出 xS = x + x² + ⋯ + xⁿ⁺¹,两式相减——中间所有项大规模抵消,只剩 S − xS = 1 − xⁿ⁺¹,解出 S = (1 − xⁿ⁺¹)/(1 − x)。求导一次还能得到 Σixⁱ 的闭式(定理 14.1.2)。下一章生成函数会再用这招。

14.2

幂和:Gauss 的配对与系数猜法

Sums of Powers

高斯小学生的传说:把 1+2+⋯+n 正写一遍反写一遍,相加得 n(n+1),所以和是 n(n+1)/2。平方和用不了这招,但可以猜它是三次多项式 an³+bn²+cn+d:n=0 给 0=d,n=1 给 1=a+b+c+d,n=2 给 5=8a+4b+2c+d,n=3 给 14=27a+9b+3c+d——解出 a=1/3, b=1/2, c=1/6, d=0,即 n³/3+n²/2+n/6,与式 14.14 的 (2n+1)(n+1)n/6 吻合。原书正体警告框(Be careful!):猜出来必须回头证明(归纳或生成函数),猜错形状就全错。

互动 ③

🧮 幂和工坊:亲手解出平方和的系数

假设 Σi² = an³ + bn² + cn + d。调 a、b、c、d(可填分数如 1/3),让 n=0…5 的预测值全部命中真值——命中即锁定原书方程组的解。

提示:真值来自直接硬算 Σi²。四个未知数只需要 n=0..3 四条方程——多出来的 n=4、5 是给你"回头证明"用的免费验证。
14.3

积分包围:给没有闭式的和找上下界

Approximating Sums
定理 14.3.2 · 积分包围

f 弱递增时:I + f(1) ≤ S ≤ I + f(n),其中 I = ∫₁ⁿ f(x)dx(把和看成矩形面积、把积分看成曲线下面积)。f 弱递减时上下界对调。

例:Σ√i 被 (2/3)(n^(3/2) − 1) + 1 与 (2/3)(n^(3/2) − 1) + √n 夹住——即 S ≈ (2/3)n^(3/2)。"和 ≈ 最大项的常数倍"是几何递减/递增和的经验法则。

互动 ④

📐 积分包围实验台:矩形与曲线夹住 S

14.4

书堆悬挑:调和数登场

Hanging Out Over the Edge

n 本书叠成一摞、每本往桌沿外探,最多能探出多远?物理:第 i 层的质心要坐在下一层的边缘上。解递推得 Bₙ = Hₙ/2——调和数 Hₙ = 1 + 1/2 + ⋯ + 1/n 的一半!调和数没有已知闭式,但积分包围给 ln(n) + 1/n ≤ Hₙ ≤ ln(n) + 1(式 14.20)。结论:书可以悬出桌沿任意远(Hₙ ~ ln n → ∞),但代价指数级——悬出 3 本书长需要 227 本。

互动 ⑤

📚 书堆悬挑模拟器:Hₙ/2 本长的野心

书 = 4 本 · 悬挑 = Hₙ/2 ≈ 1.0417 本书长(ln n ≈ 1.386)
H₄ = 25/12 > 2:四本书就能悬出一整个书长。要悬出 3 本书长?227 本起步。
14.5–7

乘积、Stirling 与渐近记号

Products · Stirling · Asymptotics

14.5乘积:取对数变求和

乘积不需要新工具——取对数就变求和:ln(n!) = Σᵢ₌₁ⁿ ln i。对它用积分包围(∫ln x dx = x ln x − x + 1),再指数回去,得 nⁿ/eⁿ⁻¹ ≤ n! ≤ nⁿ⁺¹/eⁿ⁻¹(式 14.23)。最常用的是 Stirling 公式(定理 14.5.1):

n! ~ √(2πn)·(n/e)ⁿ  (n≥10 误差 <1%,n≥100 误差 <0.1%)

π 和 e 居然同时出现在 n! 的渐近式里——谁能想到。

互动 ⑥

🎰 Stirling 近似实验台:误差被定理焊死

拖动 n:橙条是实测相对误差 |n! − 近似|/n!(对数尺度),蓝区是定理 14.5.1 的保证区间 [0, 1/(12n)]。原书 Table 14.1:n≥10 实测必进 1%,n≥100 进 0.1%。

n = 10 · n! = — · √(2πn)(n/e)ⁿ = —

14.6Double Trouble:双重求和

和的和听起来吓人,常规操作是"先算内和、换闭式,再算外和";没有现成闭式时还有一招交换求和次序。经典战例:Σₖ₌₁ⁿ Hₖ 写成三角形表格(第 k 行是 1, 1/2, …, 1/k),按列而不是按行加,立得

Σₖ₌₁ⁿ Hₖ = (n+1)Hₙ − n  (式 14.27)

这条结论并入了下面的渐近自测题。

14.7渐近记号

渐近相等 f ~ g:lim f(x)/g(x) = 1。Hₙ ~ ln n(欧拉常数 γ 与 ε(n) 都被 ~ 吸收——注意 Hₙ ~ ln n + γ 写法不对,常数被 ~ 的定义吞掉)。小 o:f=o(g) ⟺ f/g→0(幂次镇压:xᵃ=o(xᵇ) 当 a<b;log x = o(xᵉ);xᵇ=o(aˣ) 当 a>1)。Big-O:比值 limsup 有限(等价定义:存在 c 与 x₀ 使 |f|≤c·g 对 x≥x₀)。Θ:互为 Big-O。四道快判热身:

互动 ⑦

⚖️ 渐近关系快判:f ~ g 成立吗?

进度 0 / 4
⚔️

习题实战

Practice Problems, Playable

两道原书 Practice Problem 做成解题器。

互动 ⑧

🧬 习题 14.17:渐近家族判别台

原书题目:f(n) = n³。对表中每个 g(n),判四个关系是否成立(点格子切换 ✓/✗,判满 24 格再判定)。提示:算 g/f 或 f/g 的极限(或 limsup)。

互动 ⑨

🔢 习题 14.16:最小指数判敛器

原书题目:对每个 f(x),找出使 f(x) = O(xⁿ) 成立的最小非负整数 n——若不存在(指数函数碾压一切多项式)选"无"。

⚖️

终局自测

Final Check

八题,覆盖 14.1–14.7。

🥚

彩蛋与课后挑战

Easter Eggs & Problems
0.99999… = 1(原书 14.1.5,式 14.7)

0.9·Σ(1/10)ⁱ = 0.9 · 1/(1−1/10) = 1。几何级数一句顶一万句的"数学辩论终结者"。还有 1 − 1/2 + 1/4 − ⋯ = 2/3(交错级数)、1 + 2 + 4 + ⋯ + 2ⁿ⁻¹ = 2ⁿ − 1(几何递增和 ≈ 最大项的两倍)。

倒金字塔:书堆的进阶玩法(原书 14.4 末尾)

我们的"每本书只压在一本上"结论其实可以再进化:允许一本压在多本上(倒金字塔结构),n 本书能悬出 ∝ n^(1/3) 本书长——比 ln n 快得多(Maximum Overhang, [14])。所以"调和数一半"也不是极限,是单支撑结构的极限。

课后挑战(均出自原书习题)
  • 14.2 用扰动法(而非求导)推导 Σixⁱ 的闭式。
  • 闭式推导 1·2 + 2·3 + ⋯ + n(n+1) = n(n+1)(n+2)/3(用 14.1 节的扰动/换序技巧;第 2 章习题 2.17 的闭式来源)。
  • 14.10 补全弱递减情形的积分包围证明。
  • 证明 |Hₙ − ln(n) − γ| ≤ 1/n 的精细版。
本章路线图
14.1 · 年金与几何级数14.2 · 幂和与 Gauss14.3 · 积分包围近似 14.4 · 书堆悬挑与调和数14.5–7 · 乘积 · 双和 · 渐近⚔️ · 习题实战 ⚖️ · 终局自测🥚 · 彩蛋与挑战