和式-技巧

指标变量的取值

对于一个和式,一个好的建议是尽可能保证求和指标简单,同时不要吝啬加上值为 0的项。 k=0k=nk2 比起 k=1k=nk2 更像是一个好主意(我在下一篇文章中提到 扰动法时会用到这一点)

谁是系数

在上一次提到成套方法时,我们给出了求解形如 Sn=Sn1+βn+γ 的递归式的解。仅仅是要 注意,在我们最终写成的 Sn=A(n)α+B(n)β+C(n)γ 形式中,A(n),B(n),C(n) 是系数,但在递归式中 α,β,γ 才是 系数。

为什么能写成一般形式

不加以证明,但是这可以引出来另一个相关的问题。

我们在上一篇文章中通过直接用 n 的简单函数替换 Sn 来求出对应参数 α,β,γ 的值。

考虑如下的递归式(看起来似乎比上次的简单?)

S0=α S2j=S2j1+β S2j+1=S2j+γ

其中 j 是正整数。
如果我们仍然利用之前的方法试图 仅仅 通过用 n 的简单 函数替换 S 来求取递归式中参数的取值进而得出它的一般表示(我们之后会 [不严格地]说明原因)Sn=A(n)α+B(n)β+C(n)γ 中系数的表达式时,我们会遇到困难:对 B(n) 和 C(n) 我们只能得到 B(n)+C(n)=n (这当然是成立的)。当我们试图用 n2 替换 Sn 时,我们得到了不相容的方程。

原因(个人感性地理解)是这个递归式无法拟合一个二次函数。

观察更一般的情况,如果一个递归式形如 Sn=Sn1+P(n), 其中 P(n) 是 n 的多项式函数,我们可以将它对应的和式形式 k=1nP(k) 近似地看作一个定积分(使用有限积分可以 消除这个近似,但是此时我不会没有必要)。那么 Φ(x)=1nP(t)dt 就是这个积分,是和式的封闭形式,事实上 这个积分是一个恰好比 P(k) 高一次的多项式函数。

很显然,对于上面提到的例子,一个一次函数无法拟合二次函数,那么就会产生不相容 的方程。对于这个题目而言,我们需要通过启发式的不严格方法以及数学归纳法 来得出 B(n) C(n) 中的一者,进而求出另一者。

Publish: 2022-07-27
如无特殊说明,本站所有内容以 CC-BY-SA 4.0 协议发布
GO BACK