数学预备知识

1 常用证明方法

• 直接法
• 反证法
• 反例证明法
• 数学归纳法

  2 常用函数和公式

  2.1 指数和对数函数

  

  2.2 阶乘和二项式函数

  2.2.1 阶乘

  
  

2.2.2 二项式定理

   ![image.png](https://cdn.nlark.com/yuque/0/2020/png/632230/1583205194481-732d20f4-ae71-4653-af7d-b1698cbb3ae1.png#align=left&display=inline&height=155&name=image.png&originHeight=310&originWidth=664&size=36160&status=done&style=none&width=332)

2.3 鸽巢原理

2.4 级数求和

2.5 求和的积分近似

2.6 递归方程求解

2.6.1 用生成函数求解递归方程

2.6.1.1 生成函数的性质

2.6.2 用特征方程求解递归方程

2.6.2.1 线性同质递归方程求解

2.6.2.2 不同质递归方程求解

2.6.3 用递推发求解递归方程

2.6.3.1 展开递推

2.6.3.2 代入法

![image.png](https://cdn.nlark.com/yuque/0/2020/png/632230/1583206302464-d3cc217f-4ce8-4323-a6dd-cca81b3676a3.png#align=left&display=inline&height=293&name=image.png&originHeight=586&originWidth=688&size=163380&status=done&style=none&width=344)

2.6.3.3 变元法

![image.png](https://cdn.nlark.com/yuque/0/2020/png/632230/1583206325422-5600c419-a708-45dc-b777-7f1ba12e3c89.png#align=left&display=inline&height=73&name=image.png&originHeight=146&originWidth=674&size=43104&status=done&style=none&width=337)

2.6.3.4 套用公式法

• Master Theorem

这个方法对形如 f(n)=af(n/b)+s(n) 的递归方程，给出三种情况下方程解的渐进阶的三个相应估计公式供套用。