Gosper 算法（三）

一些例子

求和式 $\displaystyle S_n(z) = \sum_{k = 0}^{n} \binom{n+k}{k}z^k$

首先还是根据常规的 Gosper 算法流程，求出

$p(n, k) = \hat{p}(n, k) = (n+1)\beta_0(n) + (n+1+k)\beta_1(n)$

$\overline{t}(n, k) = t(n, k) / (n+1) = \displaystyle \frac{(n+k)!z^k}{k!(n+1)!}$

$q(n, k) = (n+1+k)z$
$r(n, k) = k$

注意到 $\text{deg}(q-r) = \text{deg}(q+r)$，那么 $s(n, k)$ 的次数 $d$ 为
$d = \text{deg}(\hat{p}) - \text{deg}(q-r) = 0$

这样我们就有
$\beta_0(n) = 1, \ \beta_1(n) = z-1, \ s(n, k) = 1$

这样一来就可以求出

$\beta_0(n)t(n, k) + \beta_1(n)t(n+1, k) = T(n, k+1) - T(n, k)$
从而 $t(n, k) + (z-1) t(n+1, k) = T(n, k+1) - T(n, k)$

其中 $T(n, k) = r(n, k) s(n, k) \overline{t}(n, k) = \displaystyle \binom{n+k}{k-1}z^k$

对 $k$ 求和，$\displaystyle \sum_{k = 0}^{n+1}$，求和到第 $n+1$ 项，这样多出来一项 $t(n, n+1)$

记 $S_n(z) = \displaystyle \sum_{k=0}^{n} t(n, k)$

$S_n(z) + t(n, n+1) + (z-1) S_{n+1}(z) = T(n, n+2) - T(n, 0)$

$\quad = \displaystyle \binom{2n+2}{n+1}z^{n+2} = 2\binom{2n+1}{n}z^{n+2}$

另外 $\displaystyle t(n, n+1) = \binom{2n+1}{n+1}z^{n+1} = \binom{2n+1}{n}z^{n+1}$

$S_{n+1}(z) = \displaystyle \frac{1}{1-z} \left(S_n(z) + (1-2z)\binom{2n+1}{n}z^{n+1}\right)$

我们立即有

$\displaystyle S_{n+1}\left(\frac{1}{2} \right) = 2S_n \left(\frac{1}{2} \right)$，另外还可以如下化简

两边同时乘以 $(1-z)^{n+1}$ 并且作代换 $n \leftarrow n+1$ 有

$\displaystyle (1-z)^n S_n(z) = (1-z)^{n-1} S_{n-1}(z) + (1-2z)(1-z)^{n-1} \binom{2n-1}{n} z^n$

实际上就是

$\displaystyle (1-z)^n S_n(z) = (1-z)^{n-1} S_{n-1}(z) + \frac{1-2z}{1-z} \binom{2n-1}{n} \left((1-z)z \right)^n$

令 $F(n) = (1-z)^n S_n(z)$，从而

$\displaystyle F(n) - F(0) = \frac{1-2z}{1-z} \sum_{k = 1}^{n} \binom{2k-1}{k} ((1-z)z)^k$，其中 $F(0) = 1$

这样就得到一个不可思议的封闭形式

$\displaystyle (1-z)^n \sum_{k = 0}^{n} \binom{n+k}{k}z^k = 1+ \frac{1-2z}{2-2z} \sum_{k = 1}^{n} \binom{2k}{k} \left(z(1-z) \right)^k$

一些例子2

$\displaystyle t(n, k) = \binom{n-k}{k}z^k$

$\displaystyle p(n, k) = \hat{p}(n, k) = (n+1-2k)\beta_0(n) + (n+1-k)\beta_1(n)$
$\overline{t}(n, k) = t(n, k) / (n+1-2k) = (n-k)!z^k / k!(n+1-2k)!$
$q(n, k) = (n+1-2k)(n-2k)z$
$r(n, k) = (n+1-k)k$

另外注意到

$\displaystyle S_n(-\frac{1}{4}) = \frac{1}{2^{n+1}} \left(\frac{(1+\sqrt{1+4z}) ^ {n+1} - (1-\sqrt{1+4z}) ^ {n+1} }{\sqrt{1+4z}} \right)$

