你面前排着无穷多张多米诺骨牌，想证明「它们全会倒」。你不可能一张张去推。归纳法说：你只需证明两件事——第一张会倒；以及「只要任意一张倒了，它一定会撞倒下一张」。这两件事一旦成立，无穷多张的命运就被锁死了。
归纳法的精妙，是把「验证无穷个命题」压缩成「验证一个起点 + 一条传递规则」。你从不真的走完无穷步——你只是证明了「这条链没有断点」。断不了的链，就是全倒的链。
$P(n)$ 是关于自然数 $n$ 的命题。基础步 证 $P(0)$；归纳步 假设 $P(k)$ 成立（称 归纳假设），据此推出 $P(k{+}1)$。两步齐备，则 $P(n)$ 对所有 $n$ 成立。注意归纳假设不是「偷偷假设了要证的结论」——你假设的是「某一张倒」，要证的是「它撞倒下一张」，是传递而非结论。
归纳法揭示了一件事：无穷不必用无穷的力气去对付。有限的两步论证，可以覆盖无穷个命题。更深的是，它不是一个「技巧」——皮亚诺公理里，归纳原理本身就是自然数的定义之一。换句话说，「自然数为什么能被归纳」不是一条定理，而是「我们把满足归纳的东西才叫自然数」。归纳法与自然数是同一件事的两面。它还有变体——强归纳（假设 $P(0),\dots,P(k)$ 全真）和 结构归纳（对树、表达式等递归结构施归纳），是同一精神的推广。
归纳法是计算机科学证明的主力。证明循环不变量——「每轮迭代后某性质仍成立」——就是对迭代次数施归纳，这是程序正确性证明的核心。递归算法（归并排序、快速幂）的正确性几乎都靠结构归纳。类型系统的健全性、编译器优化的保序性、分布式协议的安全性证明，底层都是归纳。可以说，凡是涉及「对一切规模都成立」的软件保证，背后都站着归纳法。
俄罗斯套娃：打开一个，里面是一个更小的、一模一样的娃娃，直到最里面那个小到打不开为止。递归就是这种结构——解决一个大问题的方法，是先解决一个更小的同类问题，一层层缩小，直到抵达一个「不用再想就知道答案」的最小情形（基例）。
如果说归纳法是「证明的向上爬」（从 $k$ 推到 $k{+}1$），递归就是「计算的向下钻」（把 $n$ 化归到 $n{-}1$）。它们是同一枚硬币的两面：归纳保证递归会终止且正确，递归则是归纳在计算世界里的化身。
一个 递推关系 用较小的项定义当前项，再加上初始条件（基例）把链锚在地面上。上式是斐波那契数列——去掉初始条件，它只是一个空悬的规则；有了 $F(0),F(1)$，整个数列就被唯一确定。递归函数就是把这个定义直接翻译成代码：函数在自己体内调用自己，靠基例停下来。
同一个递归可以有惊人不同的面孔。斐波那契的递推是最朴素的加法，可它的闭式解竟然是 $F(n)=\frac{\varphi^n-\psi^n}{\sqrt5}$，其中 $\varphi=\frac{1+\sqrt5}{2}$ 正是黄金比例——一个满是无理数、幂运算的公式，代进去每次都吐出整数。为什么一个只讲整数相加的规则，骨子里藏着黄金比例？因为递推关系对应一个特征方程 $x^2=x+1$，它的根就是 $\varphi$。递推的「增长基因」写在特征方程的根里——这是离散世界与代数、与连续增长率之间一座隐秘的桥。
分治算法（归并排序、快速排序、FFT）就是「把问题劈成两半，各自递归，再合并」，其运行时间由递推 $T(n)=2T(n/2)+O(n)$ 描述，靠主定理一眼解出 $O(n\log n)$。动态规划 本质是「有重叠子问题的递归」——上图里 $F2$ 被重复计算，记忆化（把算过的存下来）就能把指数级的重复砍成线性。语法解析、分形生成、递归神经网络、乃至函数式编程的整个范式，都建在递归之上。
你写了个程序，跑一次要 3 毫秒——这个数字几乎没用。换台机器、换个编译器，它就变了。真正决定命运的问题是：数据量翻倍时，时间怎么变？翻倍？还是翻四倍？还是原地不动？大 O 记号丢掉所有常数和低阶项，只保留「增长的形状」，因为当数据足够大时，唯有增长率是命运，常数只是噪声。
一个 $O(n)$ 的笨算法配慢机器，长远看仍会碾压 $O(n^2)$ 的巧算法配快机器——只要 $n$ 够大。大 O 量的不是「此刻多快」，而是「扩展时会不会撞墙」。
读作：当 $n$ 大过某个门槛 $n_0$ 之后，$f$ 永远被 $g$ 的某个常数倍 $c\,g(n)$ 压在下面。$c$ 吸收了所有硬件、常数因子的差异；$n_0$ 表示「我们只关心足够大的规模」。所以 $3n^2+100n+5 = O(n^2)$——低阶的 $100n$ 和常数 $5$ 在大 $n$ 面前全被淹没。大 O 是一副「只看趋势、不看细节」的眼镜。
大 O 让算法脱离机器、语言、年代，成为可以纯粹比较的数学对象。而它最震撼之处在于：不同的 O 之间不是「快一点慢一点」，而是「可行与不可行」的鸿沟。$O(n)$ 与 $O(n^2)$ 在 $n=10^6$ 时相差一百万倍；$O(n)$ 与 $O(2^n)$ 的差距则超越了宇宙原子数。这条「多项式 vs 指数」的分界线，正是理论计算机科学最深的悬案 P vs NP 的心脏——某些问题我们能验证答案，却似乎无法快速找到答案。一个记号，划开了「计算之可能」的边界。
数据库为什么建索引？把查找从 $O(n)$ 的全表扫描降到 $O(\log n)$ 的 B 树——数据越大，差距越致命。哈希表用 $O(1)$ 平均查找支撑了几乎所有系统。而当下最鲜活的例子是大模型：Transformer 的自注意力是 $O(n^2)$（每个 token 看所有 token），这正是长上下文的瓶颈——FlashAttention、线性注意力、状态空间模型 的全部动机，就是把这个 $n^2$ 降下来。大 O 不是学院概念，它每天决定着能不能把上下文从 8K 拉到 100 万。
连续概率是「量面积」，离散概率是「数数」。你把所有可能的结果列成一张清单（样本空间），如果每个结果等可能，那么一个事件的概率，就是有利结果的个数 ÷ 结果总数。掷骰子出偶数？$3/6$。从一副牌抽到红桃？$13/52$。概率在这里退化成了纯粹的组合计数——会数数，就会算概率。
正因如此，离散概率与组合数学是连体双生：算概率的难点，往往不在概率本身，而在「怎么把有利情况数清楚、又不重不漏」。
$\Omega$ 是样本空间（所有结果的集合），$A\subseteq\Omega$ 是事件，$|A|$ 是它含的结果数。等可能时，概率就是两个计数之比。期望 $\mathbb{E}[X]$ 是随机变量 $X$ 的「加权平均」——把每个取值乘以它的概率再相加，代表「长期平均而言会得到多少」。它是离散概率里最有用的一个数。
离散概率最优雅的武器是期望的线性性：$\mathbb{E}[X+Y]=\mathbb{E}[X]+\mathbb{E}[Y]$，无论 $X$ 与 $Y$ 是否独立。这看似平淡，威力却惊人——许多看上去要纠缠所有相关性的难题，一旦拆成一堆简单随机变量之和，各自求期望再相加，答案立刻浮现。比如「一副洗乱的牌，平均有多少张停在自己原来的位置」，直接算要面对复杂的相关性；用线性性，答案干净利落地等于 $1$。把不确定性拆成可以逐个数、再相加的小块——这是离散概率的核心美感。
随机化是现代算法的秘密武器：随机化快排用「随机选主元」把最坏情况压到几乎不可能；哈希 靠随机分布实现负载均衡；Bloom 过滤器 等概率数据结构，用一点点可控的错误率换取巨大的空间节省。机器学习靠随机采样（mini-batch、dropout）训练，大模型生成时的「温度」正是在对下一个 token 的离散概率分布做采样。凡是要在不确定中做决策的地方，都是离散概率在支撑。