算法导论A.1 Exercises 答案
A.1-1
令\(g_k(i)=O(f_k(i))\)，那么根据符号\(O\)的定义，\(\exists c_1,c_2,\dots,c_n,m_1,m_2,\dots,c_m>0,\forall n\ge m_k,0\le g_k(n)\le c_kf_k(n)\)成立。
令\(\displaystyle{m=\max_{k=1}^n \{m_k\},c=\max_{k=1}^n\{c_k\}}\)。根据求和的线性性质，对于\(\forall n\ge m\)，如下不等式成立：
\[0\le \sum_{k=1}^n g_k(n)\le\sum_{k=1}^n c_kf_k(n)\le \sum_{k=1}^n cf_k(n) \le c\sum_{k=1}^n f_k(n)=O\left(\sum_{k=1}^n f_k(n)\right)\]
因此\(\displaystyle{\sum_{k=1}^n O(f_k(i))}=O\left(\sum_{k=1}^n f_k(n)\right)\)。
A.1-2
\(\begin{aligned} \sum_{k=1}^n(2k-1)&=2\left(\sum_{k=1}^nk\right) -n\\ &=n(n+1)-n\\ &=n^2 \end{aligned}\)
A.1-3
代入\(x=10,n=9\)，那么有\(111111111=\dfrac{10^{10}-1}{9}\)。级数的第\(k\)项表示这个数十进制数下的第\(k\)位为\(1\).
A.1-4
令\(f(x)=\sum_{k=0}^{\infty} x^k=\dfrac{1}{1-x}\)。可以发现，这个值是\(f\left(-\dfrac{1}{2}\right)\)。
因此，
\[1-\dfrac{1}{2}+\dfrac{1}{4}-\dfrac{1}{8}+\dots=\dfrac{2}{3}\]
A.1-5
由于\(f(x)=x^c\)是递增的，因此考虑使用式子\((A.18)\)进行逼近。
上界：
\[\sum_{n=1}^k k^c\le \int_{1}^{n+1} x^c dx=\left.\dfrac{x^{c+1}}{c+1}\right|_{1}^{n+1}=\dfrac{(n+1)^{c+1}-1}{c+1}\]
下界：
\[\sum_{n=1}^k k^c\ge \int_{0}^{n} x^c dx=\left.\dfrac{x^{c+1}}{c+1}\right|_{0}^{n}=\dfrac{n^{c+1}}{c+1}\]
最终可以得到：
\[\dfrac{n^{c+1}}{c+1}\le\sum_{n=1}^k k^c\le \dfrac{(n+1)^{c+1}-1}{c+1}\]
并且有\(\dfrac{n^{c+1}}{c+1}=\Omega(n^{c+1}),\dfrac{(n+1)^{c+1}-1}{c+1}=O(n^{c+1})\)，因此最终有：
\[\sum_{n=1}^k k^c=\Theta(n^{c+1})\]
A.1-6
等式\((A.11)\)已有：
\[\sum_{k=0}^{\infty} kx^k=\dfrac{x}{(1-x)^2}\]
对以上式子两边进行求导，得到：
\[\sum_{k=0}^{\infty} k^2x^{k-1}=\dfrac{1-x^2}{(1-x)^4}\]
两边乘上\(x\)后得到最终答案（并且\(|x|<1\)）：
\[\sum_{k=0}^{\infty} k^2x^k=\dfrac{x(1+x)}{(1-x)^3}\]
A.1-7
上界：
\[\begin{aligned} \sum_{k=1}^n\sqrt{k\lg k}&\le \sum_{k=1}^n \sqrt{k \lg n}\\ &\le \sqrt{\lg n} \sum_{k=1}^n \sqrt{k}\\ &=\sqrt{\lg n}\cdot \Theta(n^{3/2})&\qquad(A)\\ &=O(n^{3/2}\lg^{1/2} n)\end{aligned}\]
其中，\((A)\)的变化使用了题目A-1.5的结论。
下界：
假设前\(\dfrac{n}{2}\)项的值都放缩到\(0\)，后\(\dfrac{n}{2}\)项的值都放缩到\(\dfrac{n}{2}\lg \dfrac{n}{2}\)。
\[\begin{aligned} \sum_{k=1}^n\sqrt{k\lg k}&= \sum_{k=1}^{n/2-1} \sqrt{k\lg k}+\sum_{k=n/2}^n\sqrt{k\lg k}\\ &\ge \sum_{k=1}^{n/2-1} 0+\sum_{k=n/2}^n\sqrt{\dfrac{n}{2}\lg \dfrac{n}{2}}\\ &\ge \dfrac{n}{2}\sqrt{\dfrac{n}{2}\lg \dfrac{n}{2}}\\ &= \dfrac{n^{3/2}}{8} \sqrt{\lg n-1}\\ &=\Omega(n^{3/2}\lg^{1/2} n) \end{aligned}\]
因此有：
\[\sum_{k=1}^n\sqrt{k\lg k}=\Theta(n^{3/2}\lg^{1/2} n) \]
\(\star\) A.1-8
可以观察出，级数\(\sum_{k=1}^n\dfrac{1}{2k-1}\)与调和数的关系满足：
\[\sum_{k=1}^n\dfrac{1}{2k-1}=H_n-\dfrac{H_{n/2}}{2}\]
因此，
\(\begin{aligned} \sum_{k=1}^n\dfrac{1}{2k-1}&=H_n-\dfrac{H_{n/2}}{2}\\ &=\ln n-\dfrac{\ln n/2}{2}+O(1)\\ &=\ln n-\dfrac{\ln n-\ln 2}{2}+O(1)\\ &=\dfrac{\ln n}{2} + O(1)\\ &=\ln(\sqrt{n}) + O(1) \end{aligned}\)
\(\star\) A.1-9
考虑使用列项相消解决，令\(\dfrac{ak+b}{2^k}-\dfrac{a(k+1)+b}{2^{k+1}}=\dfrac{k-1}{2^k}\)，那么通过待定系数法，可以解出来：
\(a=2,b=0\)
因此，
\[\sum_{k=0}^{\infty}\dfrac{k-1}{2^k}=\sum_{k=0}^{\infty} \left(\dfrac{2k}{2^k}-\dfrac{2(k+1)}{2^{k+1}}\right)=0-\lim_{k\rightarrow\infty} \dfrac{2(k+1)}{2^{k+1}}=0\]
\(\star\) A.1-10
不难发现，当\(|x|<1\)时，级数\(\sum_{k=1}^{\infty} 2k\cdot x^{2k}\)和\(\sum_{k=1}^{\infty} x^{2k}\)都是收敛的。
分别将两部分的计算结果相加就可以得到原级数\(\sum_{k=1}^{\infty} (2k+1)\cdot x^{2k}\)的答案。
\(\begin{aligned} \sum_{k=1}^{\infty} x^{2k}&=\sum_{k=0}^{\infty} x^{2k} -1\\ &=\sum_{k=1}^{\infty} (x^2)^k - 1\\ &=\dfrac{1}{1-x^2}-1 \end{aligned}\)
\(\begin{aligned} \sum_{k=1}^{\infty} 2k\cdot x^{2k}&=\sum_{k=0}^{\infty} 2k\cdot x^{2k}\\ &=2\sum_{k=0}^{\infty} k\cdot (x^2)^k\\ &=\dfrac{2x^2}{(1-x^2)^2} \end{aligned}\)
因此最终有
\[\sum_{k=1}^{\infty} (2k+1)\cdot x^{2k}=\dfrac{1}{1-x^2}-1+\dfrac{2x^2}{(1-x^2)^2}=\dfrac{1+x^2}{(1-x^2)^2}-1\]
\(\star\) A.1-11
\(\begin{aligned} \prod_{k=2}^n\left(1-\dfrac{1}{k^2}\right)&=\prod_{k=2}^n\dfrac{k-1}{k} \cdot \dfrac{k+1}{k}\\ &=\dfrac{(n-1)!\cdot (n+1)!/2}{(n!)^2}\\ &=\dfrac{1}{n}\cdot (n+1)\cdot\frac{1}{2}\\ &=\dfrac{n+1}{2n} \end{aligned}\)