括号内的部分可以划归成

$\displaystyle \quad = \frac{2\binom{n+1}{1} \sqrt{1+4z} + 2 \binom{n+1}{3} (\sqrt{1+4z})^3 + \cdots}{\sqrt{1-4z}}$

由此 $S_n(\displaystyle -\frac{1}{4}) = \frac{2(n+1)}{2^{n+1}} = \frac{n+1}{2^n}$

注意到如果 $z \neq \displaystyle -\frac{1}{4}$，那么 $\text{deg}(q-r) = \text{deg}(q+r) = 2$

那么 $\text{deg}(\hat{p}) - \text{deg}(q-r) = -1$，那么此时考虑二阶递推

$\hat{t}(n, k) = \beta_0(n)t(n, k) + \beta_1(n)t(n+1, k) + \beta_2(n)t(n+2, k)$

$p(n, k) = \hat{p}(n, k) = (n+1-2k)(n+2-2k)\beta_0(n)$
$\quad \quad + (n+1-k)(n+2-2k)\beta_1(n)$
$\quad \quad + (n+1-k)(n+2-k)\beta_2(n)$

$\displaystyle \overline{t}(n, k) = t(n, k) / (n+1-2k)(n+2-2k) = \frac{(n-k)!z^k}{k!(n+2-2k)!}$

$q(n, k) = (n+2-2k)(n+1-2k)z$
$r(n, k) = (n+1-k)k$

这样 $\text{deg}(\hat{p}) - \text{deg}(q-r) = 0$，也就是说 $s(n, k) = \alpha_0(n)$

$\displaystyle z\alpha_0 = \beta_0 + \beta_1 + \beta_2$
$4z + \alpha_0 = 4\beta_0 + 2\beta_1 + \beta_2$
$2(2n+3)z\alpha_0 + (n+1)\alpha_0 = 2(2n+3)\beta_0 + (3n+4)\beta_1 + (2n+3) \beta_2$

可以推出一个解为

$\beta_0(n) = z, \quad \beta_1(n) = 1, \quad \beta_2(n) = -1, \quad \alpha_0(n) = 1$

$zt(n, k) + t(n+1, k) - t(n+2, k) = T(n,k+1)-T(n,k)$

其中 $T(n, k) = r(n, k)s(n, k)\overline{t}(n, k) = \displaystyle \binom{n+1-k}{k-1}z^k$

方程两边同时对 $k \in [0 \to n]$ 求和

$\displaystyle zS_n(z) + \left(S_{n+1}(z) - \binom{0}{n+1}z^{n+1} \right) - \left(S_{n+2}(z) - \binom{0}{n+2}z^{n+2} - \binom{1}{n+1}z^{n+1} \right)$
$\quad \quad \displaystyle = T(n, n+1) - T(n, 0)$

又因为对所有 $n \geqslant 0$ 都有 $\displaystyle \binom{1}{n+1}z^{n+1} = \binom{0}{n}z^{n+1} = T(n, n+1)$
$T(n, 0) = 0$

综上所述我们有

$\displaystyle S_{n+2}(z) = S_{n+1}(z) + zS_n(z), \quad n \geqslant 0$

一些例子3

1978 年，法国数学家证明了 $\displaystyle \zeta(3) = 1 + \frac{1}{2^3} + \frac{1}{3^3} + \frac{1}{4^3} + \cdots$ 是无理数

其中用到一个重要的递推包括一个二项和

$\displaystyle A_n = \sum_k\binom{n}{k}^2 \binom{n+k}{k}^2$

首先我们尝试 $\beta_0(n), \beta_1(n)$，最后得到

$(n+1-k)^2 \beta_0(n) + (n+1+k)^2 \beta_1(n) = (n+k+1)^2(n-k+1)^2\alpha_0(n) - k^4\alpha_0(n)$

发现无可行解 $\beta_0(n), \beta_1(n)$，所以考虑使用 $\beta_2(n)$

$\displaystyle p(n, k) = (n+1-k)^2(n+2-k)^2\beta_0(n)$
$\quad + (n+1+k)^2(n+2-k)^2 \beta_1(n)$
$\quad + (n+1+k)^2(n+2+k)^2 \beta_2(n) = \hat{p}(n, k)$

