隐藏目录
多项式级数
超几何级数
极大阶乘分解
Gosper算法

回到顶部多项式级数

为了解决多项式级数求和问题,我们先来研究一元单项式级数求和.

定理1

  1. $\sum\limits_{0\le k<n}k=\frac{n(n-1)}{2}$
  2. $\sum\limits_{0\le k<n}k^2=\frac{n(n-1)(2n-1)}{6}$
  3. $\sum\limits_{0\le k<n}k^3=\frac{n^2(n-1)^2}{4}$
  4. $\sum\limits_{0\le k<n}k^4=\frac{n(n-1)(2n-1)(3n^2-3n-1)}{30}$
事实上可以利用二项式展开求出任意次幂方和,但这样做得到的表达式一般比较复杂.
定义1
  1. 平移算子$E$将函数映射为函数,它满足$$E(f)(x)=f(x+1),$$定义$E^n=E\circ E^{n-1}$,$E^1=E$,$E^0=e$.
  2. 差分算子$\Delta=E^1-E^0$,它满足$$\Delta(f\cdot g)=\Delta(f)\cdot g+f\cdot\Delta(g)-\Delta(f)\cdot\Delta(g).$$
如果$g=\Delta(f)$,那么$\sum\limits_{i=a}^{b-1}g(i)=\sum\limits_{i=a}^{b-1}(f(i+1)-f(i))=f(b)-f(a)$,即$$g=\Delta(f)\Leftrightarrow f=\Sigma(g),$$这和微积分的互逆定理$$g=D(f)\Leftrightarrow f=\int g$$类似. 定义降阶乘$$f^{\underline{m}}=f(x)\cdot f(x-1)\cdots f(x-m+1),$$则$\Delta(x^{\underline{m}})=mx^{\underline{m-1}}$,于是$$\sum_{i=0}^{n-1}i^{\underline{m}}={1\over m+1}n^{\underline{m+1}}.$$ 设$$x^m=\sum_{i=0}^ma_{m,i}x^{\underline{i}},$$则 \begin{align*} x^m&=x\cdot x^{m-1}\\ &=\sum_{i=0}^{m-1}a_{m-1,i}(x-i+i)\cdot x^{\underline{i}}\\ &=\sum_{i=0}^{m-1}a_{m-1,i}x^{\underline{i+1}}+\sum_{i=0}^{m-1}a_{m-1,i}i\cdot x^{\underline{i}}\\ &=x^{\underline{m}}+\sum_{i=1}^{m-1}(a_{m-1,i-1}+i\cdot a_{m-1,i})x^{\underline{i}}, \end{align*} 于是有递推公式$$a_{m,i}=a_{m-1,i-1}+i\cdot a_{m-1,i},$$其中$a_{m,0}=1$.$a_{m,i}$在组合数学中被称为第二类斯特林(Stirling)数,它表示将一个$m$元有限集划分为$k$个非空子集的方法数.以$m=1,2$为例:
  • $\sum\limits_{i=0}^{n-1}i=\sum\limits_{i=0}^{n-1}i^{\underline 1}={1\over 2}n^{\underline 2}={1\over 2}n(n-1),$
  • $\sum\limits_{i=0}^{n-1}i^2=\sum\limits_{i=0}^{n-1}(i^{\underline 2}+i^{\underline 1})={1\over 3}n^{\underline 3}+{1\over 2}n^{\underline 2}={1\over 6}n(n+1)(2n+1).$

设$g=\sum\limits_{m=0}^dg_mx^m$,则 \begin{align*} \Sigma(g)&=\sum_{m=0}^dg_m(\sum_{i=0}^ma_{m,i}x^{\underline i})\\ &=\sum_{0\le i\le m\le d}g_ma_{m,i}\frac{x^{\underline{i+1}}}{i+1}, \end{align*} 因此$$\sum_{k=0}^{n-1}g(k)=\sum_{0\le i\le m\le d}g_ma_{m,i}\frac{n^{\underline{i+1}}}{i+1}.$$

回到顶部超几何级数

和多项式级数的情形一样,首先研究一元超几何单项式级数求和.

