Answer

问题及解答

计算下面的级数

Posted by haifeng on 2013-06-02 09:43:09 last update 2013-06-02 09:45:54 | Edit | Answers (2)

\[
\sum_{i=0}^{+\infty}\frac{1}{4^i},\qquad\sum_{i=0}^{+\infty}\frac{i}{4^i},\qquad\sum_{i=0}^{+\infty}\frac{i^2}{4^i},\qquad\sum_{i=0}^{+\infty}\frac{i^N}{4^i}
\]


题目来源:

Mark Allen Weiss, 数据结构与算法分析 C++ 描述.(第三版),张怀勇等译. (习题 1.8)

1

Posted by haifeng on 2013-06-02 12:20:38

第一个级数是几何级数, 且是收敛的.

\[
\sum_{i=0}^{+\infty}\frac{1}{4^i}=\frac{1}{1-\frac{1}{4}}=\frac{4}{3}.
\]

 第二个级数首先证明它是收敛的, 这可以使用比值判别法或者根值判别法. 然后记和

为 $S$, 写出 $4S$ 的形式, 用后者减去前者即可发现能写成几何级数的形式, 从而容

易求出 $S$ 来. 具体的.

由于

\[
\lim_{i\rightarrow+\infty}\frac{\frac{i+1}{4^{i+1}}}{\frac{i}{4^i}}=\frac

{1}{4} < 1,
\]

所以级数收敛. 假设其和为 $S$, 则

\[
\begin{aligned}
S&=\frac{1}{4}+\frac{2}{4^2}+\frac{3}{4^3}+\frac{4}{4^4}+\frac{5}{4^5}+

\cdots\\
4S&=1+\frac{2}{4}+\frac{3}{4^2}+\frac{4}{4^3}+\frac{5}{4^4}+\frac{6}{4^5}+

\cdots
\end{aligned}
\]

将第二式减去第一式, 得

\[
\begin{split}
3S&=1+\frac{1}{4}+\frac{1}{4^2}+\frac{1}{4^3}+\frac{1}{4^4}+\frac{1}{4^5}+

\cdots\\
&=1+\frac{\frac{1}{4}}{1-\frac{1}{4}}=\frac{4}{3}
\end{split}
\]

因此, $S=\frac{4}{9}$.

第三个级数以及更一般的最后一个级数都是收敛的, 可以用比值判别法或根值判别法证

明. 这里不再赘述.

求和的过程类似于第二个情形. 仍设和为 $S$, 有

\[
\begin{aligned}
S&=\frac{1}{4}+\frac{2^2}{4^2}+\frac{3^2}{4^3}+\frac{4^2}{4^4}+\frac{5^2}

{4^5}+\cdots\\
4S&=1+\frac{2^2}{4}+\frac{3^2}{4^2}+\frac{4^2}{4^3}+\frac{5^2}{4^4}+\frac

{6^2}{4^5}+\cdots
\end{aligned}
\]

将第二式减去第一式, 得

\[
\begin{split}
3S&=1+\sum_{i=1}^{+\infty}\frac{(i+1)^2-i^2}{4^i}=\sum_{i=1}^{+\infty}\frac

{2i+1}{4^i}\\
&=2\sum_{i=1}^{+\infty}\frac{i}{4^i}+\sum_{i=0}^{+\infty}\frac{1}{4^i}\\
&=2\times\frac{4}{9}+\frac{4}{3}=\frac{20}{9}
\end{split}
\]

2

Posted by haifeng on 2013-07-05 17:21:33

最后一个级数的求出需要用到前面的级数, 也就是需要递归解决. 设

\[
S=\sum_{i=0}^{\infty}\frac{i^N}{4^i}=\frac{1}{4}+\frac{2^N}{4^2}+\frac{3^N}{4^3}+\frac{4^N}{4^4}+\frac{5^N}{4^5}+\cdots
\]

\[
4S=1+\frac{2^N}{4^1}+\frac{3^N}{4^2}+\frac{4^N}{4^3}+\frac{5^N}{4^4}+\frac{6^N}{4^5}+\cdots
\]

减去第一式, 得

\[
3S=1+\frac{2^N-1}{4}+\frac{3^N-2^N}{4^2}+\frac{4^N-3^N}{4^3}+\cdots=1+\sum_{i=1}^{\infty}\frac{(i+1)^N-i^N}{4^i}
\]

注意到

\[
(i+1)^N-i^N=Ni^{N-1}+C_N^2 i^{N-2}+\cdots+C_N^r i^{N-r}+\cdots+1
\]

因此要计算 $S(N)$ 的值, 必须先求出 $S(j)$, $j=1,2,\ldots,N-1$.