注：本节内容为《具体数学》(原书第二版) 1.3 约瑟夫问题中成套方法的旁注。

问题描述

对于任意的 $\alpha ,\beta ,\gamma$，试解递推式：

$$f(1)=\alpha$$

$$f(2n)=2f(n)+\beta (n\ge 1)$$

$$f(2n+1)=2f(n)+\gamma (n\ge 1)$$

解决方案——成套方法

先暂且不谈成套方法，我们不妨先看看我们是怎么解决这个问题的。观察这个式子。我们发现：$f(n)$ 一定是 $\alpha ,\beta ,\gamma$ 的线性组合。我们不妨设出三个多项式：$A(n),B(n),C(n)$，那么我们就可以将 $f(n)$ 表达为：

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

而如果要解出 $f(n)$，我们则只需要解出 $A(n),B(n),C(n)$ 三个式子的表达。三个未知数，三个方程。看，问题就这样被转化了。

注意：由于我们的式子应该对 任意 $\alpha ,\beta ,\gamma$ 成立，那么无论 $\alpha ,\beta ,\gamma$ 取何值，$A(n),B(n),C(n)$ 都应该是固定的。这便给了我们解决上述方程的第一条线索：

• 讨论某些特殊的 $\alpha ,\beta ,\gamma$，给出关于 $A(n),B(n),C(n)$ 的方程。

除此之外，我们还有其他的解决方法。看回我们假设的 $f(n)$ 的等式以及 $f(n)$ 原本的递推式。另一种思路浮出水面：为何不直接假设 $f(n)$？好吧，这是在猜测答案，但是我们也需要承认，有的时候猜测答案确实能够导向正确的结论。猜测 $f(n)$ 可能产生两种后果：

1. 是某组 $\alpha ,\beta ,\gamma$ 所给出的答案，我们顺利地得到了 $A(n),B(n),C(n)$ 的一组关系（通过将 $\alpha ,\beta ,\gamma$ 带入 $f(n)=A(n)\alpha +B(n)\beta +C(n)\gamma$)
2. 这样的 $f(n)$ 不可能成立，无解。

接下来我们看看书上用了什么方法来得出表达式：

1. 方法二：假设 $f(n)=1$
2. 方法二：假设 $f(n)=n$
3. 方法一：考察 $(\alpha ,\beta ,\gamma )=(1,0,0)$

最后我们成功解出了方程。

理解成套方法

我将成套方法总结为：先一般化问题，再特殊化问题。在特殊中寻求一般，再在一般中寻求特殊。

首先，何谓「先一般化」？很简单，我们看约瑟夫问题的原方程，只不过是我们给出的递推式的 $(\alpha ,\beta ,\gamma )=(1,-1,1)$ 的情况。

再看「特殊化」。我们设出了「一般情况」的式子之后，借助其的 一般性，去研究特殊子问题，由于一般中蕴含着特殊，而对特殊成立的式子对一般亦成立，这样双向的操作下，便能够对整个系统进行研究。不由得感慨这和马克思主义哲学中矛盾的一般性和特殊性有着异曲同工之妙。