Concrete Mathematics 2 :Sums

2017-01-17 阅读量

第二章内容略多,个人感觉难度的话,是从易到难。但是作者写的过程都很清晰,慢慢啃也是美滋滋 233333333 :D

目录:   0.和式的表示   1.解递归式   2.单个和式的处理   3.多重和式的处理   4.一般性的方法   5.有限微积分和无限微积分 (以下是正文)

和式的表示

这部分好像没啥可以多说的…

有两种表示和式的方式。 一种是用Σ:   对于∑,如果下标只有上下界的限制,表示起来相对自由;如果有多个限制,一般全部写在Σ的下方。   对于被加数的限制,可以使用艾弗森约定来表示。例如表示为$\sum_{k}a_{k}[P(k)]$,定义[]中式子的值。

另一种表示方式,是使用”…”

解递归式

个人觉得作者在写这个部分的时候,将和式和递归式联系的很好。 作者给了两种求解方法。

第一种求解方法是求递归式的通用方法之一: 成套方法。 对于一般形式,如: R(0)=α,R(n)=R(n-1)+β+γn; 我们可以令: R(n)=A(n)α+B(n)β+C(n)γ; 接着取特殊值,求出α,β,γ,如:   令R(n)=1,得 α=0,β=1,γ=0;   令R(n)=n,得 α=0,β=1,γ=0;   令R(n)=n^2,得 α=0,β=-1,γ=2; 分别代入等式,解得 A(n),B(n),C(n)的表达式; 反求R(n)即可;

第二种方法是构造法;(用于等差数列的求和) 形如: a(n)T(n)=b(n)T(n-1)+c(n); 令: s(n)=a(n)a(n-1)…a(1)/b(n)b(n-1)…b(1); 两边同时乘以s(n),其中s(n)满足: s(n)b(n)=s(n-1)a(n-1); 记: S(n)=S(n-1)+s(n)c(n); 整理出T(n)的表达式即可;

BTW在看第二种求解方法的时候,让我回想到很多高中学过的数列求和问题的解法。构造法是其中一种,除此之外还有公式法,裂项相加法,错位相减法,分组求和法(顺便想了想培杰)。

作者在这一节里还提到一个叫调和数的东西,用于方便表示递归解里的Σ表达式。

单个和式的处理

主要是用以下三种法则: $\sum _{ k\in K }^{ }{ c{ a }_{ k } } =c\sum _{ k\in K }^{ }{ a_k }$ (分配律)

$\sum _{ k\in K }^{ }{ (a_k + b_k) } =\sum _{ k\in K }^{ }{ a_k } + \sum _{k\in K}{b_k}$ (结合律)

$\sum_{k\in K}{a_k} = \sum_{P(k)\in K}{a_P(k)}$ (交换律)

其中,交换律举个例子: $a_{-1} + a_0 + a_1 = a_1 + a_0 + a_{-1}$

$\sum_{0<=k<=n}{ak} = \sum_{0<=n-k<=n}{a(n-k)}$

对于单个和式的处理,书中主要写了两种和式:等差级数的和式几何级数的和式

等差级数的和式: 形如:$S = \sum_{0<=k<=n}{(a + bk)}$ 一般套路是: 0.根据交换律,用n-k代替k,得到 $S = \sum_{0<=n-k<=n}{a + b(n-k)} $ 1.利用结合律,把两式相加,得到 $2S = \sum_{0<=k<=n}{(2a + bn)}$ 2.利用分配律,得到 $2S = (2a + bn)\sum_{0<=k<=n}{1} = (2a + bn)*(n+1)$ 3.整理得 $S = (a + \frac { 1 }{ 2 } bn)*(n + 1)$

几何级数的和式: 形如: $S_n = \sum_{0<=k<=n}{a_k}$ 一般使用扰动法(perturbation method)解之;(所谓扰动法,就是把一项分出去的运算) 扰动法求解:通过把$S_n$的最后一项和第一项分离出去,用两种方法改写$S_{n+1}$: $S_n + a_{n+1} = \sum_{0<=k<=n+1}{a_k} = a_0 + \sum_{1<=k<=n+1}{a_k} \\ = a_0 + \sum_{1<=k+1<=n+1} {a_{k+1}} $ (交换律) $= a_0 + \sum_{0<=k<=n} {a_{k+1}}$ 最后,尝试在等式两次都找到$S_n$,并将它表达出来即可;

多重和式的处理

所谓多重和式,就是一个和式的项由两个或者更多的指标确定;(同样可用艾弗森约定)

处理多重和式,一般用交换求和次序以及一般分配律进行化简,将多重和式化简为单重和式,再分别用三种基本法则处理单重和式;

交换求和次序: 基本法则:(其实就是结合律的推广)

$\sum_{j}\sum_{k}{a_{j,k}[P(j,k)]} = \sum_{[P(j,k)]}{a_{j,k}} = \sum_{k}\sum_{j}{a_{j,k}[P(j,k)]} $

