TAOCP 1.2.1部分习题

TAOCP 1.2.1部分习题

T9

题目标记：[25]
题目：
试求下面式子的求和表达式，并予以证明：

\[1^2 , 2^2 -1^2 , 3^2 -2^2 +1^2 , 4^2 -3^2 +2^2 -1^2\]
以下是分析：
手动计算几个，发现就是等差数列求和。
于是我们猜想，前n项和为 \(\frac{n(n+1)}{2}\) 。
接下来是证明：
我们使用数学归纳法证明。
当 \(n=1\) 时，左边为 \(1^2=1\)，右边为 \(\frac{1(1+1)}{2}=1\)，成立。
假设当 \(n=k\) 时，等式成立，即归纳假设IHk:

\[k^2 - (k-1)^2 + (k-2)^2 - \cdots - (-1)^{k}= \frac{k(k+1)}{2}\]
成立。
现在考虑 \(n=k+1\) 的情况。记前 \(n\) 项和为 \(F_n\)，则有

\[F_k = \frac{k(k+1)}{2}\]
我们尝试表示 \(F_{k+1}-F_k\)，注意到 \(F_{k+1}\) 与 \(F_k\) 除首项外，每项符号相反，因此，当我们计算 \(F_{k+1}-F_k\) 时，只有首项 \((k+1)^2\) 会被保留，其余项均翻倍。
因此，

\[F_{k+1} -F_k = - 2F_k + (k+1)^2 \\= - 2 \cdot \frac{k(k+1)}{2} + (k+1)^2 \\= - k(k+1) + (k+1)^2 \\= (k+1)(-k + k + 1) \\= k+1\]
因此，

\[F_{k+1} = F_k + (k+1) \\= \frac{k(k+1)}{2} + (k+1) \\= \frac{k(k+1) + 2(k+1)}{2} \\= \frac{(k+1)(k+2)}{2}\]
证毕。
T10

题目标记：[30]
题目：
试求下面式子的求和表达式，并予以证明：

\[\frac{1^3}{1^4+4} +\frac{3^3}{3^4+4}+ \cdots + \frac{(-1)^{n}(2n-1)^3}{(2n-1)^4+4}\]
以下是分析：
手动计算，我们注意到，分母之间每次差4的倍数，于是我们大胆猜想，是否有分母是类似 \(1+4 \times 2+4 \times 3+ \cdots +4 \times n\) 的形式。
显然是有的，这一步大约花费了我5min的时间。
随后我们考虑分子，肉眼就能观察到，分子就是 \(n\) 。
综上，我们有：

\[\frac{1^3}{1^4+4} +\frac{3^3}{3^4+4}+ \cdots + \frac{(-1)^{n}(2n-1)^3}{(2n-1)^4+4} \\= \frac{(-1)^{n+1} \cdot n}{1+4n^2}\]
接下来是证明：
我们使用数学归纳法证明。
当 \(n=1\) 时，左边为 \(\frac{1^3}{1^3+4}=\frac{1}{5}\)，右边为 \(\frac{(-1)^{1+1} \cdot 1}{1+4 \cdot 1^2}=\frac{1}{5}\)，成立。
假设当 \(n=k\) 时，等式成立，即

\[\frac{1^3}{1^4+4} +\frac{3^3}{3^4+4}+ \cdots + \frac{(-1)^{k}(2k-1)^3}{(2k-1)^4+4} \\= \frac{(-1)^{k+1} \cdot k}{1+4k^2}\]
现在考虑 \(n=k+1\) 的情况。我们记前 \(n\) 项和为 \(F_n\)，则有

\[F_k = \frac{(-1)^{k+1} \cdot k}{1+4k^2}\]
则左边为

\[\frac{1^3}{1^4+4} +\frac{3^3}{3^4+4}+ \cdots + \frac{(-1)^{k}(2k-1)^3}{(2k-1)^4+4} + \frac{(-1)^{k+1}(2(k+1)-1)^3}{(2(k+1)-1)^4+4} \\= F_k + \frac{(-1)^{k+1}(2(k+1)-1)^3}{(2(k+1)-1)^4+4} \\\]