定义2 单项式级数通项$g_n$是超几何单项式,如果相邻项之比$$r(n)=\frac{g_{n+1}}{g_n}$$是关于$n$的有理函数.

  • 二项式系数$\binom{m}{n}$是超几何单项式,因为 \begin{align*} \frac{\binom{m}{n+1}}{\binom{m}{n}}&=\frac{\Gamma(m+1)\Gamma(n+1)\Gamma(m-n+1)}{\Gamma(n+2)\Gamma(m+n)\Gamma(m)}\\ &=\frac{-n+m}{n+1} \end{align*}

设$$r(n)=\frac{g_{n+1}}{g_n}=\frac{a(n)}{b(n)}\cdot \frac{c(n+1)}{c(n)},$$并且满足$\gcd(a(n),b(n+k))=1$,$\forall k\in \mathbb{N}$.设$\Delta(f)=g$,则$f_n=f_0+\sum\limits_{k=0}^{n-1}g_k$,$$\frac{f_n}{g_n}=\frac{f_n}{f_{n+1}-f_n}=\frac{1}{\frac{f_{n+1}}{f_n}-1}.$$令$y(n)=\frac{f_n}{g_n}$,则$$y(n+1)g(n+1)=f_{n+1}=(y(n)+1)g(n),$$即$r(n)y(n+1)=y(n)+1$,所以存在$x(n)\neq 0$使得$y(n)=\frac{b(n-1)}{c(n)}x(n)$,其中$$a(n)x(n+1)-b(n-1)x(n)=c(n).$$

回到顶部极大阶乘分解

极大阶乘分解(Greatest Factorial Factorization)是多项式的一种特殊分解.

定义3 设$f$为首一多项式,记$f$的极大阶乘分解为$$gff(f)=\langle f_1,\cdots,f_m\rangle,$$它满足:

  1. $f=f_1^{\underline 1}\cdots f_m^{\underline m}$.
  2. $f_1,\cdots,f_m$为首一多项式且$f_m\neq 1$.
  3. $\gcd(f_i^{\underline i},E(f_j))=1$.
  4. $\gcd(f_i^{\underline i},E^{-j}f_j)=1$,$1\le i,j\le m$.
这样定义是为了保证$$f_j^{\underline j}=f_j\cdot E^{-1}f_j\cdots E^{-j+1}f_j$$没有更小的降阶乘因子,因为如果$g=\gcd(f_i^{\underline i},E^{-j}f_j)\neq 1$,则$g^{\underline{j+1}}|f$.

根据极大阶乘分解的定义,它有很好的性质.

定理2

  1. 设$f$为首一多项式且$f\neq 0$,则$f$至多有一种极大阶乘分解.
  2. $gff(\gcd(f,E(f)))=\langle f_2,\cdots,f_m\rangle$.

回到顶部Gosper算法

在上面的讨论中,超几何单项式级数求和归结到求解超几何单项式的差分原函数.给定超几何单项式$g$,设$\sigma={E(g)\over g}$,$f=\tau\cdot g$,则 \begin{align*} \Delta(f)&=E(f)-f\\ &=E(\tau)\cdot E(g)-\tau\cdot g\\ &=(E(\tau)\cdot\sigma-\tau)g, \end{align*} 于是$$\Delta(f)=g\Leftrightarrow E(\tau)\cdot \sigma-\tau=1.$$由超几何单项式的性质可以设$\sigma={a\over b}$,$\tau={u\over v}$,其中$(a,b)=(u,v)=1$,并且$b,v$均为首一多项式,上式化为$$a\cdot v\cdot E(u)-b\cdot u\cdot E(v)=b\cdot v\cdot E(v).$$这样我们就把求解差分原函数的问题归结到求解多项式方程,理论上可以直接通过待定系数法像求解线性方程组一样解出这个方程来,但是计算量很大.

