By Mark van Hoeij
Posted: Feb. 28, 2024
The recursion relation in the program K(n, x) has the following polynomial solution:
P := (n-x+1)*(n-x)*(3*n^2+2*x*n+3*n+x^2+x);
(Several computer algebra systems have code to find polynomial/rational/hypergeometric solutions.)
One can construct a new recurrence L such that the solutions of L are:
the solutions of the original recurrence, divided by P.
Since the original recurrence had P among its solutions, the new recurrence L will have P/P = 1 among its solutions. We can write L in Q(x, n)[Sn] where Sn is the shift operator, which sends f(n,x) to f(n+1,x).
Saying that 1 is a solution of L is equivalent to saying that L factors like this:
L = L1 * (Sn - 1)
for some L1 in Q(x, n)[Sn] where * = composition of operators.
If u is a solution of L1, then sum(u) is a solution of L, and P * sum(u) is a solution of the original recurrence.
Here `sum(u)' refers to an expression such that if you apply Sn - 1 to it, you get u. In Maple, `sum(u)' would be something like this:
ui := subs(n=i, u);
add( ui, i=0..n-1 );
because if you apply Sn - 1 to that you get:
add(ui, i=0..n) - add(ui, i=0..n-1) = subs(i = n, ui) = u.
After computing P and u, and putting them into a program, I get a program MyK(n, x)
MyK := proc(n,x) local i;
4*(x-n-1)*(x-n)*(3*n^2+2*n*x+x^2+3*n+x) * add(i/(i^2+i*x+x^2-1)/(x-i), i=1..n)
+
n/45*(n+1)*(250*n^4-456*n^3*x-198*n^2*x^2+494*n*x^3-45*x^4+500*n^3-684*n^2*x-198*n*x^2
+247*x^3+92*n^2-2*n*x+45*x^2-158*n+113*x)/(x^3-x)
end:
for which MyK(n, x) = K(n, x) for n = 1, 2, 3,... (PS. You can make K(n,x) shorter by returning 0 at n=0, and omitting the case `elif n = 2' Then the two programs also coincide at n = 0).
However, if I try to compute MyK(n, n+1) then I get a division by zero error. The reason is because u (which turns out to be an element of Q(n, x)), if you substitute n = i and then x = n+1, then it has a pole at i = n-1. This pole is at the last point of the summation interval i = 0..n-1.
To solve this problem, suppose that v is some rational function for which sum(v) is also rational. Then sum(u) is the same as sum(v) + sum(u - v).
This way we can do a couple of things: (1) choose v to cancel out the pole at i = n-1. That produces the program MyK(n, x) in my first e-mail. But we can also do this: (2) pick v in such a way that u - v is `small'. That produces the program MyK(n, x) in my second e-mail.
As for (2), I did that in an ad-hoc manner, but there are papers with systematic algorithms to decompose a rational function u as u1 + u2 where sum(u1) is a rational function and where u2 is as small as possible.