先别急着算。
想象你站在这一排骨牌的前面——
你要做的事情有几件？
💡 神奇的地方：只要做到这 两件 事，不管骨牌排到第 100 张、第 100 亿张，还是无穷多张，它们全部都会倒。
必须有人（或风）动手推第一下。否则，排得再整齐的骨牌也只会永远站着。
第 k 张倒下时，一定能压到第 k+1 张。间距不能太大，也不能缺一张。
今天我们要证明的「骨牌」，不是塑料做的，而是一句一句关于整数 n 的断言 —— 一共无穷多句。
1 加到 100，9 岁高斯怎么 10 秒算完
能被判断真假的句子，和一个就够了
基底 + 归纳，征服无穷的正式武器
1+3+5+… 为什么总是平方数
黑白棋怪题：看起来对，其实全错
程序员为什么天天在用归纳法
练习方式：先自己想 30 秒 → 再点「看答案」
今日目标：能独立写出一个完整的归纳法证明
在你面前有一个空存钱罐：
每天都这样投下去，第 100 天 时，罐子里一共有多少钱？
也就是求：1 + 2 + 3 + … + 99 + 100 = ?
笔算 + 计算器，很快就能搞定。
就算计算器 1 秒加 1 次，也要算到你的曾孙的曾孙……
问题不在「会不会算」，而在「有没有更聪明的算法」。
而聪明算法的背后，正好藏着今天的主角：数学归纳法。
每一列都是 101，一共 100 个 101
101 × 100 = 10 100
但这是两份的和（我们加了两次！）
1 次加法 + 1 次乘法 + 1 次除法，完事。
🔑 妙招的核心：把「一长串加法」变成「整齐的乘法」。首尾配对，每一对和都一样。
长方形：
面积 = 11 × 10 = 110 块砖
台阶只有它的一半：
1+2+…+10 = 55 ✓
把 10 换成 n，长方形就是 (n+1) × n，于是和 = n(n+1)/2。
1. 首尾配对：1+50 = 51，一共 50 ÷ 2 = 25 对，所以 51 × 25 = 1275。
2. 1+1000 = 1001，共 1000 ÷ 2 = 500 对，1001 × 500 = 500 500。
3. 1+2+…+30 = (1+30) × 30 ÷ 2 = 31 × 15 = 465 元。
4. 提公因数 2：2+4+…+100 = 2 × (1+2+…+50) = 2 × 1275 = 2550。
从 0 加到 n 的和
这个等式里的 n 是「任意一个」整数，不是某一个具体的数。
代 n=10 → 10×11÷2 = 55
代 n=100 → 100×101÷2 = 5050
代 n=1000 → 1000×1001÷2 = 500500
❓ 但等一下 —— 我代了三个数都对，就能说它对所有整数 都成立吗？
这就是今天要解决的核心问题。答案，即将在第 3 站揭晓。
把断言里塞进一个 n，它就变成了一台「真假制造机」：
⚠️ 注意 D 和 F：它们对 很多 n 都成立（D 在 n≥1 时对，F 在 n 为偶数时对），但只要 有一个 反例，就不能说「对所有 n 成立」。
检查了 n = 0,1,2,3,…,99 全都对 ✓✓✓……
但 n = 100 时错了 ✗ —— 整句话立刻作废。
「所有天鹅都是白的」——你见过 10 万只白天鹅也没用，只要有 1 只黑天鹅，这句话就倒了。
所以做判断题时，先去找反例，是最省力的策略。
1. 假。反例 n = 0：0² = 0，不大于 0；n = 1 时 1 = 1 也不大于。（1 以后才都成立）
2. 真。n²+n = n(n+1)，是两个相邻整数相乘。相邻两数必有一个偶数，所以乘积一定是偶数。
3. 真。两边同时减 n，就是 3 > 1，永远成立。
4. 假。反例 n = 1：1 不是 3 的倍数。（n=0、3、6… 时才成立）
5. 真。2n 一定是偶数，偶数加 1 一定是奇数。
断言 G(n)
（对 0 以上的所有整数 n）
试出来几十个都对 ✓但无穷多个 n 试不完
画图能看懂 ✓但图只画得出一个具体例子
需要一把新武器 ⚔——数学归纳法
亲自动手，把第一张骨牌推倒。（如果断言是"1 以上"，那就证 P(1)）
这里的 k 是任意的 0 以上整数。也就是：只要这一张倒了，下一张一定跟着倒。
两步都完成 ⟹ P(n) 对 0 以上的所有整数 n 都成立。
🧠 注意：我们没有真的去检查每一个 n。我们只证明了「第一步」和「传递规则」，剩下的交给推理完成 —— 这就是人类能谈论「无穷」的方式。
「P(k) 不就是我要证的东西吗？先假设它成立，再推出它成立，这不等于什么都没证？」
步骤 2 证明的不是「P(k) 是真的」，而是一句条件句：
「如果 P(k) 是真的，那么 P(k+1) 也一定真。」
条件句可以独立成立，与 P(k) 真假无关。
🪜 打个比方：n 是你要爬到的那一级（目标阶梯），k 只是你此刻站的这一级（途经阶梯）。归纳步骤说的是一件与你自己在哪儿有关的事：「站在第 k 级时，一定能迈上第 k+1 级」。
把 n 全部换成 0，看左右两边是否相等：
左边
右边
左边 = 0，右边 = 0，两边相等 ⟹ G(0) 成立，基底证毕 ✓
💬 基底这一步通常最简单，只要代入算一下。但它绝对不能省 —— 没有它，「骨牌」一张都不会倒。
① 假设（记作 G(k)）
② 要证明（记作 G(k+1)）
③ 从左边出发，把①塞进去替换
这正是 ② 的右边 ⟹ 「G(k) ⇒ G(k+1)」成立，归纳证毕 ✓
标准答题模板
① 要证：断言 P(n) 对 n ≥ 0（或 n ≥ 1）的所有整数成立。
② 基底：当 n = 0 时，左边 = ___，右边 = ___，相等，故 P(0) 成立。
③ 归纳：假设 P(k) 成立（k ≥ 0），即 ___。则当 n = k+1 时，
左边 = …（用上假设）… = 右边，故 P(k+1) 成立。
④ 结论：由数学归纳法，P(n) 对所有 n ≥ 0 成立。∎
❗ 一定写清「假设 P(k) 成立」——这是条件，不是结论。
❗ 最后一行别忘「由数学归纳法」——告诉老师你用的是这把武器。
有人这样"证明"：
P(n)：n = n + 1
假设 P(k) 成立，即 k = k+1，两边各加 1 得 k+1 = k+2，正是 P(k+1)。
归纳步骤完美，可整句话是错的。因为 P(0)：0 = 1，一开始就不成立。骨牌第一张没人推。
「1+3+5 = 9，1+3+5+7 = 16……我试了 5 个都对，所以对所有 n 都对。」
举例子永远不等于证明。下一站结束你会看到一个著名反例：前 16 个数全对，第 17 个就崩了。
✅ 正确姿势：基底 + 归纳，缺一不可。基底负责「起步」，归纳负责「传递」。
① 要证：断言 P(n)：前 n 个偶数之和 = n(n+1)，对 n ≥ 1 成立。
② 基底：当 n = 1 时，左边 = ____，右边 = ____。
③ 归纳：假设 P(k) 成立，即 2+4+⋯+2k = ____。
则 n = k+1 时，左边 = 2+4+⋯+2k + ____ = ____（用假设）= ____，正是右边。
④ 结论：由数学归纳法，P(n) 对 n ≥ 1 成立。
② n=1：左边 = 2，右边 = 1×2 = 2，相等 ✓
③ 假设 2+4+⋯+2k = k(k+1)。则 n=k+1 时：
左边 = k(k+1) + 2(k+1) = (k+1)(k+2) = (k+1)((k+1)+1)，正是 P(k+1) 的右边 ✓
④ 由数学归纳法，对一切 n ≥ 1 成立。∎
验证：n=5 时左边 = 2+4+6+8+10 = 30，右边 = 5×6 = 30 ✓
1
= 1²
1+3
= 2²
1+3+5
= 3²
1+3+5+7
= 4²
1+3+5+7+9
= 5²
猜想（断言 Q(n)）
前 n 个奇数加起来，正好是 n 的平方。
🤔 五个例子都成立 —— 但这也是「只试了几个数」。要真正确认，得请出归纳法。
第 n 圈（L 形）有几块砖？
横边 n 块 + 竖边 n 块 − 拐角重复 1 块
= 2n − 1 块
拼到第 n 圈，就是一个 n × n 的大正方形，共 n² 块。
这个"镶边"动作，正好就是归纳步骤：
P(k)：k×k 正方形 → 加一圈 2(k+1)−1 块 → P(k+1)：(k+1)×(k+1)
左边 = 1
右边 = 1² = 1
相等 ⟹ Q(1) 成立 ✓
假设 1+3+⋯+(2k−1) = k²
要证 1+3+⋯+(2k−1)+(2(k+1)−1) = (k+1)²
看：k² + 2k + 1 = (k+1)² —— 这不是巧合，这是完全平方公式。数学里最漂亮的配合之一。
🔍 检验口诀：让 n=1，看是不是第一项
2n+1 从 3 开始，是「从第二个奇数起」的写法
常用换算：第 50 个奇数 = 2×50−1 = 99；第 100 个奇数 = 199。
归纳步骤里的 k 也要跟着改：
从 0 开始 → 「对任意 k ≥ 0」
从 1 开始 → 「对任意 k ≥ 1」
范围写错，常常就是隐藏的漏洞（第 5 站会看到一个真实的翻车案例）。
1. 99 = 2n−1 ⟹ n = 50，所以和 = 50² = 2500。
2. 第 10 个奇数 = 2×10−1 = 19；前 10 个之和 = 10² = 100。
3. 2×12−1 = 23 是第 12 个奇数，和 = 12² = 144。
4. 101 是第 51 个，199 是第 100 个。所以
原式 = (1+3+⋯+199) − (1+3+⋯+99) = 100² − 50² = 10000 − 2500 = 7500。
也可以直接数：一共 (199−101)÷2+1 = 50 项，平均 (101+199)÷2 = 150，50×150 = 7500。
规律：每多摆一个正方形，只新增 3 根（有一条边是和前一个共用的）。
归纳法证明：
基底 n=1：3×1+1 = 4 ✓
归纳：T(k+1) = T(k) + 3 = (3k+1) + 3 = 3(k+1)+1 ✓
📚 老师说的「找规律」，本质就是先猜出 T(n)，再用归纳法确认它永远不会出错。猜 + 证，缺一不可。
断言 T(n)
投掷 n 枚黑白棋，所有棋子的颜色一定相同。（n ≥ 1）
这个断言显然是假的。可是——
我能用它推出一份看起来毫无破绽的「证明」。
你的任务：找出错在哪一步。
证明 T(1)：只扔 1 枚棋子，颜色当然只有 1 种。✓
假设 T(k) 成立：任意 k 枚棋子颜色都相同。
现在扔了 k+1 枚，把它们分成两组：
A 组：第 1 ~ k 枚（k 枚）；B 组：第 2 ~ k+1 枚（k 枚）
由假设，A 组内部同色，B 组内部同色；
而 A、B 有重叠的棋子，颜色必须一致。
⟹ k+1 枚全同色，即 T(k+1) 成立。✓
步骤 1+2 都完成 ⟹ T(n) 对所有 n ≥ 1 成立。
k = 4 时的分法（k+1 = 5 枚）
🔎 每一步都「说得通」，结论却荒唐。错的不是算术，而是某个隐含的条件。
k = 4（成立）
重叠 3 枚 ⟹ A、B 被"钉"在一起 ⟹ 结论成立。
k = 1（断裂）
重叠 0 枚 ⟹ 左边白、右边黑，谁也没矛盾 ⟹ 归纳断了。
所以「T(k) ⇒ T(k+1)」并不是对所有 k ≥ 1 都成立，它只在 k ≥ 2 时成立。
从 k=1 到 k=2 这一步跨不过去，整条链子在第一环就断了。
画 k=4、k=5 都很舒服，偏偏 k=1、k=0 画不出来、也不好画 —— 而漏洞常常就藏在最小的那个数上。
黑白棋的伪证悄悄用了一句「两组有重叠」，这句只在 k ≥ 2 时才真。用之前，先问：它对任意 k 都成立吗？
「n ≥ 1 成立」的断言，归纳步骤就要对 任意 k ≥ 1 成立。黑白棋的链条要从 k=1 传到 k=2，恰恰传不过去。
n = 0,1,2,…,15 对应前 16 个数（都是质数）；最后一个是 n = 16。
1. 256 + 16 + 17 = 289 = 17 × 17，不是质数。反例找到了，断言作废。
2. 不能。举多少个例子都只是「验证」，不是「证明」。整整 16 个对的例子，抵不过 1 个反例；而要想证明无穷多个 n，只能靠归纳法。
3. 违反了第 ② 条和第 ③ 条：它在 k=1 时偷偷用了「两组有重叠」，也就是归纳步骤并没有对所有 k ≥ 1 成立。
💡 循环变量 k 就是「骨牌的第几号」。基底把 k 归零、推倒第一张；循环体每次让它前进一格。
循环不变式 M(k)
程序执行到循环开头时，s 永远等于数组前 k 个元素之和。
也就是：s = a[0] + a[1] + ⋯ + a[k−1]
「不变式」就是归纳法里的那句断言 P(n)。
只要证明它在循环里一直保持，就等于证明了函数是对的。
写循环前先问自己一句：「这个循环的不变式是什么？」—— 能问出这句话，你就已经比大多数初学者少踩坑了。
循环做了两件事：达到目的（s 变成总和）、适时结束（k 追到 size）。
不变式管第一件，k 递增管第二件。
1. k=1,f=1；k=2,f=2；k=3,f=6；k=4,f=24 ⟹ 4! = 24 ✓
2. M(k)：f = 1 × 2 × ⋯ × k = k!
3. 基底：f=1（此时 k=0，0! = 1）。
归纳：f = f * k —— 若 f 原是 (k−1)!，乘上 k 就变成 k!，即 M(k−1) ⇒ M(k)。
结束时 k = n，M(n) 成立，所以 return 的 f 就是 n! ✓
阶梯拼长方形 n(n+1)/2；L 形镶边拼正方形 n²。
图能帮你猜结论，但不能代替证。
基底对、归纳看着也对，但 k=1 时「两组有重叠」是假的。
边界情况要单独检查。
写循环前先说出「不变式」，就等于给程序写了一份归纳法证明。
基底：把第一张推倒
P(0) 或 P(1)
归纳：P(k) ⇒ P(k+1)
对任意 k 都要成立
结论：由数学归纳法
对所有 n 成立 ∎
考前速查 · 四个高频失误
用数学归纳法证明：1 + 2 + 4 + 8 + ⋯ + 2n = 2n+1 − 1（对 n ≥ 0）。
提示：从 k 到 k+1，只是多了一项 2k+1。
有人"证明"：1 + 3 + ⋯ + (2n−1) = n² + 1。
他的归纳步骤：假设成立，则两边同加 2k+1 得 k²+1+2k+1 = (k+1)²+1 —— 完全正确。
那么，这个证明错在哪里？
题 1. ① 基底 n=0：左边 = 1，右边 = 2¹−1 = 1 ✓
② 归纳：假设 1+2+⋯+2k = 2k+1−1，则
1+2+⋯+2k+2k+1 = 2k+1−1+2k+1 = 2·2k+1−1 = 2k+2−1，正是 P(k+1) ✓
③ 由数学归纳法，对一切 n ≥ 0 成立。∎
题 2. 错在基底不成立。n=1 时左边 = 1，右边 = 1²+1 = 2，不相等。
归纳步骤再漂亮也没用 —— 第一张骨牌没倒，后面永远不会倒。（这正是「翻车 A」）
每一格里的麦粒数，就是"上一格 × 2"：
第 64 格 = 263 粒 ≈ 92 亿亿粒。
全部加起来 = 264 − 1 ≈ 1844 亿亿粒，按今天的产量要种几千年。国王当然付不起。
而"1+2+4+⋯+2n = 2n+1−1"，正是你刚才在终极挑战里亲手证过的那条式子。