具体数学-使用成套方法解递归式

在本篇文章中，我们将使用一种通用的方法解如下的递归式。

\begin{alignedat}{2}
    f(1) &= \alpha，\\
    f(2n) &= 2f(n) + \beta,&n \ge 1 \\
    f(2n+1) &= 2f(n) + \gamma,&n \ge 1
\end{alignedat}

我们将f(n)对\alpha,\beta,\gamma的依存关系分离出来，我们就把它表示成形式

    f(n) \equiv A(n)\alpha + B(n)\beta + C(n)\gamma

看起来有

\begin{alignedat}{1}
    A(n) &= 2^m \\
    B(n) &= 2^m -1 -l \\
    C(n) &= l
\end{alignedat}

这里有n=2^m + l 和 0 \le l 。用数学归纳法来证明这些并不困难，但是，如果你没有很好的“眼力”，你可能看不出这些等式。对此，我们决定找一种更为通用的方法来解决此类问题。

这个方法是，通过取特殊的值，然后将它们组合起来。我们首先考虑\alpha=1,\beta=\gamma=0这一特殊情况来对此方法进行说明。此时f(n) = A(n)，所有我们有

\begin{alignedat}{2}
    f(1) &= A(1) = 1 \\
    f(2n) &= A(2n) &= 2A(n) , n \ge 1\\
    f(2n+1) &= A(2n+1) &= 2A(n), n \ge 1
\end{alignedat}

也就是说

\begin{alignedat}{1}
    A(1) &= 1 \\
    A(2n) &= 2A(n) , n \ge 1\\
    A(2n+1) &= 2A(n), n \ge 1
\end{alignedat}

足以肯定的是A(2^m+l) = 2^m。对m用数学归纳法即可证明这一点。当m=0时必定有l=0，因为有n=2^m + l 和 0 \le l ，此时A(1)=1,此结论为真。归纳证明分为两个部分，l是偶数还是奇数：当m>0,l是偶数时：

\begin{alignedat}{1}
    A(2^m+l) &= A(2 \cdot (2^{m-1}+\frac{l}{2})) \\
            &= 2A(2^{m-1}+\frac{l}{2}) \\
            &= 2^m
\end{alignedat}

令一方面当m>0,l是奇数时：

\begin{alignedat}{1}
    A(2^m+l) &= A(2 \cdot (2^{m-1}+\frac{l-1}{2}) + 1) \\
            &= 2A(2^{m-1}+\frac{l-1}{2}) \\
            &= 2^m
\end{alignedat}

至此，我们就证明了这一结论。接下来，我们反过来使用递归式，从一个简单函数f(n)出发，并研究是否有任何常数(\alpha,\beta,\gamma)能定义它。比方说，把常数函数f(n) = 1 代入得到

\begin{alignedat}{1}
    1 &= \alpha,\\
    1 &= 2 \cdot 1 + \beta \\
    1 &= 2 \cdot 1 + \gamma
\end{alignedat}

从而满足这些方程的值(\alpha,\beta,\gamma) = (1,-1,-1)，然后我们就会得到一个新的方程

    A(n) - B(n) - C(n) = f(n) = 1

进一步的，我们代入f(n) = n，会得到(\alpha,\beta,\gamma) = (1,0,1)，就有

    A(n) + C(n) = f(n) = n

总结一下，我们有

\begin{alignedat}{1}
    A(2^m+l) &= 2^m \\
    A(n) - B(n) - C(n) &= 1 \\
    A(n) + C(n) &= n
\end{alignedat}

这样，我们就可以解出A(n),B(n),C(n)了！

现在，我们从进制的方面重新考虑这一问题，我们令\beta_{0} = \beta,\beta_{1} = \gamma,我们就可以吧递归式进行改写

\begin{alignedat}{2}
    f(1) &= \alpha，\\
    f(2n+j) &= 2f(n) + \beta_{j},j=0,1 ,n \ge 1 \\
\end{alignedat}

好！，我们按照二进制展开有

\begin{alignedat}{1}
    f((b_{m}b_{m-1}…b_{1}b_{0})_{2}) &= 2f((b_{m}b_{m-1}…b_{1})_{2}) + \beta_{b_{0}} \\
    &=4f((b_{m}b_{m-1}…b_{2})_{2}) + 2 \beta_{b_{1}} + \beta_{b_{0}} \\
    &=2^{m}\alpha + \sum_{i=0}^{m-1} 2^{i}\beta_{b_{i}}
\end{alignedat}

这也就是说:

    f((b_{m}b_{m-1}…b_{1}b_{0})_{2}) = (\alpha \beta_{b_{m-1}} \beta_{b_{m-2}} … \beta_{b_{1}} \beta_{b_{0}})_{2}.

事实上，对于更一般的递推式，

    f(j) = \alpha_{j}, \quad 1 \leq j 

我们有如下结论

    f((b_{m}b_{m-1}…b_{1}b_{0})_{d}) = (\alpha_{b_{m}} \beta_{b_{m-1}} \beta_{b_{m-2}} … \beta_{b_{1}} \beta_{b_{0}})_{c}.