习题一
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+⋯+x
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/23959.html