Gosper算法利用极大阶乘分解来求解这个多项式方程,记$\gcd(E(f))=\gcd(f,E(f))$,设$v_0={v\over\gcd(E(v))}$,$v_1={E(v)\over\gcd(E(v))}$,则$(v_0,v_1)=1$,方程两边同除以$\gcd(E(v))$得$$a\cdot v_0\cdot E(u)-b\cdot v_1\cdot u=b\cdot v_0\cdot v_1\cdot\gcd(E(v)),$$其中$$(u,v_0)=(E(u),v_1)=(u,v)=1,$$于是有$$v_0|b,v_1|a.$$设$gff(v)=(h_1,\cdots,h_m)$,则 \begin{align*} v_0&=\frac{h_1^{\underline 1}h_2^{\underline 2}\cdots h_m^{\underline m}}{h_2^{\underline 1}\cdots h_m^{\underline{m-1}}}\\ &=h_1\cdot E^{-1}(h_2)\cdots E^{-(m-1)}(h_m), \end{align*} \begin{align*} v_1&=\frac{E(h_1)^{\underline 1}E(h_2)^{\underline 2}\cdots E(h_m)^{\underline m}}{h_2^{\underline 1}\cdots h_m^{\underline{m-1}}}\\ &=E(h_1)\cdot E(h_2)\cdots E(h_m), \end{align*} 再由$v_0|b$,$v_1|a$可得$$h_i|E^{-1}(a),h_i|E^{i-1}(b).$$若$v\neq 1$,则 \begin{align*} 1&\neq h_m|\gcd(E^{-1}(a),E^{m-1}(b))\\ &=E^{-1}(\gcd(a(x),b(x+m))), \end{align*} 而这等价于$$res_x(a(x),b(x+y))|_{y=m}=0.$$我们可以写出求$v$的某一个倍数$V$的算法.

算法1(Gosper)

输入:$(a,b)$=1,其中$b$为首一多项式.

输出:首一多项式$V$,满足$v|V$,其中$(u,v)=1$且$$a\cdot v\cdot E(u)-b\cdot u\cdot E(v)=b\cdot v\cdot E(v).$$

  1. 设$R=res_x(a(x),b(x+y))$,$d=\max\{k\in \mathbb{N}$;$k=0$或$R(k)=0\}$.若$d=1$,输出1.
  2. 设$a_0=a$,$b_0=b$,对$i=1,2,\cdots,d$依次计算$$H_i=\gcd(E^{-1}(a_{i-1}),E^{i-1}(b_{i-1})),$$ $$a_i=\frac{a_{i-1}}{E(H_i)},b_i=\frac{b_{i-1}}{E^{-(i-1)}(H_i)}.$$
  3. 输出$H_1^{\underline 1}\cdots H_d^{\underline d}$.
不难看出$h_i|H_i$,因此$$v=h_1^{\underline 1}\cdots h_m^{\underline m}|H_1^{\underline 1}\cdots H_m^{\underline m}\cdots H_d^{\underline d}=V.$$在算法实际运行过程中,一旦$a_i=1$或$b_i=1$,可以预计$H_j=1$,其中$j=i+1,\cdots,d$,此时可以自动结束计算.

现在我们将方程化成了$$a\cdot V\cdot E(U)-b\cdot E(V)\cdot U=b\cdot V\cdot E(V),$$其中$V$为已知的首一多项式.左右同除以$g=\gcd(a\cdot V,b\cdot E(V))$,得$$r\cdot E(U)-s\cdot U=t,$$其中$r=\frac{a\cdot V}{g}$,$s=\frac{b\cdot E(V)}{g}$,$t=s\cdot V$.设$$U=U_ex^e+\cdots+U_0,$$其中$e$可以这样确定:

设$m=\max\{\deg(r)-1,\deg(s-r)\}$,$\delta$为$(s-r)$中$x^m$的系数.

  • 若$\deg(r)-1<\deg(s-r)$或$\delta\notin \mathbb{N}$,令$e=\deg(t)-m$.
  • 若$\deg(t)-m=\delta$,不可解.
  • 若$\deg(t)-m\neq \delta$,设$e=\max\{\deg(t)-m,\delta\}$,如果$e<0$,不可解.

比较对应项系数将得到一个上三角阵的线性方程组,这时就可以解出$U$来.通过这一系列手续,最终求得$$u=\frac{U}{\gcd(U,V)},v=\frac{V}{\gcd(U,V)}.$$

最后更新： 2009年01月28日 22:41:14 返回主页 / 更新记录 / 许可协议 Copyright © 2007,2008 maTHμ Project Group