Teapot
混凝土数学(一)

目录

递归式的成套方法

定义

递归式:存在一个函数,输入一个正整数,输出一个数。有一些式子描述了分别输入有一定关系的不同正整数,输出的数的关系。称这些式子为递归式。

封闭形式:这个函数的输出的仅关于其输入的一个表达式。

使用

对于递归式,若它的封闭形式是“线性的”,即可以表示为 ,其中 n 为函数的输入、 为常数、 为与 n 有关的表达式,那么它的封闭形式可以应用这样的方法解出:

寻求一组已知其解的通用参数,获得一整套可以求解的特殊情形,然后将特殊情形组合起来得到一般的情形。有多少个独立的参数,就需要多少个独立的特解。

注意,在这种解法中,不妨将常数与封闭解的关系看作一个输入一组常数、输出封闭解的函数,因为此时 虽未知却是确定的。这意味着我们有两种方法去试探 的取值:

  • 给出一组常数,得到这组常数定义的封闭解,将解代入递归式,得到描述 的递归式。解出(一个)
  • 给出封闭形式的一个解,由递归式得到定义这组解的常数,将常数代入封闭形式的表达式,得到描述(一些) 关系的一个表达式。

若将第一种方法的结果看作第二种方法的特殊情形,那么我们实际上是在做这样的事情:我们寻找两两正交的若干个向量(与独立参数的个数——不妨设为 k——相等),解方程组 ,其中 是一组由对应向量代表的常数组确定的封闭解组成的向量。

示例

  • 用成套方法来求解一般的四参数递归式

  • 先观察 n 比较小的情形中 g(n) 的取值。

    n g(n)
    1
    2
    3
    4

    故设

    考虑特殊情形 ,有:

    容易归纳得到 ,其中

    考虑特殊情形 ,有:

    这定义了一组常数:

    代入封闭形式,得到:

    考虑特殊情形 ,类似地有:

    代入封闭形式,得到:

    接下来考虑了一下 ,发现无解,可能不太容易直接找出合适的 了,于是考虑直接给出一个与前三个常数向量正交的向量 ,解 。代入递归式后注意到封闭解可以写成 ,分别归纳 ,得到:

    于是有:

    即:

    联立上述四式:

    解得:

    于是得到封闭解。

和式转换为递归式求解

使用

和式 等价于递归式 故转换成递归式后可用递归式的成套方法解决。

递归式转换为和式求解

定义

求和因子:考虑形如 的递归式,在两边乘上一个 ,使得 ,那么记 ,有更简单的递归式 。称 为求和因子。

使用

对形如 的递归式,经求和因子处理后,得到递归式 ,这易于由和式转换为递归式求解的思路重新转化为和式,即 。那么就有原递归式的解

接下来考虑如何获得求和因子。 可以写成 ,从而展开成

故选取 的适当的常数倍,即获得一个合适的求和因子。

扰动法

定义

为任意一个有限整数集合, 中元素的和式可以用三条法则加以变换: 其中 的任意一个排列。

使用

基于三条法则,我们有用封闭形式计算一个和式的一般方法。称这个方法为扰动法(perturbation method)。它的思想是为一个未知和式命名,例如令 ,然后在两侧同时加上 ,并分离出右侧的 ,从而得到 接下来尝试处理右端的和式,用 表示它,从而消去和式并取得 的封闭解。

示例

  • 用扰动法解和式

  • 按照扰动法的一般格式得到: 运用结合律和分配律,有: 于是解得

交换求和次序

定义

交换求和次序(interchanging the order of summation):为了处理多重和式,我们推广结合律,得到交换求和次序的法则: 在计算多重和式时,先对一个指标求和通常比先对另一个指标求和更简单。此法则可用于获得理想的求和顺序。

使用

结合逻辑运算和艾弗森约定,交换求和次序可以处理比较复杂的情况。例如当内和范围与外和指标有关时, 成立,当 这种做法也时常配合替换指标变量(实质上是结合律)使用,以期在第一次求和时得到关于那个指标的平凡的和。

示例

在本例中,扰动法无法直接求出 ,但是通过展开 ,交换求和次序,获得更容易处理的和式,对其求和后,我们得到类似于扰动法结果的方程,并可以解出

有限微积分

定义

差分(difference)算子 有限微积分基本定理 其中 不定和式(indefinite sum),是差分等于 的一个函数类。 是满足 的任意一个函数

定和式 下降阶乘幂 其中 读作 直降 次。当 时,补充定义: 上升阶乘幂 其中 读作 直升 次。

阶乘二项式定理 的系数依 对应相等。

注:须在第三篇给出证明并删除此注释。

下降幂的指数法则 移位算子(shift operator)E

使用

有限微积分求未知和式封闭形式

有限微积分指出了一个求解未知和式封闭形式的方法:将其写成定和式形式 ,求出其逆差分函数 ,使得 ,于是和式叠缩(telescoping)

幂和式转换为下降幂和式求解

对于非负指数的下降阶乘幂,差分算子有一个好的性质:

于是写成定和式的形式并适当修改和替换,有: 这指出了一个对幂求和的方法,即先用下降幂的和将求和对象表示出来,然后用上式可以很容易地脱去求和号。

注:须在第三篇给出转换方法并删除此注释。

而当 ,若 ,上式仍然成立;若 ,由定义有: 从而有: 其中 为第 个调和数,即 。这是有限微积分相对于微积分中的 的一个类似物(就数值而言,也是它的一个离散模拟)。

于是有下降幂和式的完整描述:

分部求和法则

类比微积分中的分布积分法,同样可以导出一个分部求和法则