§ Gosper's algorithm

• Given a hypergeometric function $a(n)$, gosper's algorithm finds the function $S(k) = \sum_{i=0}^k f(k)$, iff $S$ is hypergeometric.
• Suppose $S(k)/S(k-1)$ is a rational function of $k$.
• Then $f(k) / f(k - 1) = (S(k) - S(k - 1))/(S(k - 1) - S(k - 2)$, which equals $(S(k)/S(k - 1) - 1)/(1 - S(k-2)/S(k-1))$ which is also a rational function.
• Thus, we want to expression $f(k)/f(k - 1) = q(k) / r(k)$.
• However, we give ourselves a "fudge factor" of the form $f(k) / f(k - 1) = p(k)/p(k - 1) \cdot q(k)/r(k)$.

§ Step 1: p, q, r decomposition

• We try to impose a condition on $q(k), r(k)$ that we impose using $p(k)$, which states: $\forall a, b, (k + a) \| q(k) \land (k + b) \| r(k) \implies a < b$.
• For example, if we have $(x - 100) / (x - 1)$, then $a = -100$ is less than $b = 1$, which satisfies the condition.
• We claim that this is always possible to achieve:

# f(k)/f(k-1) = (a1+k)(a2+k)..(am+k)z/(b1+k)(b2+k)...(bn+k)
p = 1
q = (a1+k)(a2+k)..(am+k)
r = (b1+k)(b2+k)...(bn+k)

while exists a, b such that q % (k + a) = 0 and r % (k + b) = 0:
  N = a - b
  if N < 0: break
  # N nonnegative, so a >= b.
  q = q / (k + a); r = r / (k + b);
  fudge = falling_factorial(k + a, N)
  # so 'fudge(k) = (k + a) (k + a - 1) ... (k + b + 1)'
  # see that 't(k) / t(k - 1) = (k + a) / (k + b)',
  # which is exactly what we cancelled from p, q.
  p = p * t

§ Step 2: The secret function s(k)

• We assume that $f(k) = S(k) - S(k - 1)$.
• We now write $S(k) = q(k + 1)/p(k) \cdot s(k) f(k)$ for some secret function $s(k)$ to be found.

§ $s(k)$ is a rational function iff $S(k)$ is

• substituting in the above eqn, we get:

• This tells us that $s(k)$ is a rational function whenever $S(k)$ is.

§ Recurrence of $s(k)$

Substituting $S(k) = q(k + 1)/p(k) \cdot s(k) f(k)$ into $f(k) = S(k) - S(k - 1)$, we get:

$$\begin{aligned} f(k) &= \frac{q(k+1)}{p(k)}s(k)f(k) - \frac{q(k)}{p(k-1)}s(k-1)f(k-1) \\ \frac{p(k)}{f(k)} f(k) &= \frac{p(k)}{f(k)} \frac{q(k+1)}{p(k)}s(k)f(k) - \frac{p(k)}{f(k)} \frac{q(k)}{p(k-1)}s(k-1)f(k-1) \\ \dots p(k) = q(k + 1)s(k) - r(k) s(k - 1) \end{aligned}$$

• TODO: What does this recurrence mean for GP?

§ Step 3: $s(k)$ is polynomial iff $S(k)$ is a rational function

• We already know that $s(k)$ is a rational function.
• For contradiction, assume $s(k) = u(k) / v(k)$ where $v(k) \neq 1$, $gcd(u(k), v(k)) = 1$ for contradiction.
• let $N$ be the largest natural such that $(k + \beta)$ and $(k + \beta + N)$ both occur as factors for $v(k)$ ( $\beta \in \mathbb C$). See that $N$ always exists because $N = 0$ exists.
• Substituting into the definition of $p(k)$ in terms of $q(k), r(k), s(k)$, we get:

$$\begin{aligned} p(k) &= q(k + 1)s(k) - r(k) s(k - 1) \\ p(k) &= q(k + 1)u(k)/v(k) - r(k) u(k - 1)/v(k-1) \\ p(k)v(k)v(k-1) &= q(k + 1)u(k)v(k-1) - r(k) u(k - 1)v(k) \\ \end{aligned}$$

• We know that $v$ can be made zero if its argument equals $\beta$, and $beta + N$, so we perform the followig assignments:
• First set $k - 1 = -\beta$ (so $v(k-1) = 0$):

$$\begin{aligned} p(k)v(k)(v(k-1) \sim 0) &= q(k + 1)u(k)(v(k-1) \sim 0) - r(k) u(k - 1)v(k) \\ 0 &= - r(k) u(k - 1)v(k) \\ 0 &= r(-\beta + 1) u(-\beta)v(-\beta + 1) \end{aligned}$$

• Next set $k = -\beta - N$ (so $v(k) = 0$):

$$\begin{aligned} p(k)(v(k) \sim 0)v(k-1) &= q(k + 1)u(k)v(k-1) - r(k) u(k - 1)(v(k) \sim 0) \\ 0 &= q(k+1)u(k)v(k - 1) \\ 0 &= q(-\beta - N +1)u(-\beta - N)v(-\beta -N - 1) \end{aligned}$$

• Now, we must have that $u(-beta) \neq 0$, and $u(-\beta -N) \neq 0$, since $(u, v)$ have no common factors.
• Also, $v(-\beta + 1) \neq 0$ and $v(-\beta -N - 1) \neq 0$, because $v(k)$ would otherwise have a factor of $k + \beta + N + 1$ or $k + \beta - 1$, which contradicts the maximality of $N$ (??? what does this even mean?)
• Thus, we must have $r(-\beta + 1) = 0 = q(-\beta - N + 1)$.
• But this contradicts condition (3).
• Hence, $s(k)$ is a polynomial.
• WTF is this proof? I see no moral of the story.

§ Step 4: finding $s(k)$ given $p, q, r$

§ References

• A = B.
• Concrete Mathematics.
• BA thesis by Richard B. Reeves: gosper's algorithm - a decision procedure for partial hypergeometric sums.
• Algorithm hyper lecture notes