- 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)$.

- 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
```

- 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.

- substituting in the above eqn, we get:

$\begin{aligned}
s(k) &= \frac{p(k)}{q(k)} frac{S(k)}{f(k)} \\
&= \frac{p(k)}{q(k)} \frac{S(k)}{(S(k) - S(k - 1)} \\
&= \frac{p(k)}{q(k)} \frac{1}{(1 - (S(k - 1)/S(k))} \\
\end{aligned}$

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

$\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?

- 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.