第一章基础方法论

· · 个人记录

递归式求解方法

  1. 研究小的情形： 用比较简单的样例模拟操作过程或计算过程
  2. 命名： 引入记号（字母）表示，加以严谨定义
  3. 求解： 如果不能直接得出答案，可以从夹逼等角度考虑

数学归纳法

用处：证明某个命题对无穷多个整数都成立

  1. 基础： 对于某个 n_0 ，命题成立
  2. 归纳： 假设对于某个 n，对所有它依赖的 n_x 命题都成立，且根据计算可知对这个 n 也成立

如果 n 与 n_x 可以在整数域上递推到整个定义域，那么对于定义域里面的任何一个 n ，命题都成立

成套方法求线性递归式的封闭形式

现在有一包含多个参数的线性递归式，求其封闭形式

  1. 设答：设 f(n)=A(n)\alpha+B(n)\beta+C(n)\gamma+D(n)\delta+\cdots
  2. 取特殊值：用特殊的参数组，使得函数有特殊的结果
    • 先带入参数组，然后解出函数的结果
    • 先令函数有特殊结果，再解方程得到参数组的特殊值
  3. 回代：将特殊值代入所设方程
  4. 解决：解系数函数的方程组