算法导论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}$