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}
\]
结束。