$\displaystyle\overline{t}(n, k) = \frac{t(n, k)}{(n+1-k)^2(n+2-k)^2} = \frac{(n+k)!^2}{k!^4(n+2-k)!^2}$

$q(n, k) = (n+1+k)^2(n+2-k)^2$
$r(n, k) = k^4$

注意到这里 $q$ 有因子 $(k+n+1)$，对应 $(k+\alpha)\Rightarrow \alpha = n+1$
而 $r$ 有因子 $k$，对应 $(k+\beta)\Rightarrow \beta = 0$，本来有 $\alpha - \beta = n+1 > 0$
这本来是不满足 $\alpha - \beta$ 不是正整数这个条件的
但是这里我们把 $n$ 看作参数，所以符合 Gosper 算法条件

注意到 $q(n, k) - r(n, k) = -2k^3 + \cdots$，$q+r = 2k^4 + \cdots$
$d = \text{deg}(\hat{p}) - \text{deg}(q+r) + 1 = 4-4+1 = 1$
但是我们尝试了 $\beta_0(n), \beta_1(n)$ 失败了，所以转到二阶递推

此时不存在 $\beta_0(n), \beta_1(n)$ 不全为 $0$ 的解，应该考虑 Gosper 算法中下一步

令 $d = -2\lambda' / \lambda$，其中 $\lambda$ 是 $q+r$ 的最高次幂 $k^{d_R} = k^4$ 的系数 $2$
$\lambda'$ 是 $q-r$ 中 $k^3$ 的系数 $-2$

所以取 $s(n, k)$ 的最高幂为 $d = 2$

$\displaystyle s(n, k) = \alpha_2(n)k^2 + \alpha_1(n)k + \alpha_0(n)$

求解该方程比较复杂，大致步骤如下
$(n+1-k)^2(n+2-k)^2\beta_0(n) + (n+1+k)^2(n+2-k)^2 \beta_1(n) + (n+k+1)^2(n+k+2)^2\beta_2(n)$
$\quad = \left(k^4 - 2k^3 + ((n+1)^2 + (n+2)^2 - 4(n+1)(n+2))k^2 + 2(n+1)(n+2)k + (n+1)^2(n+2)^2 \right)$
$\quad \quad \cdot (\alpha_2 k^2 + (2\alpha_2 + \alpha_1)k + (\alpha_2 + \alpha_1 + \alpha_0))$
$\quad \quad - k^4(\alpha_2 k^2 + \alpha_1 k + \alpha_0)$

$[k^0]: \quad \beta_0 + \beta_1 + \beta_2 - \alpha_1 - \alpha_2 - \alpha_0 = 0$
$[k^4]: \quad \beta_0 + \beta_1 + \beta_2 + \alpha_1 + (2n^2 + 6n + 6)\alpha_2 = 0$
$[k^3]: \quad (-4n-6)\beta_0 - 2\beta_1 + (4n+6)\beta_2 = -2\alpha_0 - (2n^2 + 6n + 5)\alpha_1 - (2n^2 + 6n + 4)\alpha_2$
$[k^2]: \quad (6n^2 + 18n + 13)\beta_0 - (2n^2 + 6n + 3)\beta_1 + (6n^2 + 18n + 13)\beta_2$
$\quad \quad \quad \quad = (-2n^2 - 6n -3)\alpha_0 + \alpha_1 + (n^4 + 6n^3 + 15n^2 + 18n + 9)\alpha_2$
$[k] : \quad -2(n+1)(n+2)(2n+3)\beta_0 + 2(n+1)(n+2)\beta_1 + 2(n+1)(n+2)(2n+3)\beta_2$
$\quad \quad \quad \quad = (n+1)(n+2) \left(2\alpha_0 + (2+(n+1)(n+2))\alpha_1 + (2(n+1)(n+2) + 2)\alpha_2 \right)$

首先从 $[k], [k^0]$ 的表达式推出
$\alpha_0, \alpha_1, \alpha_2$ 均有 $(2n+3)$ 因子
并且 $\beta_1$ 中有 $(2n+3)$ 因子，$(\beta_0 + \beta_2)$ 中也一定有因子 $(2n+3)$

