• Given a hypergeometric function $F(n, k)$, we want to find a recurrence that $F(n, k)$satisfies.
• Crucially, we want a recurrence with coefficients in $n$, but not in $k$.
• So the recurrence eqn comes from the right $\mathbb Q[n, n^{-1}, S_n, S_k]$ where $S_n(F) \equiv \lambda n, k. F(n + 1, k)$, and $S_k(F) \equiv \lambda n, k. F(n, k + 1)$ (shift operators).
• The algorithm is to guess a length of the recurrence, then write the equation e.g. $a[0][0]F(n, k) + a[0][1] F(n + 1, k) + a[1][0] F(n, k + 1) + a[1][1] F(n + 1, k + 1) = 0$.
• We set the recurrence to zero, which gives us a polynomial of the form $p_0(n, \vec a) k^0 + p_1(n, \vec a) k^1 + \dots p_D(n, \vec a) k^d = 0$.
• This gives a system of equations $p_i(n, \vec a) = 0$.
• We write this as $M(n) \cdot \vec a = 0$ with coefficients for $M(n)$ in the ring $\mathbb Q[n, n^{-1}]$.
• This system is solved (can be, since $\mathbb Q[n, n^{-1}]$ is a field!) giving us solutions for $\vec a$.

§ Example: rising factorial

• suppose $F(n, k) = (n + 0) (n + 1) \dots (n + k - 1)$.
• Let's guess a recurrence of the form $a[0][0] F(n, k) + a[0][1] F(n + 1, k) + a[1][0] F(n, k + 1) + a[1][1] F(n + 1, k + 1) = 0$.
• Rewrite to $a[0][0] + a[0][1] F(n + 1, k) / F(n, k) + a[1][0] F(n, k + 1) / F(n, k) + a[1][1] F(n + 1, k + 1) / F(n, k) = 0$.
• To evaluate $F(n + 1, k) / F(n, k)$, let's estimate with $n = 4, k = 3$. This gives $(4 \cdot 5 \cdot 6 \cdot 7) / (3 \cdot 4 \cdot 5 \cdot 6) = 7 / 3 = (n + k) / n$.
• To evaluate $F(n, k + 1) / F(n, k)$, let's estimate with $n = 4, k = 3$. This gives $(4 \cdot 5 \cdot 6 \cdot 7) / (4 \cdot 5 \cdot 6) = n + k$
• To evaluate $F(n + 1, k + 1) / F(n, k)$, let's estimate with $n = 4, k = 3$. This gives $(5 \cdot 6 \cdot 7 \cdot 8)/(4 \cdot 5 \cdot 6) = 7 \cdot 8 / 4 = (n + k) (n + k + 1) / n$
• See that this gives us a $k^2a[1][1]$ term, and no other term contributes a $k^2$, so $a[1][1] = 0$.
• So we only need to solve the recurrence with $a[0][0], a[0][1], a[1][0]$.