和式-技巧

指标变量的取值

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

谁是系数

在上一次提到成套方法时,我们给出了求解形如 $ S_n = S _ {n - 1} + \beta n + \gamma $ 的递归式的解。仅仅是要 注意,在我们最终写成的 $ S _ n = A(n) \alpha + B(n) \beta + C(n) \gamma $ 形式中,$ A(n),B(n),C(n) $ 是系数,但在递归式中 $ \alpha ,\beta ,\gamma $ 才是 系数。

为什么能写成一般形式

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

我们在上一篇文章中通过直接用 n 的简单函数替换 $ S _ n $ 来求出对应参数 $ \alpha ,\beta ,\gamma $ 的值。

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

$$ S _ 0 = \alpha $$ $$ S _ {2j} = S _ {2j - 1} + \beta $$ $$ S _ {2j + 1} = S _ {2j} + \gamma $$

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

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

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

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

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