除去 $(2n+3)$ 因子后的多项式记为 $\alpha'$
那么根据 $[k^3], [k^1]$ 表达式

$-2\beta_0 - 2\beta_1' + 2\beta_2 = -2\alpha_0' - (2n^2 + 6n + 5)\alpha_1' - (2n^2 + 6n + 4) \alpha_2'$
$-2\beta_0 + 2\beta_1' + 2\beta_2 = 2\alpha_0' + (n^2 + 3n + 4)\alpha_1' + (2n^2 + 6n + 6)\alpha_2'$

$4\beta_1' = 4\alpha_0' + (3n^2 + 9n +9)\alpha_1' + (4n^2 + 12n + 10)\alpha_2'$，同时除去因子 $4$

$\alpha \xrightarrow{(2n+3)} \alpha' \xrightarrow{4} \alpha''$
$\beta_1' = \alpha_0' + (3n^2 + 9n + 9)\alpha_1'' + (4n^2 + 12n + 10)\alpha_2''$

从 $[k^0], [k^4]$ 表达式推出
$\displaystyle 2\alpha_1 + (2n^2 + 6n + 7)\alpha_2 + \alpha_0 = 0$，又根据 $[k^3],[k]$ 的结论
可以推出 $\alpha_1', \alpha_0', \alpha_2'$ 均有因子 $4$

从而 $\alpha_2' \xrightarrow{4} \alpha_2''$ 表示从 $\alpha_2'$ 中除去因子 $4$ 得到 $\alpha_2''$
$(2n^2 + 6n + 7)\alpha_2'' = -\alpha_0'' - 2\alpha_1''$

这样就可以取 $\alpha_2'' = 2$，方程左边 $4n^2 + 12n + 14 = 4(n^2 + 3n + 2) + 6 = 4(n+1)(n+2) + 6$
这样拼凑的原因是尽可能去构造 $(2n + 3)$

这样我们就可以有
$\alpha_2 = 2 \cdot 4 \cdot (2n + 3) = 8(2n + 3)$
$\alpha_0 = -4(n+1)(n+2) \cdot 4 \cdot (2n + 3) = -16(n+1)(n+2)(2n + 3)$
$\alpha_1 = -3 \cdot 4 \cdot (2n + 3) = -12(2n + 3)$

这样代入 $[k^3], [k]$ 推出的表达式，可以有
$\beta_1' = -16(n+1)(n+2) + (-3)\cdot (3n^2 + 9n + 9) + 2(4n^2 + 12n + 10)$
$\quad = -17n^2 -51n - 39$

从而 $\beta_1 = -(2n + 3)(17n^2 + 51n + 39)$

因为 $\beta_0 + \beta_2$ 中也有 $(2n + 3)$ 因子，可以考虑 $\beta' = \displaystyle \frac{\beta_0 + \beta_2}{2n + 3}$

对于 $[k^2]$ 可以有
$(6n^2 + 18n + 13)\beta' = 6n^4 + 36n^3 + 85n^2 + 93n + 39$，执行多项式除法
$\beta' = (n^2 + 3n + 3)$

同时根据 $[k^0]$ 我们也有
$\beta' = \alpha_0' + \alpha_1' + \alpha_2' - \beta_1'$
$\quad = (17n^2 + 51n + 39) - 16(n+1)(n+2) + 8 - 12 = n^2 + 3n + 3$

从而我们有 $\beta_0 + \beta_1 = (2n + 3)(n^2+3n + 3)$
而 $(2n+3)(n^2 + 3n + 3) = (n+1)^3 + (n+2)^3$
从而我们有 $\beta_0 = (n+1)^3, \beta_2 = (n+2)^3$

综上所述

$\beta_0(n) = (n+1)^3$
$\beta_1(n) = -(2n + 3)(17n^2 + 51n + 39)$
$\beta_2(n) = (n+2)^3$
$\alpha_0(n) = -16(n+1)(n+2)(2n + 3)$
$\alpha_1(n) = -12(2n + 3)$
$\alpha_2(n) = 8(2n + 3)$

由此应用 Gosper 算法求解结果为

