《CM》2.5 General Methods

2.5 General Methods 一般方法

和的求解是非常有趣的,但是应当采用什么方法?而且关键是往往不知到怎么开始,求解这个和应当首先做什么?以下所有讨论都围绕求解如下和:

S_n=\sum_{0 \leq k \leq n}k^2,\quad \text{for }n \geq 0.

即0到n的所有数的平方和。该和的解为

S_n=\frac{n(n+\frac{1}{2})(n+1)}{3}

Method 0:查(You could look it up)

没错,书籍啊,google啊,去查吧,总可能有人已经求过这个和,你只需享受结果就行了。。有几本好书:《Mathematical Functionsm, by Abramowitz and Stegun》,《Handbook of Integer Sequences, by Sloane》...。还有几个好软件:Axiom,MACSYMA,Maple,Mathematica...。另外还有一个非常牛B的一个数列网站(Acmer应该都知道的吧):oeis

Method 1:猜,证(Guess the answer, prove it by induction)

就像求解递归式一样,打表,找规律,猜答案,最后数学归纳法证明答案。对S_n来说,数归证明毫无压力。

Method 2:扰动和(Perturb the sum)

还记得perturbation method吗?通常,对于求解一个和如果不知到怎么开始,那么可以试试perturbation method。如对S_n的求解应用此方法:

\begin{array}{l}S_n+(n+1)^2 & =\sum_{1 \leq k \leq n+1}k^2 & \\ & =\sum_{0 \leq k \leq n}(k+1)^2 & \text{replace }k\text{ by }k+1 \\ & =S_n+2\sum_{0 \leq k \leq n}k+n(n+1). & \text{unfold} \end{array}

S_n被消掉了。!但是,我们求出了\sum_{k=0}^nk!即0到n的的所有数的和!根据这个发现,有理由相信,如果我们对和C_n=\sum_{k=0}^nk^3应用perturbation method,那么C_n消掉之后,就剩了平方项,即要求的S_n!尝试一下,不难发现

C_n+(n+1)^3=C_n+3S_n+3\frac{(n+1)n}{2}+(n+1).

这样,就求出了S_n

Method 3:构造一般形式(Build a repertoire)

如同2.2节说的,和与递归有着相当的联系,可以利用解递归式的方法求解和。利用repertoire method可以解出递归式

\begin{array}{l}R_0=\alpha; \\ R_n=R_{n-1}+\beta +\gamma n+\delta n^2, \quad \text{for }n \gt 0.\end{array}

的解为:

R_n=A(n)\alpha +B(n)\beta +C(n)\gamma +D(n)\delta

的形式。显然S_n=D(n)

Method 4:用积分替换和(Replace sums by integrals)

这是一种非常神奇的方法,利用积分来求和!设函数

f_k(x)=\left\{ \begin{array}{l l}k^2 & \quad x \in [k-1,k] \\ 0 & \text{other} \end{array} \<br />
ight.

f_k(x)即为在[k-1,k]上高为k^2的一个长条形,显然[0,1], ..., [n-1,n]这n个长条形的面积就等于S_n,即

\int_{0}^{n}\sum_{k=1}^nf_k(x)\, \mathrm{d}x=\sum_{k=1}^{n}\int_{k-1}^{k}f_k(x)\, \mathrm{d}x=\sum_{k=1}^{n}k^2=S_n

现在用一个连续的函数f(x)=x^2,x \in [0,n]来近似\sum_{k=1}^nf_k(x),对这两个函数在[0,n]区间上积分,前者\int_{0}^{n}x^2\, \mathrm{d}x=\frac{1}{3}n^3,后者就为S_n。令E_n=S_n-\frac{1}{3}n^3,代表两者之间的差距,如果我们求出了E_n,也就求出了S_n。注意到

\begin{array}{l}E_n=S_n-\int_{0}^{n}x^2\, \mathrm{d}x & =\sum_{k=1}^n\int_{k-1}^kk^2\, \mathrm{d}x-\sum_{k=1}^n\int_{k-1}^kx^2\, \mathrm{d}x \\ & =\sum_{k=1}^n\left(k^2-\frac{k^3-(k-1)^3}{3}\<br />
ight) \\ & =\sum_{k=1}^n(k-\frac{1}{3}).\end{array}

So easy!

Method 5:“扩张和收缩”(Expand and contract)

还记得2.4节讲的在求单索引和的时候可以适当先引入多重和?我们说的所谓“扩张和收缩”就是指先把问题“扩大”,看似变难,然后再慢慢“收缩”,化成更加容易求解的形式

\begin{array}{l}S_n & =\sum_{1 \leq k \leq n}k^2=\sum_{1 \leq k \leq n}\left(k\sum_{1 \leq j \leq k}1\<br />
ight)=\sum_{1 \leq j \leq k \leq n}k \\ & =\sum_{1 \leq j \leq n}\sum_{j \leq k \leq n}k \\ & =\sum_{1 \leq j \leq n}\left(\frac{j+n}{2}\<br />
ight)(n-j+1) \\ & =\frac{1}{2}\sum_{1 \leq j \leq n}\left(n(n+1)+j-j^2\<br />
ight) \\ & =\frac{1}{2}n(n+\frac{1}{2})(n+1)-\frac{1}{2}S_n. \end{array}

Yes!

Method 6:使用有限微积分(Use finite calculus)

goto:next section(2.6节)

Method 7:使用生成函数(Use generating functions)

goto:chapter 5 section 4(5.4节)



发表评论

电子邮件地址不会被公开。 必填项已用*标注

*