习题一
1.2
将原来汉诺塔中，从 A A A直接到 B B B的步骤转化为以 C C C作为过渡进行移动，因此，解出 T ( n ) = 3 n − 1 T(n)=3^n-1 T(n)=3n−1
下面用数学归纳法证明：
- 当 n = 1 n=1 n=1时，将圆盘从 A A A移到 C C C再到 B B B，共花费 T ( 1 ) = 3 1 − 1 = 2 T(1)=3^1-1=2 T(1)=31−1=2步
- 假设当 n = k n=k n=k时，将圆盘从 A A A移到 B B B需要花费 T ( k ) = 3 k − 1 T(k)=3^k-1 T(k)=3k−1步
- 则当 n = k + 1 n=k+1 n=k+1时，先将前 k k k个圆盘移到 B B B桩，花费 T ( k ) T(k) T(k)步，再将第 k + 1 k+1 k+1个圆盘移到 C C C桩，花费1步；接着将前 k k k个圆盘移回 A A A桩，花费 T ( k ) T(k) T(k)步，将第 k + 1 k+1 k+1个圆盘移到 B B B桩，花费1步；最后将 k k k个圆盘再移动到 B B B桩，花费 T ( k ) T(k) T(k)步。因此，总共花费了 T ( k + 1 ) = 3 T ( k ) + 2 T(k+1)=3T(k)+2 T(k+1)=3T(k)+2步，即有 T ( k + 1 ) = 3 ( 3 k − 1 ) + 2 = 3 k + 1 − 1 T(k+1)=3(3^k-1)+2=3^{k+1}-1 T(k+1)=3(3k−1)+2=3k+1−1
由此可证： T ( n ) = 3 n − 1 T(n)=3^n-1 T(n)=3n−1
1.6
前面已经证出，平面上 n n n条直线所界定的区域的最大个数 L n = n ( n + 1 ) 2 + 1 , n ≥ 0 L_n= \frac{n(n+1)}{2}+1, \ n \ge0 Ln=2n(n+1)+1, n≥0，因此，要求有界区域的最大个数，即相当于无界区域个数最少时的情形。而经过仔细观察 n = 3 n=3 n=3到 n = 4 n=4 n=4时无界区域个数的变化情况，会发现在区域1和2新增加了2个无界区域。
由此易得当第 n n n条直线与前 n − 1 n-1 n−1条直线相交于 n − 1 n-1 n−1个不同点时，每次增加的无界区域最小为 2 n 2n 2n个。因此，有界区域的最大个数 T ( n ) = n ( n + 1 ) 2 + 1 − 2 n = 1 2 n 2 − 3 2 n + 1 , n ≥ 0 T(n)= \frac{n(n+1)}{2}+1-2n=\frac{1}{2}n^2-\frac{3}{2}n+1, \ n \ge0 T(n)=2n(n+1)+1−2n=21n2−23n+1, n≥0
1.7
由 J J J的定义式：
J ( 1 ) = 1 J ( 2 n ) = 2 J ( n ) − 1 , n ≥ 1 J ( 2 n + 1 ) = 2 J ( n ) + 1 , n ≥ 1 \begin{aligned} J(1)&=1 \\J(2n)&=2J(n)-1, \ n\ge1 \\ J(2n+1)&=2J(n)+1, \ n\ge1 \end{aligned} J(1)J(2n)J(2n+1)=1=2J(n)−1, n≥1=2J(n)+1, n≥1得： J ( 2 ) = 2 J ( 1 ) − 1 = 1 J(2)=2J(1)-1=1 J(2)=2J(1)−1=1，而 H ( n ) = J ( n + 1 ) − J ( n ) H(n)=J(n+1)-J(n) H(n)=J(n+1)−J(n)，所以 H ( 1 ) = J ( 2 ) − J ( 1 ) = 0 ≠ 2 H(1)=J(2)-J(1)=0\ne2 H(1)=J(2)−J(1)=0=2，因此归纳法的基础情况不满足。
1.8
按照 Q n Q_n Qn的定义式： Q n = 1 + Q n − 1 Q n − 2 , n > 1 Q_n=\frac{1+Q_{n-1}}{Q_{n-2}}, \ n>1 Qn=Qn−21+Qn−1, n>1，计算下去： Q 0 = α Q 1 = β Q 2 = 1 + β α Q 3 = 1 + α + β α β Q 4 = 1 + α β Q 5 = α Q 6 = β … \begin{aligned} Q_0&= \alpha \\ Q_1&=\beta \\ Q_2&=\frac{1+ \beta }{ \alpha } \\ Q_3&=\frac{1+ \alpha + \beta}{ \alpha \beta} \\ Q_4&=\frac{1+ \alpha}{\beta} \\ Q_5&=\alpha \\ Q_6&=\beta \\ \dots \end{aligned} Q0Q1Q2Q3Q4Q5Q6…=α=β=α1+β=αβ1+α+β=β1+α=α=β易得， Q n Q_n Qn的周期为5，因此有： Q n = Q n + 5 Q_n=Q_{n+5} Qn=Qn+5
1.9
a. 若 P ( n ) P(n) P(n)成立，即有 x 1 … x n ≤ ( x 1 + ⋯ + x n n ) n , x 1 , … , x n ≥ 0 → x n = x 1 + ⋯ + x n − 1 n − 1 x 1 … x n − 1 x 1 + ⋯ + x n − 1 n − 1 ≤ ( x 1 + ⋯ + x n − 1 + x 1 + ⋯ + x n − 1 n − 1 n ) n ⇔ x 1 … x n − 1 x 1 + ⋯ + x n − 1 n − 1 ≤ ( x 1 + ⋯ + x n − 1 n − 1 ) n ⇔ x 1 … x n − 1 ≤ ( x 1 + ⋯ + x n − 1 n − 1 ) n − 1 \begin{aligned} x_1 \dots x_n &\le (\frac{x_1+ \dots +x_n}{n})^n, \ x_1,\dots ,x_n \ge0 \\ \xrightarrow{x_n=\frac{x_1+ \dots +x_{n-1}}{n-1}} x_1 \dots x_{n-1} \frac{x_1+ \dots +x_{n-1}}{n-1} &\le (\frac{x_1+ \dots +x_{n-1}+\frac{x_1+\dots+x_{n-1}}{n-1}}{n})^n \\ \Leftrightarrow x_1 \dots x_{n-1} \frac{x_1+ \dots +x_{n-1}}{n-1} &\le (\frac{x_1+\dots+x_{n-1}}{n-1})^n \\ \Leftrightarrow x_1 \dots x_{n-1} &\le (\frac{x_1+\dots+x_{n-1}}{n-1})^{n-1} \end{aligned} x1…xnxn=n−1x1+⋯+xn−1x1…xn−1n−1x1+⋯+xn−1⇔x1…xn−1n−1x1+⋯+xn−1⇔x1…xn−1≤(nx1+⋯+xn)n, x1,…,xn≥0≤(nx1+⋯+xn−1+n−1x1+⋯+xn−1)n≤(n−1x1+⋯+xn−1)n≤(n−1x1+⋯+xn−1)n−1
所以，对于 P ( n − 1 ) P(n-1) P(n−1)也成立。
b. 若 P ( 2 ) P(2) P(2)和 P ( n ) P(n) P(n)成立，有： P ( n ) : x 1 … x n ≤ ( x 1 + ⋯ + x n n ) n P ′ ( n ) : x n + 1 … x 2 n ≤ ( x n + 1 + ⋯ + x 2 n n ) n \begin{aligned} P(n):\ x_1\dots x_n &\le (\frac{x_1+ \dots +x_n}{n})^n \\ P'(n):\ x_{n+1}\dots x_{2n} &\le (\frac{x_{n+1}+ \dots +x_{2n}}{n})^n \end{aligned} P(n): x1…xnP′(n): xn+1…x2n≤(nx1+⋯+xn)n≤(nxn+1+⋯+x2n)n 所以： ( x 1 … x n ) ( x n + 1 … x 2 n ) ≤ ( ( x 1 + ⋯ + x n ) ( x n + 1 + ⋯ + x 2 n ) n 2 ) n (x_1\dots x_n)(x_{n+1}\dots x_{2n}) \le (\frac{(x_1+\dots+x_n)(x_{n+1}+\dots+x_{2n})}{n^2})^n (x1…xn)(xn+1…x2n)≤(n2(x1+⋯+xn)(xn+1+⋯+x2n))n又： P ( 2 ) : x 1 x 2 ≤ ( x 1 + x 2 2 ) 2 ⇒ ( x 1 + ⋯ + x n ) ( x n + 1 + ⋯ + x 2 n ) ≤ ( x 1 + ⋯ + x 2 n 2 ) 2 \begin{aligned} P(2): x_1x_2 &\le (\frac{x_1+x_2}{2})^2 \\ \Rightarrow (x_1+\dots+x_n)(x_{n+1}+\dots+x_{2n}) &\le(\frac{x_1+\dots+x_{2n}}{2})^2 \end{aligned} P(2):x1x2⇒(x1+⋯+xn)(xn+1+⋯+x2n)≤(2x1+x2)2≤(2x1+⋯+x2n)2所以： x 1 … x n x n + 1 … x 2 n ≤ ( ( x 1 + ⋯ + x 2 n 2 ) 2 n 2 ) n = ( x 1 + ⋯ + x 2 n 2 n ) 2 n x_1\dots x_n x_{n+1} \dots x_{2n} \le(\frac{(\frac{x_1+\dots+x_{2n}}{2})^2}{n^2})^n =(\frac{x_1+\dots+x_{2n}}{2n})^{2n} x1…xnxn+1…x2n≤(n2(2x1+⋯+x2n)2)n=(2nx1+⋯+x2n)2n
即证 P ( 2 n ) P(2n) P(2n)也成立。
c. 由a,b易知： P ( 2 ) → P ( 1 ) ; P ( 2 ) ∧ P ( 2 ) → P ( 4 ) → P ( 3 ) → P ( 6 ) → P ( 5 ) → … \begin{aligned} &P(2) \rightarrow P(1); \\ &P(2)\wedge P(2) \rightarrow P(4) \rightarrow P(3) \rightarrow P(6) \rightarrow P(5) \rightarrow \dots \end{aligned} P(2)→P(1);P(2)∧P(2)→P(4)→P(3)→P(6)→P(5)→…所以 P ( n ) P(n) P(n)对所有 n n n为真。
1.10
如图：
Q n Q_n Qn代表按顺时针将 n n n个圆盘从 A A A移到 B B B的最少移动次数， R n R_n Rn代表按顺时针将 n n n个圆盘从 B B B返回 A A A的最少移动次数。理解的关键在于观察到 Q n Q_n Qn需要移动的两个桩柱是相邻的，而 R n R_n Rn需要移动的桩柱之间隔了一根。
因此： Q n = { 0 n = 0 , 2 R n − 1 + 1 n > 0 , Q_n = \begin{cases} 0 &n=0, \\ 2R_{n-1}+1 &n>0, \\ \end{cases} Qn={02Rn−1+1n=0,n>0, 意即先将前 n − 1 n-1 n−1个圆盘从 A A A移到 C C C，花费 R n − 1 R_{n-1} Rn−1步；再将第 n n n个圆盘移到 B B B，花费1步；最后再将 n − 1 n-1 n−1个圆盘从 C C C移到 B B B，花费 R n − 1 R_{n-1} Rn−1步。
R n = { 0 n = 0 , 2 R n − 1 + 1 + Q n − 1 + 1 = Q n + Q n − 1 + 1 n > 0 , R_n= \begin{cases} 0 &n=0, \\ 2R_{n-1}+1+Q_{n-1}+1=Q_n+Q_{n-1}+1 &n>0, \\ \end{cases} Rn={02Rn−1+1+Qn−1+1=Qn+Qn−1+1n=0,n>0,意即先将前 n − 1 n-1 n−1个圆盘从 B B B移到 A A A，花费 R n − 1 R_{n-1} Rn−1步；再将第 n n n个圆盘从 B B B移到 C C C，花费1步；再将前 n − 1 n-1 n−1个圆盘从 A A A移到 B B B，花费 Q n − 1 Q_{n-1} Qn−1步；接着将第 n n n个圆盘从 C C C移到 A A A，花费1步；最后将前 n − 1 n-1 n−1个圆盘从 B B B移到 A A A，花费 R n − 1 R_{n-1} Rn−1步。
1.11
a.
因为相同尺寸的圆盘是不可区分的，且每一种尺寸的圆盘有两个。记有 n n n种不同的圆盘，易得： A 1 = 2 A n = 2 A n − 1 + 2 , n > 1 \begin{aligned} A_1 &=2 \\ A_n&=2A_{n-1}+2, \ n>1 \end{aligned} A1An=2=2An−1+2, n>1再算出它的封闭形式： A n + 2 = 2 ( A n − 1 + 2 ) → C n = A n + 2 C n = 2 C n − 1 ⇒ C n = 2 n + 1 ⇒ A n = 2 n + 1 − 2 \begin{aligned} A_n+2 & =2(A_{n-1}+2) \\ \xrightarrow{C_n=A_n+2}C_n & =2C_{n-1} \\ \Rightarrow C_n & = 2^{n+1} \\ \Rightarrow A_n & =2^{n+1}-2 \end{aligned} An+2Cn=An+2Cn⇒Cn⇒An=2(An−1+2)=2Cn−1=2n+1=2n+1−2
b.
如果需要在最后的排列中将所有同样尺寸的圆盘恢复到原来的上下顺序，则对于 n n n种圆盘（ 2 n 2n 2n个圆盘），有： B 1 = 3 B n = A n − 1 + 2 + A n − 1 + 2 + B n − 1 , n > 1 \begin{aligned} B_1&=3 \\ B_n&=A_{n-1}+2+A_{n-1}+2+B_{n-1}, \ n>1 \end{aligned} B1Bn=3=An−1+2+An−1+2+Bn−1, n>1假设是将 n n n种圆盘（每种两个）从 A A A柱移到 B B B柱，以 C C C柱为过渡。先将前 n − 1 n-1 n−1种圆盘不计顺序的从 A A A移到 B B B，花费 A n − 1 A_{n-1} An−1步；再将最后1种圆盘从 A A A移到 C C C，此时这2个圆盘在 C C C柱上的顺序应该是反向的，花费2步；接着将前 n − 1 n-1 n−1种圆盘不计顺序的从 B B B回到 A A A，花费 A n − 1 A_{n-1} An−1步；此时将 C C C柱上的两个反向的圆盘移到 B B B柱上，这样两个圆盘就可以按照正确的顺序落在 B B B柱上，花费2步；最后将前 n − 1 n-1 n−1种圆盘按顺序的从 A A A移到 B B B，花费 B n − 1 B_{n-1} Bn−1步
再算出它的封闭形式： B n = 2 ( 2 n − 2 ) + 4 + B n − 1 ⇒ B n = B n − 1 + 2 n + 1 ⇒ B 2 = B 1 + 2 3 B 3 = B 2 + 2 4 B 4 = B 3 + 2 5 ⋮ B n = B n − 1 + 2 n + 1 ⇒ S n − B 1 = S n − 1 + 2 3 ( 2 n − 1 − 1 ) 2 − 1 ⇒ S n − S n − 1 = B n = 2 n + 2 − 5 \begin{aligned} B_n & = 2(2^n-2)+4+B_{n-1} \\ \Rightarrow B_n & =B_{n-1}+2^{n+1} \\ \Rightarrow B_2 &= B_1 + 2^3 \\ B_3 &= B_2 + 2^4 \\ B_4 &= B_3 + 2^5 \\ \vdots \\ B_n &= B_{n-1} + 2^{n+1} \\ \Rightarrow S_n -B_1 & =S_{n-1} + \frac{2^3(2^{n-1}-1)}{2-1} \\ \Rightarrow S_n-S_{n-1} = B_n &= 2^{n+2} -5 \end{aligned} Bn⇒Bn⇒B2B3B4⋮Bn⇒Sn−B1⇒Sn−Sn−1=Bn=2(2n−2)+4+Bn−1=Bn−1+2n+1=B1+23=B2+24=B3+25=Bn−1+2n+1=Sn−1+2−123(2n−1−1)=2n+2−5
1.13
我们可以将眼前的直线看作是有着极其细微的 Z Z Z型折痕：
因此，可以仿照直线切割平面区域来思考。同时又观察到，原本的每个交点现在会多增加8个区域，所以列出下面的递推方程： Z 1 = 2 Z n = Z n − 1 + n + 8 ( n − 1 ) , n > 1 \begin{aligned} Z_1 & = 2 \\ Z_n & = Z_{n-1}+n+8(n-1), \ n>1 \end{aligned} Z1Zn=2=Zn−1+n+8(n−1), n>1意即，当第 n n n条直线在 n − 1 n-1 n−1个不同地方与前面那些直线相交，会使区域个数新增加 n n n个（这是直线切割的情况），再加上Z型交点新增加的 8 ( n − 1 ) 8(n-1) 8(n−1)个区域。进而算出它的封闭形式： Z 2 = Z 1 + 9 ∗ 2 − 8 Z 3 = Z 2 + 9 ∗ 3 − 8 ⋮ Z n = Z n − 1 + 9 n − 8 ⇒ S n − 2 = S n − 1 + 9 ( ( n − 1 ) ( 2 + n ) 2 ) − 8 ( n − 1 ) ⇒ S n − S n − 1 = Z n = 9 2 n 2 − 7 2 n + 1 \begin{aligned} Z_2 & = Z_1+9*2-8 \\ Z_3 & = Z_2 +9*3-8 \\ \vdots \\ Z_n & = Z_{n-1} +9n-8 \\ \Rightarrow S_n-2 & = S_{n-1} +9( \frac{(n-1)(2+n)}{2} ) -8(n-1) \\ \Rightarrow S_n - S_{n-1} = Z_n & = \frac{9}{2} n^2 - \frac{7}{2} n +1 \end{aligned} Z2Z3⋮Zn⇒Sn−2⇒Sn−Sn−1=Zn=Z1+9∗2−8=Z2+9∗3−8=Zn−1+9n−8=Sn−1+9(2(n−1)(2+n))−8(n−1)=29n2−27n+1
1.14
首先计算出 n n n很小时， P n P_n Pn的值： P 1 = 2 P 2 = 4 P 3 = 8 \begin{aligned} P_1 & = 2 \\ P_2 & = 4 \\ P_3 & = 8 \end{aligned} P1P2P3=2=4=8 也许看上去很像是 P n = 2 n P_n = 2^n Pn=2n的关系，但实际上这是不可能的，因为不能保证每一刀都能触碰到之前分出的每一块。而要想让第 n n n刀切下去时，蛋糕尽量分出更多份，需要保证前面 n − 1 n-1 n−1个切痕在这第 n n n刀形成的平面上分出尽量多的区域，问题即转化为平面的直线分割。因此， P n P_n Pn的递推公式为： P n = P n − 1 + L n − 1 P_n = P_{n-1} + L_{n-1} Pn=Pn−1+Ln−1
1.15
要计算约瑟夫环的倒数第二个幸存者 I ( n ) I(n) I(n)的号码，首先考虑基础情况：当 n n n为2时，易知 I ( 2 ) = 2 I(2) = 2 I(2)=2，接着可以先算出 n n n比较小时的情况，以此来观察规律：
| n | 2 | 3 4 5 | 6 7 8 9 10 11 | 12 … \dots … | … \dots … |
|---|---|---|---|---|---|
| I ( n ) I(n) I(n) | 2 | 1 3 5 | 1 3 5 7 9 11 | 1 … \dots … | … \dots … |
写到这份上时，就很明显了，有： I ( 2 ) = 2 I ( 3 ∗ 2 m + l ) = 2 l + 1 , m ≥ 0 , 0 ≤ l < 2 m \begin{aligned} I(2) & = 2 \\ I(3*2 ^m + l) & = 2l +1, \ m \ge 0 , \ 0 \le l < 2^m \end{aligned} I(2)I(3∗2m+l)=2=2l+1, m≥0, 0≤l<2m
1.16
首先看一种递归式的有趣的解法： f ( 1 ) = α f ( 2 n + j ) = 2 f ( n ) + β j j = 0 , 1 n ≥ 1 \begin{aligned} f(1) & = \alpha \\ f(2n+j) & = 2f(n) + \beta_{j} \quad j=0,1 \quad n\ge1 \end{aligned} f(1)f(2n+j)=α=2f(n)+βjj=0,1n≥1将它按照二进制展开： f ( ( b m b m − 1 … b 1 b 0 ) 2 ) = 2 f ( ( b m b m − 1 … b 1 ) 2 ) + β b 0 = 4 f ( ( b m b m − 1 … b 2 ) 2 ) + 2 β b 1 + β b 0 ⋮ = 2 m f ( ( b m ) 2 ) + 2 m − 1 β b m − 1 + ⋯ + 2 β b 1 + β b 0 = 2 m α + 2 m − 1 β b m − 1 + ⋯ + 2 β b 1 + β b 0 \begin{aligned} f((b_m b_{m-1} \dots b_1 b_0)_2) & = 2 f((b_m b_{m-1} \dots b_1)_2 ) + \beta_{b_0} \\ & = 4f((b_m b_{m-1} \dots b_2)_2) + 2\beta_{b_1} + \beta_{b_0} \\ & \vdots \\ &= 2^{m}f((b_m)_2) +2^{m-1} \beta_{b_{m-1}}+ \dots + 2\beta_{b_1} + \beta_{b_0} \\ & = 2^m \alpha + 2^{m-1} \beta_{b_{m-1}} + \dots + 2\beta_{b_1} + \beta_{b_0} \end{aligned} f((bmbm−1…b1b0)2)=2f((bmbm−1…b1)2)+βb0=4f((bmbm−1…b2)2)+2βb1+βb0⋮=2mf((bm)2)+2m−1βbm−1+⋯+2βb1+βb0=2mα+2m−1βbm−1+⋯+2βb1+βb0 解除二进制的表示，从而允许各位上是任意数字，则有： f ( ( b m b m − 1 … b 1 b 0 ) 2 ) = ( α β b m − 1 β b m − 2 … β b 1 β b 0 ) 2 f((b_m b_{m-1} \dots b_1 b_0)_2 ) = (\alpha \beta_{b_{m-1}} \beta_{b_{m-2}} \dots \beta_{b_1} \beta_{b_0} )_2 f((bmbm−1…b1b0)2)=(αβbm−1βbm−2…βb1βb0)2再进一步推广，又有： f ( j ) = α j 1 ≤ j < d f ( d n + j ) = c f ( n ) + β j 0 ≤ j < d , n ≥ 1 ⇒ f ( ( b m b m − 1 … b 1 b 0 ) d ) = ( α b m β b m − 1 β b m − 2 … β b 1 β b 0 ) c \begin{aligned}f(j) & = \alpha_j \quad 1\le j <d \\ f(dn + j ) & = cf(n) + \beta_j \quad 0 \le j < d , \ n \ge 1 \\ \Rightarrow f((b_m b_{m-1} \dots b_1 b_0)_d) & = (\alpha_{b_m} \beta_{b_{m-1}} \beta_{b_{m-2}} \dots \beta_{b_1} \beta_{b_0})_c \end{aligned} f(j)f(dn+j)⇒f((bmbm−1…b1b0)d)=αj1≤j<d=cf(n)+βj0≤j<d, n≥1=(αbmβbm−1βbm−2…βb1βb0)c这里从基数为 d d d的数开始，结果表示为基数为 c c c的数。
而这道题目： g ( 1 ) = α g ( 2 n + j ) = 3 g ( n ) + γ n + β j j = 0 , 1 n ≥ 0 \begin{aligned} g(1) & = \alpha \\ g(2n+j) &= 3g(n) + \gamma n + \beta_j \quad j = 0,1 \quad n\ge0 \end{aligned} g(1)g(2n+j)=α=3g(n)+γn+βjj=0,1n≥0首先设： g ( n ) = a ( n ) α + b ( n ) β 0 + c ( n ) β 1 + d ( n ) γ g(n) = a(n)\alpha + b(n) \beta_0 +c(n)\beta_1 + d(n) \gamma g(n)=a(n)α+b(n)β0+c(n)β1+d(n)γ，当 n = ( b m b m − 1 … b 1 b 0 ) 2 ( b m ≠ 0 ) n= (b_m b_{m-1} \dots b_1 b_0)_2 \quad (b_m \ne 0) n=(bmbm−1…b1b0)2(bm=0) ，按照上面的思路，有： g ( ( b m b m − 1 … b 1 b 0 ) 2 ) = 3 g ( ( b m b m − 1 … b 1 ) 2 ) + γ ∗ ( b m b m − 1 … b 1 ) 2 + β b 0 = 3 2 g ( ( b m b m − 1 … b 2 ) 2 ) + 3 ∗ γ ∗ ( b m b m − 1 … b 2 ) 2 + 3 β b 1 + γ ∗ ( b m b m − 1 … b 1 ) 2 + β b 0 ⋮ = ( α b m β b m − 1 β b m − 2 … β b 1 β b 0 ) 3 + γ ∗ ( 0 ( b m ) 3 ( b m b m − 1 ) 3 … ( b m … b 1 ) 3 ) 3 = a ( n ) α + b ( n ) β 0 + c ( n ) β 1 + d ( n ) γ \begin{aligned} g(\ (b_m b_{m-1} \dots b_1 b_0)_2 \ ) & = 3g( \ (b_m b_{m-1} \dots b_1)_2\ ) + \gamma * (b_m b_{m-1} \dots b_1)_2 +\beta_{b_0} \\ & = 3^2g( \ (b_m b_{m-1} \dots b_2)_2 \ )+ 3*\gamma*(b_m b_{m-1} \dots b_2)_2 +3\beta_{b_1} +\gamma * (b_m b_{m-1} \dots b_1)_2 +\beta_{b_0} \\ \vdots \\ & =(\alpha_{b_m} \beta_{b_{m-1}} \beta_{b_{m-2}} \dots \beta_{b_1} \beta_{b_0})_3 + \gamma * (0 \ (b_m)_3 \ (b_m b_{m-1})_3 \dots \ (b_m \dots b_1)_3)_3 \\ & =a(n)\alpha +b(n) \beta_0 +c(n) \beta_1 +d(n)\gamma \end{aligned} g( (bmbm−1…b1b0)2 )⋮=3g( (bmbm−1…b1)2 )+γ∗(bmbm−1…b1)2+βb0=32g( (bmbm−1…b2)2 )+3∗γ∗(bmbm−1…b2)2+3βb1+γ∗(bmbm−1…b1)2+βb0=(αbmβbm−1βbm−2…βb1βb0)3+γ∗(0 (bm)3 (bmbm−1)3… (bm…b1)3)3=a(n)α+b(n)β0+c(n)β1+d(n)γ因此，有： d ( n ) = ( 0 ( b m ) 3 ( b m b m − 1 ) 3 … ( b m … b 1 ) 3 ) 3 a ( n ) α + b ( n ) β 0 + c ( n ) β 1 = ( α b m β b m − 1 β b m − 2 … β b 1 β b 0 ) 3 \begin{aligned} d(n) & = (0 \ (b_m)_3 \ (b_m b_{m-1})_3 \dots \ (b_m \dots b_1)_3)_3 \\ a(n) \alpha + b(n) \beta_0 +c(n) \beta_1 & = (\alpha_{b_m} \beta_{b_{m-1}} \beta_{b_{m-2}} \dots \beta_{b_1} \beta_{b_0})_3 \end{aligned} d(n)a(n)α+b(n)β0+c(n)β1=(0 (bm)3 (bmbm−1)3… (bm…b1)3)3=(αbmβbm−1βbm−2…βb1βb0)3
之后再来用成套方法（repertoire method）解决这题：
取 g ( n ) = n g(n) = n g(n)=n，则计算可知： a ( n ) + c ( n ) − d ( n ) = n a(n) +c(n) -d(n) = n a(n)+c(n)−d(n)=n ，
取 g ( n ) = 1 g(n)=1 g(n)=1，有 a ( n ) − 2 b ( n ) − 2 c ( n ) = 1 a(n)-2b(n)-2c(n)=1 a(n)−2b(n)−2c(n)=1
所以： b ( n ) = a ( n ) − 2 c ( n ) − 1 2 , d ( n ) = a ( n ) + c ( n ) − n b(n)=\frac{a(n)-2c(n)-1}{2}, \quad d(n)=a(n)+c(n) -n b(n)=2a(n)−2c(n)−1,d(n)=a(n)+c(n)−n
1.20
题目： h ( 1 ) = α h ( 2 n + j ) = 4 h ( n ) + γ j n + β j j = 0 , 1 n ≥ 1 \begin{aligned} h(1) = \alpha \\ h(2n+j) & = 4h(n) + \gamma_j n + \beta_j \quad j = 0,1 \quad n \ge 1\end{aligned} h(1)=αh(2n+j)=4h(n)+γjn+βjj=0,1n≥1思路和上一题一样：设 h ( n ) = a ( n ) α + b ( n ) β 0 + c ( n ) β 1 + d ( n ) γ 0 + e ( n ) γ 1 h(n) = a(n) \alpha +b(n) \beta_0 +c(n) \beta_1 +d(n) \gamma_0 + e(n) \gamma_1 h(n)=a(n)α+b(n)β0+c(n)β1+d(n)γ0+e(n)γ1，当 n = ( 1 b m − 1 … b 1 b 0 ) 2 n= (1 b_{m-1} \dots b_1 b_0)_2 n=(1bm−1…b1b0)2时，有 a ( n ) α + b ( n ) β 0 + c ( n ) β 1 = ( α β b m − 1 β b m − 2 … β b 0 ) 4 a(n)\alpha +b(n)\beta_0 +c(n)\beta_1 = ( \alpha \beta_{b_{m-1}} \beta_{b_{m-2}} \dots \beta_{b_0})_4 a(n)α+b(n)β0+c(n)β1=(αβbm−1βbm−2…βb0)4
若 h ( n ) = n h(n)=n h(n)=n，则 a ( n ) + c ( n ) − 2 d ( n ) − 2 e ( n ) = n a(n)+c(n)-2d(n)-2e(n)=n a(n)+c(n)−2d(n)−2e(n)=n；
若 h ( n ) = n 2 h(n) = n^2 h(n)=n2，则 a ( n ) + c ( n ) + 4 e ( n ) = n 2 a(n)+c(n)+4e(n)=n^2 a(n)+c(n)+4e(n)=n2
所以： d ( n ) = 3 a ( n ) + 3 c ( n ) − n 2 − 2 n 4 , e ( n ) = n 2 − a ( n ) − c ( n ) 4 d(n)=\frac{3a(n)+3c(n)-n^2-2n}{4}, \ e(n)=\frac{n^2-a(n)-c(n)}{4} d(n)=43a(n)+3c(n)−n2−2n, e(n)=4n2−a(n)−c(n)
