离散数学与证明方法 · 小纸条

核心机制：一阶线性递推的核心是：齐次解与特解组合，迭代展开可检查闭式；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为一阶线性递推手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：把常系数公式套到变系数递推会失效。

核心机制：递推建模与初值的核心是：递推由规模缩减关系和足够初值唯一确定序列，模型先写状态含义；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为递推建模与初值手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：只写递推不写初值通常不能唯一决定解。

核心机制：非齐次递推与待定系数的核心是：特解形式根据驱动项选择，与齐次根冲突时乘n提升；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为非齐次递推与待定系数手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：只猜一个数值序列不等于证明一般解。

核心机制：高阶常系数递推的核心是：特征多项式根决定解形，重根引入n的幂因子；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为高阶常系数递推手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：初值数量必须与阶数匹配，复根应组合成实值形式。

核心机制：Master定理与适用边界的核心是：比较n^{log_b a}与f(n)并检查正则条件，快速判断标准分治递推；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为Master定理与适用边界手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：子问题规模不等或f不满足条件时不能硬套三种情况。

核心机制：递推树与分治复杂度的核心是：递推树逐层记录子问题数与局部成本，再汇总高度和层和；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为递推树与分治复杂度手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：忽略取整、非均匀分支和边界规模会改变严格结论。

核心机制：生成函数解递推的核心是：把递推乘x^n求和转成代数方程，再由部分分式提取系数；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为生成函数解递推手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：求和下标与初值修正项最容易丢失。