等式的中间是对两个指标求和的和式。 左边,表示先对k求和再对j求和。而右边表示先对j求和再对k求和。求和顺序的改变有时候会使求解更方便。

基本法则的两种变形简易型: $\sum_{j\in J}\sum_{k\in K}{a_{j,k}} = \sum_{j\in J,k\in K}{a_{j,k}} = \sum_{k\in K}\sum_{j\in J}{a_{j,k}} $

适用于j,k的范围相互无关的情况

复杂型 $ \sum_{j\in J}\sum_{k\in K(j)}{a_{j,k}} = \sum_{k\in K’}\sum_{j\in J’(k)}{a_{j,k}} $

其中集合J,K(j),K’,J’(k)满足: $ [j\in J][k\in K(j)] = [k\in K’][j\in J’(k)] $

适用于内和的范围与外和的指标变量有关的情况;

一般分配律: $ \sum_{j\in J}\sum_{k\in K}{a_{j,k}} = \sum_{j\in J,k\in K}{a_{j,k}} = \sum_{k\in K}\sum_{j\in J}{a_{j,k}} $

一般分配律可以用交换求和次序的基本法则进行推导:(以下是推导过程)

$\sum_{1<=j,k<=3}{a_{j}b_{k}} = \sum_{j,k}{a_{j}b_{k}} [1<=j<=3][1<=k<=3] $

$=\sum_{j=1}^{3}\sum_{k=1}^{3}{a_{j}b_{k}} $

$=\sum_{j=1}^{3}{a_j}\sum_{k=1}^{3}{b_{k}} $

多重和式处理举例: 书上写了几个多重和式处理的栗子🌰,这里挑一个觉得比较妙的来写 $S = \sum_{1<=j<k=n}{(a_{k} - a_{j})(b_{k} - b_{j})}$ (j,k交换仍有对称性)

$= \sum_{1<=k<j<=n}{(a_{j} - a_{k})(b_{j} - b_{k})} = \sum_{1<=k<j<=n}{(a_{k} - a_{j})(b_{k} - b_{j})} $

根据恒等式: [1<=j<k<=n] + [1<=k<<j<=n] = [1<=j,k<=n] - [1<=j=k<=n]