$(n+1)^3 t(n, k) - (2n + 3)(17n^2 + 51n + 39)t(n+1, k)$
$\quad + (n+2)^3 t(n+2, k) = T(n, k+1) -T(n, k)$

其中
$T(n, k) = k^4 s(n, k) \overline{t}(n, k)$
$\displaystyle\quad = (2n + 3)\left(8k^2 - 12k -16(n+1)(n+2) \right)(n+k)!^2 \frac{1}{(k-1)!^4 (n+2-k)!^2}$

关于 $k$ 求和，就得到了一个不可思议的递归式

$(n+1)^3 A_n + (n+2)^3 A_{n+2} = (2n+3)(17n^2 + 51n + 39)A_{n+1}$

Gosper 算法其他讨论

对于 Gosper 算法，我们研究其正常项，即能够表示成

$\displaystyle t(n, k) = f(n, k) \frac{ (a_1n + a_1'k +a_1'')! \cdots (a_p n + a_p' k + a_p'')! }{(b_1n + b_1'k + b_1'')!\cdots (b_qn + b_q'k + b_q'')!} w^n z^k$

形式的项

只要 $t(n, k)$ 是一个正常项，就存在不全为 $0$ 的多项式 $\left<\beta_0(n), \cdots, \beta_l(n) \right>$ 以及正常项 $T(n, k)$

使得 $\beta_0(n) t(n, k) + \cdots + \beta_l(n)t(n+l, k) = T(n, k+1) - T(n, k)$

必要性

用算子方法，设 $N$ 是使得 $n$ 增加 $1$ 的算子，$K$ 是使得 $k$ 增加 $1$ 的算子
举例来说 $N^2 K^3 t(n, k) = t(n+2, n+3)$，这样可以构造一个关于 $N, K, n$ 的线性差分算子

$\displaystyle H(N, K, n) = \sum_{i = 0}^{I} \sum_{j = 0}^{J} \alpha_{i, j} (n) N^i K^j$

对于算子多项式，很显然如果 $t(n, k)$ 是一个正常项，那么 $H(N, K, n)t(n, k)$ 也是一个正常项

下面考虑构造，我们在计算 $t(n, k) \to \overline{t}(n, k)$ 的时候

$\displaystyle \frac{t(n+I, k)}{t(n, k)} = \frac{\hat{p}(n, k)}{(b_1n + b_1I)\cdots}$，从而

$\displaystyle \overline{t}(n, k) = \frac{1}{(b_1n + b_1I)\cdots} t(n, k)$

注意到如果分母有形式 $(\alpha - |a_1|n)$，那么我们有

$\displaystyle \frac{t(n+1, k)}{t(n, k)} = \frac{(\alpha - |a_1|n - |a_1|I)\cdots}{(b_1n + b_1I)\cdots }$

综上所述，可以定义一个基础项

