我有特殊的求前缀和技巧(Gosper算法)
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-----------------------------------------------------------------
谁想知道怎么快速求$\sum_{i=0}^{m}(_{i}^{n})(-1)^i$?
当然,用一些公式可以快速地推出来这个和式的封闭形式,但是这只是个例子.像这样的求和的题数不胜数,有没有一种通用的方法可以对一大部分函数求和呢?
有的,Gosper算法可以.
前置技能:离散微积分
不妨假设我们要求和的项为$f(x) = (_{x}^{n})(-1)^x$
根据离散微积分那一套理论,如果天地之间存在一个函数$S(x)$,使得$\Delta S(x) = S(x+1) - S(x) = f(x)$,那么我们就可以轻易得到原式等于$S(m+1) - S(0)$这样的结论了.
那么$S$是什么呢?
通过我的聪明才智,我发现,$S(x) = (_{x-1}^{n-1})(-1)^{x+1}$正好满足条件,因此原问题得解
诶诶别打我呀...
好吧,现在我们来介绍一种几乎是万能的求$S$的方法--Gosper算法(实际上还有比Gosper更万能的方法,这个以后再说吧,Gosper已经够可以了...)
-----------------------------------------------------------------
首先的首先,要注意Gosper算法的应用条件:${f(x+1) \over f(x)}$必须可以表示成两个非零多项式的商(为了方便,你还得求出这两个多项式因式分解之后的形式,通常可以通过把$f$表示成超几何项来做到)
满足了这一点之后,就可以使用Gosper算法,求出一个$f$的前缀和的封闭形式,或者这个算法告诉你天地之间根本就不存在这样的东西
首先,为了以后的需要,我们需要首先求出三个多项式$r,q$和$p$满足:
$条件1$:${f(x+1) \over f(x)} = {p(x+1) \over p(x)}{q(x) \over r(x+1)}$
$条件2$:对于任意一对$(a,b)$满足${q(x) \over (x+a)}$和${r(x) \over (x+b)}$是多项式,那么有$a > b$(注意,这里${q(x) \over (x+a)}$是一个多项式意味着$q(x)$因式分解之后有$(x+a)$这一项,或者,等价的,$q(-a)$等于$0$)
如何构造这三个多项式呢?
首先,之前说了$f(x+1) \over f(x)$可以表示成两个多项式的商,我们假设这两个多项式分别是$q'(x)=(x+a_1)(x+a_2)...(x+a_u)$和$r'(x)=(x+b_1)(x+b_2)...(x+b_v)$
现在,假设$p(x)=1$,令$q(x) = q'(x)$,$r(x) = r'(x - 1)$,显然满足$条件1$
现在考虑如何满足$条件2$,假设有一对不合法的$(a,b)$存在,那么令$q(x) = {q(x) \over (x + a)} , r(x) = {r(x) \over (x + b)}$,然后令$p(x) = p(x)(k+a-1)^{\underline{a-b}}$(我这里的意思是用后者给前者赋值,学过编程的大家应该都懂的...)
可以发现他始终满足$条件1$,然后不断地做直到他满足$条件2$为止即可
现在来求$S$
伟大的Gosper通过研究发现,$S$如果存在,那么他一定可以表示成这样的形式:
$S(x) = {r(x)t(x) \over p(x)}g(x)$ $(公式0)$
(其中$g$是某个未知的多项式)
因此$f(x) = {r(x+1)f(x+1)g(x+1) \over p(x+1)} - {r(x)f(x)g(x) \over p(x)}$ $(公式1)$
然后我们把$条件1$中的等式变一下形,把$f(x)$扔到等号右边,然后代入$公式1$,然后化一下简,得到:$f(x) = {q(x)f(x)g(x+1) \over p(x)} - {r(x)f(x)g(x) \over p(x)}$ $(公式2)$
然后我们就可以把$f(x)$消掉辣:$p(x) = q(x)g(x+1) - r(x)g(x)$
只要找到一个满足这个条件的$g(x)$,那么我们就求得$S$辣
显然,只要知道了$g$的次数,就可以把他带进$公式2$,令$x$的指数相同的项两边系数和也相同,就可以得到一个线性方程组,解之即得$g$(或者说明无解)
接下来看怎么才能知道$g$的次数
(...证明过程懒得写了...我还是直接说结论吧,知道结论之后不是很难证...)
设$deg(a)$表示多项式$a$的次数(特别地,对于零多项式有$deg(0) = -1$)
设$Q(x) = q(x) - r(x) , R(x) = q(x) + r(x)$
设$Q$的最高次项系数为$z$,$R$的最高次项系数为$w$,那么有:
要么$deg(g) = deg(p) - deg(R) + 1$,要么$deg(g) = -{2z \over w}$(当且仅当$-{2z \over w}$是一个大于($deg(p) - deg(R) + 1$)的正整数时才需要检查第二种情况)
因此只要对这两种情况,都去解对应的方程组,只要解得出来任意一个答案,就求出$g$了
求出了$g$之后带进$公式0$就求出$S$辣
如果求不出合法的$g$,就说明$f$的前缀和不存在封闭形式...
-----------------------------------------------------------------
现在,作为示例,来说一下怎么求开头的那个和式的封闭形式
首先我们发现,${f(x+1) \over f(x)} = {x-n \over x+1}$
因此有$p(x) = 1 , q(x) = x - n , r(x) = x$
然后我们假设$S(x)$满足这样的形式:$S(x) = {x(-1)^{x}(n-1)^{\underline{x}}g(x) \over x!}$
其中$g$还不知道
然后可以得到一个关于$g$的方程:$1 = (x-n)g(x+1) - xg(x)$
然后,我们发现了$g(x) = -{1 \over n}$是原方程的一个解.因此我们就有$g(x)= -{1 \over n}$,代进上面那个表达式,就可以得到$S(x) = (_{x-1}^{n-1})(-1)^{x+1}$
-----------------------------------------------------------------
评论 (0)