\[= \frac{(-1)^{k+1} \cdot k}{1+4k^2} + \frac{(-1)^{k+1}(2k+1)^3}{(2k+1)^4+4} \\\]

\[= \frac{(-1)^{k+1} \cdot k((2k+1)^4+4) + (-1)^{k+1}(2k+1)^3(1+4k^2)}{(1+4k^2)((2k+1)^4+4)} \\\]

\[= \frac{(-1)^{k+1}((2k+1)^3(1+4k^2) + k((2k+1)^4+4))}{(1+4k^2)((2k+1)^4+4)} \\\]

\[= \frac{(-1)^{k+1}((2k+1)^3 + 8k^2(2k+1)^3 + k(16k^4 + 32k^3 + 24k^2 + 8k + 5))}{(1+4k^2)((2k+1)^4+4)} \\\]

\[= \frac{(-1)^{k+1}(16k^5 + 32k^4 + 24k^3 + 8k^2 + (2k+1)^3 + 8k^2(2k+1)^3)}{(1+4k^2)((2k+1)^4+4)} \\\]

\[= \frac{(-1)^{k+1}(16k^5 + 32k^4 + 24k^3 + 8k^2 + 8k^3 + 12k^2 + 6k + 1 + 64k^5 + 96k^4 + 48k^3 + 8k^2)}{(1+4k^2)((2k+1)^4+4)} \\\]

\[= \frac{(-1)^{k+1}(80k^5 + 128k^4 + 80k^3 + 28k^2 + 6k + 1)}{(1+4k^2)((2k+1)^4+4)} \\\]

\[= \frac{(-1)^{k+1}((2k+2)(16k^4 + 48k^3 + 40k^2 + 12k + 1))}{(1+4k^2)((2k+1)^4+4)} \\\]

\[= \frac{(-1)^{k+2} \cdot (k+1)}{1+4(k+1)^2}\]
证毕。
T16：（T15加强版本）

题目：
求

\[\sum_{j=0}^{n}{jx^j}\]
解：

\[\sum_{j=0}^{n}{jx^j} \\= \sum_{0\leq i\leq n}{ix^i} \\= x\sum_{1\leq i\leq n}{ix^{i-1}} \\= x\sum_{0\leq i\leq n-1}{(i+1)x^i} \\= x\sum_{0\leq i\leq n-1}{ix^i} + x\sum_{0\leq i\leq n-1}{x^i} \\= x\sum_{0\leq i\leq n}{ix^i} -nx^{n+1} + x\sum_{0\leq i\leq n-1}{x^i}\]
注意到：

\[x\sum_{0\leq i\leq n-1}{x^i} \\= x\sum_{0\leq i\leq n}{x^i} -x^{n+1} \\= x + x\sum_{1\leq i\leq n}{x^i} -x^{n+1} \\= x + x^{2}\sum_{1\leq i\leq n}{x^{i-1}} -x^{n+1} \\= x + x^{2}\sum_{0\leq i\leq n-1}{x^{i}} -x^{n+1}\]
不妨令：

\[S = x\sum_{0\leq i\leq n-1}{x^i}\]
我们有：

\[S = x+ xS -x^{n+1} \\\]

\[S-Sx = x-x^{n+1} \\\]

\[S = \frac{x-x^{n+1}}{1-x}\]
所以：

\[\sum_{j=0}^{n}{jx^j} \\= x\sum_{0\leq i\leq n}{ix^i} -nx^{n+1} + x\sum_{0\leq i\leq n-1}{x^i} \\= x\sum_{0\leq i\leq n}{ix^i} -nx^{n+1} + \frac{x-x^{n+1}}{1-x}\]
再令：

\[F = \sum_{1\leq i\leq n}{ix^i}\]
我们有：

\[F = x\sum_{0\leq i\leq n}{ix^i} -nx^{n+1} + \frac{x-x^{n+1}}{1-x} \\\]

\[F-xF = -nx^{n+1} + \frac{x-x^{n+1}}{1-x} \\\]

\[F = \frac{nx^{n+2}-(n+1)x^{n+1}+x}{(x-1)^2}\]
结束。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

很好很强大  我过来先占个楼 待编辑

新版吗？好像是停更了吧。

感谢，下载保存了

这个有用。