最近因为学习深入，需要回顾微积分的知识，顺便整理了微积分上的笔记。微积分下图太多，懒得画。

这里只提及一些积分技巧，并没有完全覆盖微积分上的所有内容。

点击这下载

本文且当作组合数学容斥原理部分的课堂笔记。点击这里获得PDF文本。

由于受够了jekyll的公式支持，决定不再写网页版，如果有需要，可以点击这里下载LaTex源代码。

在这里补充莫比乌斯反演经常用到的程序。

 1 const int n = 1 << 20;
 2 int mu[n];
 3 int getMu() {
 4     for (int i = 1; i <= n; i++) {
 5         int target = i == 1 ? 1 : 0;
 6         int delta = target - mu[i];
 7         mu[i] = delta;
 8         for (int j = i + i; j <= n; j += i)
 9             mu[j] += delta;
10     }
11 }

Leonardo [fibonaci] 提出一个问题:

在一年之初把性别相反的一对新生兔子放进围栏。从第二个月开始，母兔每月生出一对性别相反的小兔。每对新生兔子也从他们第二个月大开始每月生出一对新兔。求n个月后围栏内兔子的对数。

我们令$f_n$表示第n个月时兔子的对数。先考虑n较小的情况，列出$n=0,n=1…n=14$的情况。

下面我们尝试推导$f_n$的通项公式。在第n个月时，围栏内的兔子可以分为两部分：第n-1个月开始时已经有的兔子和第n-1个月期间出生的兔子。容易得出

考虑形式 $f\_n-f\_{n-1}-f\_{n-2}=0$ 解决这个递推关系的一种方法是寻找形式为 $f\_n=q^n$ 的一个解，其中q为一个非零数。将其带入递推式得 $q^n-q^{n-1}-q^{n-2}=0$ 解得 $q\_1=\frac{1+\sqrt{5}}{2}\quad q\_2=\frac{1-\sqrt{5}}{2}$

两者都是递推关系的解。由于递推关系时线性的和齐次的，通过直接计算得到 $f\_n=c\_1\left(\frac{1+\sqrt{5}}{2}\right)^n+c\_2\left(\frac{1-\sqrt{5}}{2}\right)^n$ 将初始值$f_0=0,f_1=1$代入求解得 $f_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n\quad(n\ge 0)$

例如斐波那契数列满足2阶线性递推关系。

解这类递推公式可以借助特征方程和特征根。

具体方法可以查看这篇文章 或者阅读组合数学相关书籍。

jekyll 弄公式真是乱七八糟，我都有用latex写博客的冲动了。