Gosper's algorithm

Remarks

Check of step 3: with $y(k) = b(k-1)x(k)/c(k)$, one has $T_{k+1} - T_k = \big(y(k + 1)r(k) - y(k)\big)t_k$, and $y(k+1)r(k) - y(k) = \big(a(k)x(k+1) - b(k-1)x(k)\big)/c(k) = 1$ by step 2. Gosper's theorem says that the method is complete: if some hypergeometric $T_k$ works, then $T_k/t_k$ is rational and the equation in step 2 has a polynomial solution. Example: $t_k = k\cdot k!$ has $r(k) = (k + 1)^2/k$; take $a(k) = k + 1$, $b(k) = 1$, $c(k) = k$, which satisfy the gcd condition. The equation $(k + 1)x(k + 1) - x(k) = k$ has the solution $x = 1$, so $T_k = k!$ for $k \ge 1$, and indeed $(k + 1)! - k! = k\cdot k!$. Non-example: for $t_k = 1/(k + 1)$ the algorithm reports failure, since the partial sums are harmonic numbers, which are not a hypergeometric term. The equation of step 2 is a linear recurrence with polynomial coefficients for the unknown polynomial $x$.