水泥数学 Part 1笔记

开始读水泥数学这本书，计划学到生成函数，然后再网上看点资料，学会多项式

对于一个一般的递归式

$$\begin{align} f(1)&=\alpha \\ f(2n)&=2f(n)+\beta \\ f(2n+1)&=2f(n)+\gamma \end{align} \tag{1.1}$$

希望找到一个一般的封闭形式

对$n$列表发现可以表示成

$$\begin{equation} f(n)=A(n)\alpha+B(n)\beta+C(n)\gamma \end{equation} \tag{1.2}$$

的形式，且似乎有

$$\begin{align} A(n)&=2^m\\ B(n)&=2^m-1-l\\ C(n)&=l \end{align}\tag{1.3}$$

其中$n=2^m+l,l\in[0,2^m)$

若要验证$(1.3)$，除了带回去分奇偶性验证，还有一种方法，是选取特殊的值，通过指定的$\alpha,\beta,\gamma$或者$f(n)$，相互求解，然后观察是否满足$(1.3)$

$$\begin{align} f(n)=1 &\iff (\alpha,\beta,\gamma)=(1,-1,-1) \notag \\ f(n)=n &\iff (\alpha,\beta,\gamma)=(1,0,1) \notag \\ (\alpha,\beta,\gamma)=(1,0,0)=&\iff f(n)=A(n) \notag \\ \end{align}$$

求解

$$\begin{align} A(n)-B(n)-C(n)&=1 \notag \\ A(n)+C(n)&=n \notag \\ f(n)=A(n)&=2^m \notag \end{align}\normalsize$$

然后得证

这一成套方法(repertoire method)运用于“线性的”递归时最为成功，关键在于式$(1.2)$

---

稍稍改变$(1.1)$的形式，改写成

$$\begin{align} f(1)&=a\\ f(2n+j)&=2f(n)+\beta_{j} (j=0,1\mid n\geq 1) \end{align} \tag{1.4}$$

令
$n=(b_mb_{m-1}\dots b_1b_0)_2$
，则
$f(n)=2^m\alpha+2^{m-1}\beta_{b_{m-1}}+\dots+\beta_{b_{0}}$
（因为最后
$f((b_m)_2)=f(1)=\alpha$
），即
$f(n)=(\alpha\beta_{b_{m-1}}\cdots\beta_{b_0})_2$

这样 $O(\log n)$ 时间内得解

推广 $(1.4)$ 的形式，改写成

$$\begin{align} f(j)&=\alpha_j,1\leq j<d\\ f(dn+j)&=cf(n)+\beta_j,0\leq j<d,n\geq 1 \end{align} \tag{1.5}$$

展开容易得解 $f((b_mb_{m-1}\cdots b_0)_d)=(\alpha_{b_m}\beta_{b_{m-1}}\cdots \beta_{b_0})_c$