《算法导论》笔记-附录A-求和
xuezhiyu
·
2025-01-16 22:12:04
·
算法·理论
本笔记由本人整理，难免出现错误之处，还请评论区的各位神犇指出 orz。
1. 求和公式及其性质
内容笔记
给定一个数列 a_m,a_{m+1},\cdots,a_n ，定义
a_m+a_{m+1}+\cdots+a_n=\sum_{k=m}^n a_k
如果 m>n ，则 \displaystyle \sum_{k=m}^n a_k=0 。
给定一个无限数列 a_m,a_{m+1},a_{m+2},\cdots ，可以将其无限和 a_m+a_{m+1}+\cdots 表示为
\sum_{k=m}^\infty a_k=\lim_{n \to \infty} \sum_{k=m}^n a_k
线性性质
\sum_{k=m}^n(ca_k+b_k)=c\sum_{k=m}^n a_k+\sum_{k=m}^n b_k
注意：对于所有级数 \displaystyle \sum_{k=m}^{\infty}(ca_k+b_k) ，并不满足 \displaystyle \sum_{k=m}^{\infty}(ca_k+b_k)=\displaystyle c\sum_{k=m}^{\infty}a_k+\sum_{k=m}^{\infty}b_k ，只当级数 \displaystyle\sum_{k=m}^{\infty}a_k 和 \displaystyle\sum_{k=m}^{\infty}b_k 都收敛时才成立。
常见级数
\begin{align}
& \sum_{k=1}^n k=\frac{n(n+1)}{2}&(\text{等差级数}) \\
& \sum_{k=0}^n k^2=\frac{n(n+1)(2n+1)}{6}&(\text{平方和}) \\
& \sum_{k=0}^n k^3=\frac{n^2(n+1)^2}{4}&(\text{立方和}) \\
& \sum_{k=0}^n x^k=\frac{x^{n+1}-1}{x-1}(x\not=1)&(\text{几何级数/指数级数}) \\
& \sum_{k=0}^{\infty} x^k=\frac{1}{1-x}(|x|<1)&(\text{无限递减几何级数}) \\
H_n=& \sum_{k=1}^n \frac 1 k=\ln n+O(1)&(\text{调和级数})
\end{align}
级数的微分和积分
对级数的两端进行微分或积分，可以得到新的级数公式。
例如，对 \displaystyle \sum_{k=0}^{\infty} x^k=\frac{1}{1-x} 的两端关于 x 微分，可得：
\begin{align}
\frac{\mathrm d}{\mathrm dx}\sum_{k=0}^{\infty}x^k&=\frac{\mathrm d}{\mathrm dx}(\frac{1}{1-x})\\
\sum_{k=0}^{\infty} kx^{k-1}&=\frac{(1-x)(\frac{\mathrm d}{\mathrm dx}(1))-(1)(\frac{\mathrm d}{\mathrm dx}(1-x))}{(1-x)^2}\\
\sum_{k=0}^{\infty}kx^{k-1}&=\frac{1}{(1-x)^2}
\end{align}
两边同乘 x ，得
\sum_{k=0}^{\infty}kx^k=\frac{x}{(1-x)^2}
裂项级数
\begin{align}
\sum_{k=1}^n (a_k-a_{k-1})&=a_n-a_{n-1}+a_{n-1}-a_{n-2}+\cdots+a_1-a_0 \\
&=a_n-a_0
\end{align}
同理可得：
\sum_{k=0}^{n-1} (a_k-a_{k+1})=a_0-a_n
以下是裂项和的一个例子：
\begin{align}
\sum_{k=1}^{n-1} \frac{1}{k(k+1)}&=\sum_{k=1}^{n-1}(\frac{1}{k}-\frac{1}{k+1}) \\
&=\frac 1 1-\frac 1 n \\
&=1-\frac 1 n
\end{align}
乘积
仿照级数的定义，我们可以把 a_ma_{m+1}\cdots a_n 写成
\prod_{k=m}^na_k
同理，定义当 m>n 时 \displaystyle \prod_{k=m}^na_k=1 。
我们还可以得到它的一些性质：
\begin{align}
\prod_{k=m}^n(ab)&=\prod_{k=m}^na\cdot\prod_{k=m}^nb \\
\prod_{k=m}^n\frac a b&=\frac{\displaystyle\prod_{k=m}^na}{\displaystyle\prod_{k=m}^nb} \\
\log_s(\prod_{k=m}^na_k)&=\sum_{k=m}^n\log_s(a_k)
\end{align}
练习
1. 求 \displaystyle \sum_{k=1}^n(2k-1) 的简化形式。
\begin{align}
\sum_{k=1}^n(2k-1)&=2\sum_{k=1}^nk-\sum_{k=1}^n1 \\
&=2 \cdot \frac{n(n-1)}{2}-n \\
&=n^2-n-n \\
&=n^2-2n
\end{align}
2. 利用调和级数证明：\displaystyle\sum_{k=1}^n\frac{1}{2k-1}=\ln(\sqrt n)+O(1) 。
\begin{align}
\sum_{k=1}^n\frac{1}{2k-1}&=\frac 1 1+\frac 1 3+\frac 1 5+\cdots+\frac 1 {2n-1} \\
&=\frac 1 1+\frac 1 2+\frac 1 3+\cdots+\frac 1 {2n}-\frac 1 2(\frac 1 1+\frac 1 2+\frac 1 3+\cdots+\frac 1 n) \\
&=\sum_{k=1}^{2n}\frac 1 k-\frac 1 2\sum_{k=1}^n \frac 1 k \\
&=\ln 2n+O(1)-\frac 1 2 \ln n+O(1) \\
&=\ln n+\ln 2+-\frac 1 2\ln n+O(1) \\
&=\frac 1 2 \ln n+O(1) \\
&=\ln \sqrt n+O(1)
\end{align}
3. 证明：\displaystyle \sum_{k=0}^{\infty}k^2x^k=\frac{x(1+x)}{(1-x)^3} 在 |x|<1 条件下成立。
由
\sum_{k=0}^{\infty}kx^k=\frac{x}{(1-x)^2}
在两端同时微分，得
\begin{align}
\sum_{k=0}^{\infty}k^2x^{k-1}&=\frac{(1-x)^2(\frac{\mathrm d}{\mathrm dx}(x))-x(\frac{\mathrm d}{\mathrm dx}(1-x)^2)}{(1-x)^4}\\
&=\frac{(1-x)^2+2x(1-x)}{(1-x)^4}\\
&=\frac{1-x+2x}{(1-x)^3}\\
&=\frac{1+x}{(1-x)^3}
\end{align}
两边同乘 x ，可得
\sum_{k=0}^{\infty}k^2x^k=\frac{x(1+x)}{(1-x)^3}
4. 证明 \displaystyle \sum_{k=0}^{\infty}\frac{k-1}{2^k}=0
\begin{align}
\sum_{k=0}^{\infty}\frac{k-1}{2^k}&=\sum_{k=0}^{\infty}(\frac 1 2)^k(k-1) \\
&=\sum_{k=0}^{\infty}k(\frac 1 2)^k-\sum_{k=0}^{\infty}(\frac 1 2)^k \\
&=\frac{(\frac 1 2)}{(1-\frac 1 2)^2}-\frac{1}{1-\frac 1 2} \\
&=\frac{(\frac 1 2)}{(\frac 1 4)}-\frac{1}{(\frac 1 2)} \\
&=2-2 \\ &=0
\end{align}
5. 对于 |x|>1 ，求 \displaystyle \sum_{k=1}^{\infty}(2k+1)x^{2k} 的值
\begin{align}
\sum_{k=1}^{\infty}(2k+1)x^{2k}&=2\sum_{k=1}^{\infty}k(x^2)^k+\sum_{k=1}^{\infty}(x^2)^k \\
&=2 \cdot \frac{x^2}{(1-x^2)^2}+\frac{1}{1-x^2} \\
&=\frac{2x^2}{(1-x^2)^2}+\frac{1-x^2}{(1-x^2)^2} \\
&=\frac{1+x^2}{(1-x^2)^2}
\end{align}
6. 用和的线性性质证明 \displaystyle \sum_{k=1}^nO(f_k(i))=O(\sum_{k=1}^nf_k(i))
注：这里本人是真不会了，在评论区向神犇求助
7. 计算乘积 \displaystyle\prod_{k=1}^n2\cdot4^k
\begin{align}
\lg(\prod_{k=1}^n2\cdot4^k)&=\sum_{k=1}^n\lg(2\cdot4^k) \\
&=\sum_{k=1}^n\lg(2^{2k+1}) \\
&=\sum_{k=1}^n(2k+1) \\
&=2\sum_{k=1}^nk+\sum_{k=1}^n1 \\
&=n(n+1)+n \\
&=n^2+2n
\end{align}
\therefore \prod_{k=1}^n2\cdot4^k=2^{n^2+2n}
8. 计算乘积 \displaystyle\prod_{k=2}^n(1-\frac{1}{k^2})
\begin{align}
\prod_{k=2}^n(1-\frac{1}{k^2})&=\prod_{k=2}^n\frac{k^2-1}{k^2} \\
&=\frac{\displaystyle\prod_{k=2}^n(k+1)(k-1)}{\displaystyle\prod_{k=2}^nk^2} \\
&=\frac{\displaystyle\prod_{k=2}^n(k+1)\prod_{k=2}^n(k-1)}{(n!)^2} \\
&=\frac{\frac{(n+1)!}{2}\cdot(n-1)!}{(n!)^2} \\
&=\frac{\frac{n+1}{2}\cdot n!\cdot n!\cdot\frac{1}{n}}{(n!)^2} \\
&=\frac{n+1}{2n}
\end{align}
2. 确定求和时间的界
内容笔记
有些时候我们并不需要确定一个求和公式的具体值，只需要知道一个求和公式的界，尤其是在分析算法复杂度时。
数学归纳法
数学归纳法要满足两个条件：
初始条件：即最开始的时候假设满足
保持：假设当前的假设对某个数满足，那么可以证明到更大的规模也满足这个假设
如果能够满足这两个要求，从初始条件出发，一直归纳就可以证明每个数都满足假设。所以数学归纳法不仅可以证明级数的界，还可以证明级数的确切值。
下面给出一个例子：证明 \displaystyle \sum_{k=1}^n k=\frac{n(n+1)}{2} 。
首先对于初始条件 n=1 ，容易得到 \displaystyle \sum_{k=1}^1k=1=\frac{1\cdot2}{2} ；若假设对 n 成立，则对 n+1 有
\begin{align}
\sum_{k=1}^{n+1}k&=\sum_{k=1}^nk+\sum_{k=n+1}^{n+1}k \\
&=\frac{n(n+1)}{2}+n+1 \\
&=\frac{n(n+1)}{2}+\frac{2(n+1)}{2} \\
&=\frac{(n+1)(n+2)}{2}
\end{align}
所以假设对 n+1 也成立。
下面是一个证明上界的例子：证 \displaystyle \sum_{k=0}^n3^k=O(3^n) ，更确切地说，证明对于某个常数 c ，有 \displaystyle \sum_{k=0}^n3^k\le c3^n 。
首先对于初始条件 n=0 ，有 \displaystyle \sum_{k=0}^03^k=1\le c\cdot1 ，只要满足 c \ge 1 。
接着对于一个满足假设的 n ，对 n+1 有
\begin{align}
\sum_{k=0}^{n+1}3^k&=\sum_{k=0}^n3^k+\sum_{k=n+1}^{n+1}3^k \\
&\le c3^n+3^{n+1}\\&=(\frac 1 3+\frac 1 c)c3^{n+1}
\end{align}
只要 \frac 1 3+\frac 1 c\le1 ，即 c\ge\frac 3 2 （与 c\ge1 不冲突），则有 (\frac 1 3+\frac 1 c)c3^{n+1}\le c3^{n+1} ，所以 \displaystyle\sum_{k=0}^{n+1}3^k\le c3^{n+1} ，于是就证明了 \displaystyle\sum_{k=1}^n3^k=O(3^n) 。
确定级数中各项的界
通常，对于级数 \displaystyle\sum_{k=1}^na_k ，如果令 a_{\max}=\displaystyle\max_{1\le k\le n}a_k ，则有
\sum_{k=1}^na_k\le\sum_{k=1}^na_{\max}=n\cdot a_{\max}
同理，令 a_{\min}=\displaystyle\min_{1\le k\le n}a_k ，则有
\sum_{k=1}^na_k\ge\sum_{k=1}^na_{\min}=n\cdot a_{\min}
例如对于 \displaystyle\sum_{k=1}^nk ，a_k=k ，则 a_{\max}=n ，所以可以得到一个上界：
\displaystyle\sum_{k=1}^nk\le\sum_{k=1}^nn=n^2
但这只能给出一个非常模糊的上界（大部分时候给出的是一个 o 上界，即不紧确的上界）。给定级数 \displaystyle\sum_{k=0}^na_k ，假定对于所有 k\ge0 ，有 \frac{a_{k+1}}{a_k}\le r ，其中 0<r<1 是常数。因为 a_k\le a_0r^k ，我们可以用无限递减几何级数作为上界，所以有
\sum_{k=0}^na_k\le\sum_{k=0}^{\infty}a_0r^k=a_0\sum_{k=0}^{\infty}r^k=\frac{a_0}{1-r}
例如求 \displaystyle\sum_{k=1}^{\infty}\frac{k}{3^k} 的界，我们可以先变形成 \displaystyle\sum_{k=0}^{\infty}\frac{k+1}{3^{k+1}} 。则相邻项的比值为
\frac{(\frac{k+2}{3^{k+2}})}{(\frac{k+1}{3^{k+1}})}=\frac 1 3\cdot \frac{k+2}{k+1}\le \frac 2 3
所以 r=\frac 2 3 ，并且 a_0=\frac 1 3 ，因此
\begin{align}
\sum_{k=1}^{\infty}\frac{k}{3^k}&=\sum_{k=0}^{\infty}\frac{k+1}{3^{k+1}} \\
&\le\frac 1 3\sum_{k=0}^{\infty}(\frac 2 3)^k \\
&=\frac 1 3\cdot\frac{1}{1-\frac 2 3} \\
&=1
\end{align}
所以 \displaystyle\sum_{k=1}^{\infty}\frac{k}{3^k} 有上界 1 。
但是在使用这个方法时有一些注意点，比如求调和级数 \displaystyle\sum_{k=1}^n\frac 1 k ，虽然 \displaystyle\frac{(\frac 1 {k+1})}{(\frac 1 k)}=\frac{k}{k+1}\le1 ，但是当 k\to\infty 时，有 \frac{k}{k+1}\to1 ，所以不存在一个 r 满足 \frac{k}{k+1}\le r 并且 0<r<1 ，所以这个级数是发散的。
分割求和
对于求和公式 \displaystyle\sum_{k=m}^na_k ，若 m \le p<n ，则
\sum_{k=m}^na_k=\sum_{k=m}^pa_k+\sum_{k=p+1}^na_k
例如对 \displaystyle\sum_{k=1}^nk ，如果直接求下界，则有
\sum_{k=1}^nk\ge\sum_{k=1}^n1=n
所以等差级数有下界 \Omega(n) ，与上界 O(n^2) 相差甚远，所以不能得到紧确界 \Theta(n^2) 。
试图采用分割求和的方式：
\begin{align}
\sum_{k=1}^nk&=\sum_{k=1}^{\lfloor \frac n 2\rfloor}k+\sum_{k=\lceil\frac n 2\rceil}^nk \\
&\ge\sum_{k=1}^{\lfloor\frac n 2\rfloor}1+\sum_{k=\lceil\frac n 2\rceil}^n\lceil\frac n 2\rceil \\
&\ge\frac n 2-1+\sum_{k=\lceil\frac n 2\rceil}^n\frac n 2 \\
&\ge\frac n 2-1+\frac n 2 \cdot \frac n 2 \\
&=\frac 1 4\cdot n^2+\frac 1 2\cdot n-1
\end{align}
所以有 \displaystyle\sum_{k=1}^nk=\Omega(n^2) ，于是就可以得到紧确界 \Theta(n^2) 。
在算法分析中可以忽略掉前面的常数项，只考虑后面的：
\begin{align}
\sum_{k=m}^na_k&=\sum_{k=m}^{p-1}a_k+\sum_{k=p}^na_k \\
&=O(1)+\sum_{k=p}^na_k
\end{align}
这一技巧同样适用于无限级数。例如，欲求
\sum_{k=0}^{\infty}\frac{k^2}{2^k}
的一个渐进上界。
相邻两项的比值为：
\frac{(\frac{(k+1)^2}{2^{k+1}})}{(\frac{k^2}{2^k})}=\frac{(k+1)^2}{2k^2}
当 k\ge3 时，\frac{(k+1)^2}{2k^2}\le\frac 8 9 ，于是我们可以裂项求和：
\begin{align}
\sum_{k=0}^{\infty}\frac{k^2}{2^k}&=\sum_{k=0}^2\frac{k^2}{2^k}+\sum_{k=3}^{\infty}\frac{k^2}{2^k}\\
&=O(1)+\frac 9 8\sum_{k=3}^{\infty}(\frac 8 9)^k\\
&=O(1)+\frac 9 8\sum_{k=0}^{\infty}(\frac 8 9)^k-\frac 9 8\sum_{k=0}^2(\frac 8 9)^k\\
&=O(1)+\frac 9 8\sum_{k=0}^{\infty}(\frac 8 9)^k\\
&=O(1)
\end{align}
分割求和法可以帮助我们确定更难的和式的值，例如确定调和级数的紧确界：
\begin{align}
\sum_{k=1}^n\frac1k&\le\sum_{i=0}^{\lfloor \lg n \rfloor}\sum_{j=0}^{2^i-1}\frac 1{2^i+j}\\
&\le\sum_{i=0}^{\lfloor\lg n\rfloor}\sum_{j=0}^{2^i-1}\frac 1{2^i}\\
&=\sum_{i=0}^{\lfloor \lg n \rfloor}1\\
&=\lfloor\lg n\rfloor\\
&\le\lg n+1
\end{align}
所以 \displaystyle\sum_{k=1}^n\frac 1 k=O(\lg n) 。
通过积分求和的近似
对于一个和式 \displaystyle\sum_{k=m}^nf(k) ，其中 f 是单调函数（只要在区间 [m-1,n+1] 是单调函数就行），那么就可以用积分来确定和式的近似值。
具体地说，当 f 是单调递增函数时，有
\int_{m-1}^nf(x)\mathrm dx\le \sum_{k=m}^nf(k)\le\int_{m}^{n+1}f(x)\mathrm dx
先看下限，因为 f 是单调递增函数，区间[i-1,i] 中的最大值为 f(i) ，于是 \displaystyle{\int_{i-1}^if(x)\mathrm dx}\le f(i) ，对于每个 i\in[m,n] 都满足这个式子，就满足 \displaystyle{\int_{m-1}^nf(x)}\mathrm dx\le\sum_{k=m}^nf(k) 。同理可得 \displaystyle{\sum_{k=m}^nf(k)\le\int_{m}^{n+1}f(x)\mathrm dx} 。
当 f 是单调递减函数时，有
\int_{m}^{n+1}f(x)\mathrm dx\le\sum_{k=m}^nf(k)\le\int_{m-1}^nf(x)\mathrm dx
证明方法也差不多，这里就不过多赘述了。
积分近似公式也可以为调和级数提供一个紧确界。因为 f(x)=\frac 1 x 是一个单调递减函数。对于其下界，可得
\begin{align}
\sum_{k=1}^n\frac 1 k&\ge\int_{1}^{n+1}\frac 1 x\mathrm dx\\
&=\ln(n+1)
\end{align}
对于上界，有
\begin{align}
\sum_{k=1}^n\frac 1 k&=\sum_{k=1}^1\frac 1 k+\sum_{k=2}^n\frac 1 k\\
&=1+\sum_{k=2}^n\frac 1 k
\end{align}
其中
\begin{align}
\displaystyle\sum_{k=2}^n\frac 1 k&\le\int_1^n\frac 1 x\mathrm dx\\
&=\ln n
\end{align}
所以
\sum_{k=1}^n\frac 1 k\le\ln n+1
加上下界，可得
\ln(n+1)\le \sum_{k=1}^n\frac 1 k\le\ln n+1
所以可以得到调和级数的紧确界 \Theta(\ln n) 。
练习
1. 证明：\displaystyle\sum_{k=1}^n\frac 1{k^2} 有常数上界。
因为 f(x)=\frac 1{x^2} 是一个单调递减的函数，所以可以运用积分近似法：
\begin{align}
\sum_{k=1}^n\frac{1}{k^2}&=\sum_{k=1}^1\frac{1}{k^2}+\sum_{k=2}^n\frac{1}{k^2}\\
&=1+\sum_{k=2}^n\frac{1}{k^2}
\end{align}
其中
\begin{align}
\sum_{k=2}^n\frac{1}{k^2}&\le\int_{1}^n\frac{1}{x^2}\mathrm dx\\
&=1-\frac 1 n\\
&\le1
\end{align}
所以
\sum_{k=1}^n\frac{1}{k^2}\le1+1=2
于是就证明了 \displaystyle\sum_{k=1}^n\frac{1}{k^2}=O(1) 。
2. 求下面一个和式的一个渐进上界：\displaystyle\sum_{k=0}^{\lfloor\lg n\rfloor}\lceil\frac{n}{2^k}\rceil 。
\begin{align}
\sum_{k=0}^{\lfloor\lg n\rfloor}\lceil\frac{n}{2^k}\rceil&\le\sum_{k=0}^{\lfloor\lg n\rfloor}(\frac{n}{2^k}+1)\\
&=n\sum_{k=0}^{\lfloor\lg n\rfloor}\frac{1}{2^k}+\lfloor\lg n\rfloor+1\\
&\le 2n+\lfloor\lg n\rfloor+1
\end{align}
于是 \displaystyle\sum_{k=0}^{\lfloor\lg n\rfloor}\lceil\frac{n}{2^k}\rceil=O(n) 。
3. 通过分割求和的方式证明第 n 个调和数是 \Omega(\lg n) 。
\begin{align}
\sum_{k=1}^n\frac 1 k&\ge\sum_{i=0}^{\lfloor\lg n\rfloor-1}\sum_{j=0}^{2^i-1}\frac 1{2^i+j}\\
&\ge\sum_{i=0}^{\lfloor\lg n\rfloor-1}\sum_{j=0}^{2^i-1}\frac 1{2^{i+1}}\\
&=\sum_{i=0}^{\lfloor\lg n\rfloor-1}\frac 1 2\\
&=\frac 1 2\lfloor\lg n\rfloor\\
&\ge\frac 1 2\lg n-\frac 1 2
\end{align}
所以就证明了 \displaystyle\sum_{k=1}^n\frac 1 k=\Omega(\lg n) 。
4. 用积分方法求 \displaystyle\sum_{k=1}^nk^3 的近似值。
因为 f(x)=x^3 是单调递增函数，所以有
\begin{align}
\int_{0}^nx^3\mathrm dx\le&\sum_{k=1}^nk^3\le\int_{1}^{n+1}x^3\mathrm dx\\
\frac 1 4\cdot x^4\le&\sum_{k=1}^nk^3\le\frac 1 4\cdot(x+1)^4-\frac14
\end{align}
5. 为什么我们不在 \displaystyle\sum_{k=1}^n\frac1k 上使用积分近似来获得第 n 个调和数的上界？
如果直接使用积分近似公式，会得到
\sum_{k=1}^n\frac1k\le\int_{0}^n\frac1x\mathrm dx=\lim_{m\to0}(\ln n-\ln m)=\infty
这个上界是没有意义的（有了跟没有一样，如有）。
思考题
1. 请给出下面和式的渐进紧确界。假设 r\ge0 与 s\ge0 均为常数。
a. \displaystyle\sum_{k=1}^nk^r
因为 f(x)=x^r 是单调递增函数，所以可以用积分近似法：
\begin{align}
\int_{0}^nx^r\mathrm dx\le&\sum_{k=1}^nk^r\le\int_{1}^{n+1}x^rdx \\
\frac{n^{r+1}}{r+1}\le&\sum_{k=1}^nk^r\le\frac{(n+1)^{r+1}}{r+1}-\frac{1}{r+1}
\end{align}
又因为 r 是常数，所以有 \displaystyle\sum_{k=1}^nk^r=\Theta(n^{r+1}) 。
b. \displaystyle\sum_{k=1}^n\lg^sk
\begin{align}
\sum_{k=1}^n\lg^sk&\le\sum_{k=1}^n\lg^sn\\
&=n\lg^sn
\end{align}
所以 \displaystyle\sum_{k=1}^n\lg^sk=O(n\lg^sn) 。
\begin{align}
\sum_{k=1}^n\lg^sk&\ge\sum_{i=0}^{\lfloor\lg n\rfloor-1}\sum_{j=0}^{2^i-1}\lg^s(2^i+j)\\
&\ge\sum_{i=0}^{\lfloor\lg n\rfloor-1}\sum_{j=0}^{2^i-1}\lg^s(2^i)\\
&=\sum_{i=0}^{\lfloor\lg n\rfloor-1}i^s2^i\\
&=\sum_{i=0}^{\lfloor\frac{\lg n}{2}\rfloor}i^s2^i+\sum_{i=\lfloor\frac{\lg n}{2}\rfloor+1}^{\lfloor\lg n\rfloor-1}i^s2^i\\
&\ge\sum_{i=\lfloor\frac{\lg n}{2}\rfloor+1}^{\lfloor\lg n\rfloor-1}(\lfloor\frac{\lg n}{2}\rfloor)^s2^{i}\\
&=(\lfloor\frac{\lg n}{2}\rfloor)^s\sum_{i=\lfloor\frac{\lg n}{2}\rfloor+1}^{\lfloor\lg n\rfloor-1}2^i\\
&=(\lfloor\frac{\lg n}{2}\rfloor)^s(2^{\lfloor\lg n\rfloor+1}-1-2^{\lfloor\frac{\lg n}{2}\rfloor+1}+1)\\
&\ge(\frac{\lg n}{2}-1)^s(2^{\lg n}-2^{\frac{\lg n}{2}})\\
&=(\frac{\lg n}{2}-1)^s(n-\sqrt{n})\\
&\ge(\frac12)^s(\lg n-2)^s(n-\sqrt n)
\end{align}
因为 s 是常数，所以 \displaystyle\sum_{k=1}^n\lg^sk=\Omega(n\lg^sn) ，结合上界，可以得到
\sum_{k=1}^n\lg^sk=\Theta(n\lg^sn)
c. \displaystyle\sum_{k=1}^nk^r\lg^sk
\begin{align}
\sum_{k=1}^nk^r\lg^sk&\le\sum_{k=1}^nn^r\lg^sn\\
&=n^{r+1}\lg^sn
\end{align}
所以 \displaystyle\sum_{k=1}^nk^r\lg^sk=O(n^{r+1}\lg^sn) 。
\begin{align}
\sum_{k=1}^nk^r\lg^sk&\ge\sum_{i=0}^{\lfloor\lg n\rfloor-1}\sum_{j=0}^{2^i-1}(2^i+j)^r\lg^s(2^i+j)\\
&\ge\sum_{i=0}^{\lfloor\lg n\rfloor-1}\sum_{j=0}^{2^i-1}(2^i)^r\lg^s(2^i)\\
&=\sum_{i=0}^{\lfloor\lg n\rfloor-1}\sum_{j=0}^{2^i-1}2^{ir}i^s\\
&=\sum_{i=0}^{\lfloor\lg n\rfloor-1}2^{i(r+1)}i^s\\
&=\sum_{i=0}^{\lfloor\frac{\lg n}{2}\rfloor}2^{i(r+1)}i^s+\sum_{i=\lfloor\frac{\lg n}{2}\rfloor+1}^{\lfloor\lg n\rfloor}2^{i(r+1)}i^s\\
&\ge\sum_{i=0}^{\lfloor\frac{\lg n}{2}\rfloor}2^{0(r+1)}0^s+\sum_{i=\lfloor\frac{\lg n}{2}\rfloor+1}^{\lfloor\lg n\rfloor}2^{i(r+1)}(\lfloor\frac{\lg n}{2}\rfloor+1)^s\\
&\ge\sum_{i=\lfloor\frac{\lg n}{2}\rfloor+1}^{\lfloor\lg n\rfloor}2^{i(r+1)}(\frac{\lg n}{2})^s\\
&\ge\frac{1}{2^s}\lg^sn\sum_{i=\lfloor\frac{\lg n}{2}\rfloor+1}^{\lfloor\lg n\rfloor}(2^{r+1})^i\\
&=\frac{1}{2^s}\lg^sn(\frac{(2^{r+1})^{\lfloor\lg n\rfloor}-1}{2^{r+1}-1}-\frac{(2^{r+1})^{\lfloor\frac{\lg n}{2}\rfloor}-1}{2^{r+1}-1})\\
&\ge\frac{1}{2^{s+1}(2^{r+1}-1)}\lg^sn((2^{\lg n})^{r+1}-1-(2^{\frac{\lg n}{2}})^{r+1}+1)\\
&=\frac{1}{2^{s+1}(2^{r+1}-1)}\lg^sn(n^{r+1}-n^{\frac{r+1}{2}})
\end{align}
因为 r 和 s 都为常数，所以 \displaystyle\sum_{k=1}^nk^r\lg^sk=\Omega(n^{r+1}\lg^sn) 。结合上界可得
\sum_{k=1}^nk^r\lg^sk=\Theta(n^{r+1}\lg^sn)