Part1:求和公式及其性质
给定一个数列(a_1,a_2,dots,a_n),其中(ninmathbb{N}),可以将有限和(a_1+a_2+dots+a_n)记作
[sum_{i=1}^n a_i
]
特别地,若(n=0),则和式的值为(0),或称为级数(series).有限级数可以任意交换顺序求和.
给定一个无穷数列(a_1,a_2,dots,a_n,dots),定义其和为
[S=sum_{i=1}^{infty}a_i=lim_{n oinfty}sum_{i=1}^na_i
]
若极限存在,则该级数发散(divergent),否则该级数收敛(convergent).对于收敛级数,一般不能改变级数的求和顺序.然而,若
[S=sum_{i=1}^{infty}|a_i|
]
也收敛,则称之为绝对收敛(absolute convergent)级数.绝对收敛级数可以任意改变其求和顺序.
级数具有线性性(linearity).即,对于任意的常数(c_1,c_2)与数列(a_1,a_2,dots,a_n)和(b_1,b_2,dots,b_n),都有
[sum_{i=1}^n(c_1a_i+c_2b_i)=c_1sum_{i=1}^na_i+c_2sum_{i=1}^nb_i
]
对于无穷收敛级数也适用.线性性质还可以用于增长记号,即
[sum_{i=1}^nTheta(f(i))=Thetaleft(sum_{i=1}^n f(i)
ight);\
sum_{i=1}^nO(f(i))=Oleft(sum_{i=1}^n f(i)
ight)
]
Part2:常见级数
等差级数
形如
[sum_{i=1}^n (a+di)
]
的级数称为等差级数(arithmetic series).其和为
[S=sum_{i=1}^n (a+di)=an+sum_{i=1}^n di=an+frac{dn(n+1)}2
]
特别地,取(a=0,d=1)时,就有
[egin{align}
S=sum_{i=1}^n i=frac{n(n+1)}2=Theta(n^2)
end{align}
]
幂次和
给出柿子:
[egin{align*}
sum_{i=1}^n i^2=frac{n(n+1)(2n+1)}6\
sum_{i=1}^n i^3=frac{n^2(n+1)^2}4\
sum_{i=1}^n i^4=frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}\
sum_{i=1}^n i^5=frac{n^2(n+1)^2(2n^2+2n-1)}{12}
end{align*}
]
还有一些常用的变式:
[egin{align*}
sum_{i=1}^n (2i-1)^2=frac{n(4n^2)-1}3\
sum_{i=1}^n (2i-1)^3=n^2(2n^2-1)\
sum_{i=1}^n i(i+1)=frac{n(n+1)(n+2)}3\
sum_{i=1}^n i(i+1)(i+2)=frac{n(n+1)(n+2)(n+3)}4\
sum_{i=1}^n i(i+1)(i+2)(i+3)=frac{n(n+1)(n+2)(n+3)(n+4)}5\
sum_{i=1}^n left[prod_{j=0}^{k-1} (i+j)
ight]=frac{prodlimits_{i=0}^k (n+i)}{k+1}
end{align*}
]
更高次幂的求和公式也是有的,但是要涉及到伯努利数,也不常用.一般来说,(k)次幂和的结果是(Theta(n^{k+1}))级别的.
几何级数
对于非零实数(x
e 1),和式
[sum_{k=0}^n x^k=1+x+x^2+dots+x^n
]
称为几何级数(geometry series),其值为
[sum_{k=0}^n x^k=frac{x^{n+1}-1}{x-1}
]
当和为无限且(|x|<1)时,有
[sum_{k=0}^{infty} x^k=frac1{1-x}
]
调和数
对于(ninmathbb{N}^+),第(n)个调和数(harmonic number)是
[H_n=sum_{i=1}^n frac 1i=ln n+O(1)
]
调和级数(harmonic series)
[sum_{i=1}^{infty}frac1i
]
是发散的,但是常用来判定其它级数的敛散性.
裂项级数
对于任意数列(a_0,a_1,dots,a_n),有
[sum_{i=1}^n (a_i-a_{i-1})=a_n-a_0
]
这是因为(a_1,a_2,dots,a_{n-1})中的每一项都加减相消.这种求和方法称为裂项求和(telescoping sum).类似地,
[sum_{i=0}^{n-1}(a_i-a_{i+1})=a_0-a_n
]
举个栗子,我们考虑级数
[sum_{i=1}^{n-1}frac1{i(i+1)}
]
其每一项可写成
[frac1{i(i+1)}=frac1i-frac1{i+1}
]
所以
[sum_{i=1}^{n-1}frac1{i(i+1)}=sum_{i=1}^{n-1}left(frac1i-frac1{i+1}
ight)=1-frac1n
]
Part3:和式界的确定
有许多方法可以确定和式的界.
数学归纳法
这是求级数和的最基本的方法.以证明等差级数(sumlimits_{i=1}^n i=frac{n(n+1)}2)为例:
当(n=1)时,等式成立.假设该等式对(n)成立,那么对于(n+1),有
[sum_{i=1}^{n+1}i=sum_{i=1}^ni+(n+1)=frac{n(n+1)}2+(n+1)=frac{(n+1)(n+2)}2
]
通常我们并不需要求出和式的值,而可以用归纳法证明和式的界.以证明几何级数(sumlimits_{i=0}^n 3^i)的界为(O(3^n)),即对于所有的(nge0),都存在一个常数(c),使得(sumlimits_{i=0}^n 3^ile c3^n)为例:
当(n=0)时,只需(cge1),就有(sumlimits_{i=0}^n3^i=1le ccdot 1)成立.假设该界对(n)成立,那么对于(n+1),只需((1/3+1/c)le 1),即(cge3/2)成立,就有
[egin{align*}
sum_{i=0}^{n+1}3^i&=sum_{i=0}^n3^i+3^{n+1}\
&le c3^{n}+3^{n+1}\
&=left(frac13+frac1c
ight)c3^{n+1}\
&le c3^{n+1}
end{align*}
]
故(sumlimits_{i=0}^n 3^i=O(3^n))成立.
确定每一项的界
我们可以通过求得级数中每一项的界,通过放缩来求得级数的一个上界.举个栗子,对于等差级数((1)),有一个可以快速获得的上界
[sum_{i=1}^n ile sum_{i=1}^n n=n^2
]
通常,对于级数(sumlimits_{i=1}^n a_i),若令(m=maxlimits_{1le ile n}a_i),则有
[sum_{i=1}^na_ile ncdot m
]
当一个级数能以几何级数为界时,用级数中最大的项作为界并不理想.给定级数(sumlimits_{i=0}^n a_i),假设对于所有的(ige0),都有(a_{i+1}/a_ile r),其中(0<r<1)是常数(注意,必须是常数!).因为(a_ile a_0r^k),我们以一个收敛的无穷几何级数为界,则有
[sum_{i=0}^n a_ile sum_{i=0}^{infty} a_0r^i=a_0sum_{i=0}^{infty}r^i=a_0frac1{1-r}
]
举个栗子.我们要求(sumlimits_{i=1}^{infty}i/3^i)的界.为了从(0)开始求和,我们将柿子改写作(sumlimits_{i=0}^{infty}(i+1)/3^{i+1}).第一项(a_0)为(1/3),并且邻项的比值
[r=frac{(i+2)/3^{i+2}}{(i+1)/3^{i+1}}=frac13cdotfrac{i+2}{i+1}le frac23
]
是常数.因此有
[sum_{i=1}^{infty}frac{i}{3^i}=sum_{i=0}^{infty}frac{i+1}{3^{i+1}}le frac13cdot frac1{1-2/3}=1.
]
分割求和法
分割求和法是求取复杂和式界的好方法.其方法是,首先将一个级数按下标范围划分后表示为两个或多个级数的和,然后对每一个划分求出和式的界.以求等差级数((1))的下界为例,我们已知它有上界(n^2).为求得其一个下界,我们不妨设(n)为偶数,就有
[sum_{i=1}^ni=sum_{i=1}^{n/2}i+sum_{i=n/2+1}^{n}ige sum_{i=1}^{n/2}0+sum_{i=n/2+1}^n(n/2)=(n/2)^2=Omega(n^2)
]
因为(sumlimits_{i=1}^ni=O(n^2)),所以该界是渐进紧确界.
我们通常可以将和式分割,并忽略其常熟个起始项.该技巧一般适用于和式(sumlimits_{i=0}^na_i)中每一项(a_i)均独立于(n)的情况.之后,对于任意常数(i_0>0),都有
[sum_{i=0}^na_i=sum_{i=0}^{i_0-1}a_i+sum_{i=i_0}^na_i=Theta(1)+sum_{i=i_0}^na_i
]
例如,求
[sum_{i=0}^{infty}frac{i^2}{2^i}
]
的一个渐进上界,在(kge 3)时,观察其邻项比值为
[r=frac{(i+1)^2/2^{i+1}}{i^2/2^i}=frac{(i+1)^2}{2i^2}le frac89
]
又因为第一个和式的项数是常数,且第二个和式是一个收敛几何级数,所以
[sum_{i=0}^{infty}frac{i^2}{2^i}=sum_{i=0}^2frac{i^2}{2^i}+sum_{i=3}^{infty}frac{i^2}{2^i}le sum_{i=0}^2frac{i^2}{2^i}+frac98sum_{i=0}^{infty}left(frac89
ight)^i=O(1)
]
再举个栗子.我们可以用分割求和法确定调和数的界:
[H_n=sum_{i=1}^nfrac1i=O(log n)
]
我们将下标范围从(1)到(n)分割成(leftlfloorlog n
ight
floor+1),并令每一段上界为(1).对于(i=0,1,dots,leftlfloorlog n
ight
floor),第(i)段包含自(1/2^i)起到(1/2^{i+1})(不含)的项.因此有
[sum_{i=1}^nfrac1ilesum_{i=0}^{leftlfloorlog n
ight
floor}sum_{j=0}^{2^i-1}frac1{2^i+j}lesum_{i=0}^{leftlfloorlog n
ight
floor}sum_{j=0}^{2^i-1}frac1{2^i}=sum_{i=0}^{leftlfloor log n
ight
floor}1le log n+1
]
积分近似法
当一个和式的形式为(sumlimits_{i=m}^nf(i))时,其中(f(i))是单调递减函数,我们可以用积分求其近似值:
[int_{m-1}^nf(x)mathrm{d}xlesum_{i=m}^nf(i)leint_{m}^{n+1}f(x)mathrm{d}x
]
我们也可以用相似的方法求其渐进界:
[int_m^{n+1}f(x)mathrm{d}xlesum_{i=m}^nf(i)leint_{m-1}^nf(x)mathrm{d}x
]
我们用上述公式来计算调和数的紧估计.对于下界,可得
[sum_{i=1}^nfrac1ileint_1^{n+1}frac{mathrm dx}{x}=ln(n+1)
]
对于上界,有不等式
[sum_{i=2}^nfrac1ileint_1^nfrac{mathrm dx}{x}=ln n
]
由此得到其界
[sum_{i=1}^nfrac 1ile ln n+1
]
本文完