$2S = \sum_{1<=j,k<=n}{(a_j - a_k)(b_j - b_k} - \sum_{1<=j=k<=n}{(a_j - a_k)(b_j - b_k)} $ (第二个和式为0,将第一个和式展开)

$=\sum_{1<=j,k<=n}{(a_{j}b_{j}) - a_{j}b_{k} - a_{k}b_{j} + a_{k}b_{k}} $

$=2\sum_{1<=j,k<=n}{a_{k}b_{k}} - 2\sum_{1<=j,k<=n}{a_{j}b_{k}} $

这两个多重和式处理起来非常妙,先看第一个和式的处理方法: $2\sum_{1<=j,k<=n}{a_{k}b_{k}} = 2\sum_{1<=k<=n}\sum_{1<=j<=n}{a_{k}b_{k}} $

$=2\sum_{1<=k<=n}{a_{k}b_{k}}\sum_{1<=j<=n}{1} $

$=2n\sum_{1<=k<=n}{a_{k}b_{k}} $

第二个和式处理方法比较一般,用一般分配律即可: $2\sum_{1<=j,k<=n}{a_{j}b_{k}} = 2\sum_{1<=j<=n}{a_{j}}\sum_{1<=k<=n}{b_{k}} $ (单重和式的交换律)

$=2\sum_{k=1}^{n}{a_{k}}\sum_{k=1}^{n}{b_{k}} $

//多说一句,其实多重和式这部分,有时候推导不是一眼就能够懂。无论是推导也好,公式理解也好,可以尝试耐心地将和式展开,观察变换的过程;

和式处理的一般性方法

2.5应该是对于前面的方法的一般性总结,这一节不想说太多:(详见前面的解释) 一般性方法:

0.查找公式; 1.数学归纳法; 2.建立成套方法; (这三种方法在讲递归式与和式的时候,都用很具体的讲到)

3.扰动法 (讲单个和式-几何级数的和式中有具体讲到)

4.用积分替换和式: 这里主要根据了积分的几何意义,令$S_n = 1*1 + 1*4 + … + 1*n $ 易知,$S_n = S_{n-1} + n^2$

又,$\int _{ 0 }^{ n }{ { x }^{ 2 } } = \frac{n^3}{3} $

令$E_n = S_n - \frac{n^3}{3}$;

$E_n = S_n - \frac{n^3}{3} = S_{n-1} + n^2 - \frac{n^3}{3} $

$= E_{n-1} + \frac { 1 }{ 3 }{(n-1)^3} + n^2 + \frac{n^3}{3} $

$= E_{n-1} + n - \frac{1}{3} $

求出递归式之后,根据解递归式的套路,即可得$S_n$

5.展开与收缩: 将单重和式改写成二重和式进行化简; 这里mark一下书中的例子: $S_n = \sum_{1<=k<=n}{k^2} = \sum_{1<=j<=k<=n}{k} $

$= \sum_{1<=j<=n}\sum_{j<=k<=n}{k} $

$= \sum_{1<=j<=n}{\frac{j+n}{2}{(n-j+1)}} $

$= \frac{1}{2}\sum_{1<=j<=n}{n*(n+1) + j - j^2} $

(接下来的推导没懂,mark)

$S_n= \frac{1}{2}{n^2(n+1)} + \frac{1}{4}{n(n+1)} - \frac{1}{2}{S_n} $

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

6.生成函数 (这个东西挺有意思的,我会在后一篇文章讲讲这个东西)

有限微积分和无限微积分

细看了这一节,不得不说混泥土数学这本书真的写得很好! 这一节主要是将微积分与和式之间的联系,讲了很多概念,在此记下~

0.先介绍一下算子(operator)的概念: 所谓算子,就是在函数上给出新的函数,用于产生函数;

1.无限微积分是基于微分算子D的性质:

$Df(x) = \lim _{ h->0 }{ \frac { f(x+h)-f(x) }{ h } } $

2.有限微积分是基于差分算子$\Delta$的性质:

$\Delta f(x) = f(x+1) - f(x) $

3.阶乘幂

下降阶乘幂

${ x }^{ \underline { m } } = x(x-1)(x-2)…(x-m+1) $

上升阶乘幂

${ x }^{ \overline { m } } = x(x+1)(x+2)…(x+m-1) $

而作者将这个概念呢,是为了用下降阶乘幂完美诠释有限微积分:

$\Delta({x}^{\underline{m}}) = {(x+1)}^{\underline{m}} - {x}^{\underline{m}} $

$= (x+1)x…(x-m+2) - x…(x-m+2)(x-m+1) $

$= mx(x-1)…(x-m+2) $

$={mx}^{\underline{m-1}} $

4.接下来我们认识一个奇妙的东西:无限微积分的算子D有一个逆运算,即逆微分算子(或积分算子) $\int $. 说这个逆微分算子$\int$略有些奇妙,是因为我们知道$\int$也表示不定积分,那么微分和积分之间如何联系呢?往下看--

微积分和逆差分算子存在以下基本定理: 微积分基本定理

$g(x) = Df(x) $ 当且仅当 $\int{g(x)dx} = f(x) + C $

逆差分算子的基本定理

$g(x) = \Delta f(x)$ 当且仅当 $\sum{g(x)}\delta = f(x) + C $

(这里的$\sum{g(x)}\delta $是g(x)的不定和式,是差分等于g(x)的一个函数类)

无限微积分存在定积分: 如果 g(x) = Df(x),那么:

$\int_{a}^{b}{g(x)dx} = [f(x)]_{ b }^{ a } = f(b) - f(a) $

对于有限微积分同样有: 如果 $g(x) = \Delta f(x)$,那么:

$\sum_{a}^{b}{g(x)\delta x} = [f(x)]_{ b }^{ a } = f(b) - f(a) $

那么如何理解这个奇怪的符号$\sum_{a}^{b}{g(x)\delta x}$呢?精彩的推导来了…接着看: 我们设$g(x) = \Delta f(x) = f(x+1) - f(x) $,(a,b均是整数,且b>=a) 如果b=a,那么:

$\sum_{a}^{b}{g(x)\delta x} = f(a) - f(a) = 0 $

如果b>a,那么:

$\sum_{a}^{b}{g(x)\delta x} = \sum_{k=a}^{b-1}{g(k)} $

$=\sum_{a<=k<b}{f(x+1) - f(x)} = (f(a+1) - f(a)) + (f(a+2) - f(a+1)) + … + (f(b-1) - f(b-2)) + (f(b) - f(b-1)) $

$=f(b) - f(a) $

微积分和定积分的完美联系!是吧 :D

5.用公式求解和式: 求解和式是以上公式的用武之地。用上这些公式,我们可以开心的求解一些和式~ 举个例子🌰:

$\sum_{0<=k<n}{k^{\underline{m}}} = [\frac{k^{\underline{m+1}}}{m+1}]_{0}^{n} = \frac{n^{\underline{m+1}}}{m+1} $

这个部分就不多说了~

6.求解无限微积分和有限微积分: 通过以上推导,我们粗略的知道微积分和定积分之间的相似性,求解定积分时我们常使用分部求和的法则,在微积分中同样适用; 公式如下:

$D(uv) = uDv + vDu $

$\int{uDv} = uv - \int{vDu} $

$\Delta (u(x)v(x)) = u(x+1)v(x+1) - u(x)v(x) $ $=u(x+1)v(x+1) - u(x)v(x+1) + u(x)v(x+1) - u(x)v(x) $ $=u(x)\Delta v(x) + v(x+1)\Delta u(x) $

第二章码完~撒花~ 作者中途没在线一周,然后开始努力填坑。不得不说,这第二章我真的是码字码到昏厥。 然俄,自己挖的坑也要微笑的填完 :)wtf…