$\displaystyle \overline{t}(n, k)_{I, J} = \frac{\prod_{i = 1}^{p} \left(a_in + a_i'k + a_i I[a_i < 0] + a_i'J[a_i < 0] + a_i''\right)!}{\left(b_in + b_i'k + b_i I[b_i > 0] + b_i'J[b_i'> 0] + b_i''\right)!} w^n z^k$

比如说 $t(n, k) = \displaystyle \binom{n-2k}{k} = \frac{(n-2k)!}{k!(n-3k)!}$，那么对应的基础项

$\displaystyle \overline{t}(n, k)_{I, J} = \frac{(n-2k-2J)!}{(k+J)!(n-3k+I)!}$

这样构造，对于 $0 \leqslant i \leqslant I$ 并且 $0 \leqslant j \leqslant J$
$\displaystyle \alpha_{i, j}(n) N^i K^j t(n, k)$ 就等于 $\overline{t}(n, k)_{I, J}$ 乘上一个关于 $n, k$ 的多项式
多项式的有限和式仍为多项式，所以 $H(N, K, n)t(n, k)$ 有对应的形式

充分性

尝试证明只要 $t(n, k)$ 是正常项，就总是存在一个非零的线性差分算子 $H(N, K, n)$ 使得
$H(N, K, n)t(n, k) = 0$

如果 $0 \leqslant i \leqslant I$ 并且 $0 \leqslant j \leqslant J$，平移之后的项 $A(n, k) = N^i K^j t(n, k) = f(n, k) \cdot \overline{t}(n, k)_{I, J}$

观察 $\overline{t}(n, k)$ 的分子，注意到分子的最高次幂是

$\text{maxdeg}\left((a_in + a_i'k + a_i I[a_i < 0] + a_i'J[a_i'<0] + a_i'')! \right)$

最坏情况下，有 $|a_i|I + |a_i'|J$ 个项相乘，所以 $\text{maxdeg}(k) = |a_i|I + |a_i'|J$

所以 $A(n, k)$ 关于变量 $k$ 的次数最多是

$D_{I,J} = \text{deg}(f) + |a_1|I + |a_1'|J + \cdots + |a_p|I + |a_p'|J$
$\quad \quad + |b_1|I + |b_1'|J + \cdots + |b_q|I + |b_q'|J$

注意到 $H(N, K, n) = \displaystyle \sum_{i = 0}^{I} \sum_{j = 0}^{J}$ 能够构造出 $(I+1)(J+1)$ 个 $\alpha_{i,j}(n)$

那么我们能够有 $(I+1)(J+1)$ 个变量 $\alpha_{i, j}(n)$，有 $D_{I, J} + 1$ 个齐次线性方程
让 $n$ 的幂指对应的系数从 $[0, D_{I, J}]$ 依次相等，我们就可以求解出 $H$

只要使得 $(I+1)(J+1) > D_{I, J} + 1$，就可以

可以选取足够大的 $I, J$，这不难做到，比如说

$I = 2A' + 1, \quad J = 2A + \text{deg}(f)$
其中
$A = |a_1| + \cdots + |a_p| + |b_1| + \cdots + |b_q|$
$A' = |a_1'| + \cdots + |a_p'| + |b_1'| + \cdots + |b_q'|$

证明几乎快完成了

考虑从 $H(N, K, n)t(n, k) = 0$ 过渡到相应的解
假设 $H$ 是使得 $K$ 有可能的最小次数

$H(N, K, n)$ 看作是关于 $K$ 的一个多项式，我们有

$H(N, K, n) = H(N, 1+(K-1), n) = H(N, 1, n) - (K-1)G(N, K, n)$
其中 $G(N, K, n)$ 是一个线性差分算子

根据 $H(N, K, n)t(n, k) = 0$，代入

$H(N, 1, n)t(n, k) = (K-1)G(N, K, n)t(n, k)$
注意到如果令 $G(N, K, n)t(n, k) = T(n, k)$，那么 $KG(N, K, n)t(n, k) = T(n, k+1)$

从而 $H(N, 1, n)t(n, k) = T(n, k+1) - T(n, k)$

注意到 $H(N, 1, n)$ 与 $k$ 无关，所以可以写成
$H(N, 1, n) = \beta_0(n) + \beta_1(n)N + \cdots + \beta_l(n) N^l$

那么必然满足
$\beta_0(n) + \beta_1(n)N + \cdots + \beta_l(n) N^l = T(n, k+1) - T(n, k)$
所以 $T(n, k)$ 是一个正常项

接下来只需要检验
$H(N, 1, n)$ 并非简单的零算子即可
假设它是一个零算子，那么 $T(n, k+1) - T(n, k) = 0$，所以 $T(n, k)$ 与 $k$ 无关
于是就存在 $\beta_0(n), \beta_1(n)$，使得
$\left( \beta_0(n) + \beta_1(n)N \right) T(n, k) = 0$

但如果这样，我们之前记 $T(n, k) = G(N, K, n)t(n, k)$
那么 $\left( \beta_0(n) + \beta_1(n)N \right) G(N, K, n)\cdot t(n, k) = 0$

于是 $\left( \beta_0(n) + \beta_1(n)N \right) G(N, K, n)$ 也是一个线性差分算子
使得 $t(n, k)$ 变为 $0$，但注意到
$H(N, K, n) = H(N, 1, n) - (K-1)G(N, K, n)$，$G(N, K, n)$ 的次数为 $J-1$
这与 $J$ 的最小性矛盾，证明完毕