#CHALLENGE (by Doron Zeilberger) TO THE DIFFERENCE EQUATION PEOPLE
#Let K(n,x) be the sequence defined below in Maple notation. It is a certain SECOND-ORDER Linear recurrence
#with polynomial coefficients in the discrete variable n and the parameter x.
#Try to "solve" it in some sense and prove (rigorously) that
#K(n-1,n)=n(n+1)^2

#I WILL DONATE $100 to the OEIS in HONOR of the first PROVER(S)

#UPDATE Feb, 28, 2024: Mark van Hoeij met this challenge. A donation of $100 to the OEIS in his honor has been made.

K:=proc(n,x) option remember:
if n=1 then
 2/15*(15*x^3+262*x^2+115*x-588)/(x+1)/x:
elif n=2 then
 2/15*(45*x^6+1325*x^5+1372*x^4-10076*x^3-8557*x^2+1599*x+33876)/(x^2+2*x+3)/x/(x+1)/(x-1):
else
normal(
(500*n^13-456*n^12*x-196*n^11*x^2-1706*n^10*x^3+1726*n^9*x^4+946*n^8
*x^5+1402*n^7*x^6-2084*n^6*x^7-1304*n^5*x^8-226*n^4*x^9+814*n^3*x^10+554*n^2*x^
11+30*n*x^12-3250*n^12+2736*n^11*x+1078*n^10*x^2+8530*n^9*x^3-7767*n^8*x^4-3784
*n^7*x^5-4907*n^6*x^6+6252*n^5*x^7+3260*n^4*x^8+452*n^3*x^9-1221*n^2*x^10-554*n
*x^11-15*x^12+6000*n^11-3996*n^10*x-4480*n^9*x^2-12635*n^8*x^3+9184*n^7*x^4+
10758*n^6*x^5+7519*n^5*x^6-6275*n^4*x^7-6810*n^3*x^8-4124*n^2*x^9+547*n*x^10+
262*x^11+2750*n^10-5100*n^9*x+12075*n^8*x^2-640*n^7*x^3+4102*n^6*x^4-19030*n^5*
x^5-6530*n^4*x^6+2130*n^3*x^7+6955*n^2*x^8+3898*n*x^9-70*x^10-19000*n^9+15517*n
^8*x-13586*n^7*x^2+10746*n^6*x^3-14138*n^5*x^4+16200*n^4*x^5+12799*n^3*x^6+7957
*n^2*x^7-2701*n*x^8-1374*x^9+11250*n^8-1372*n^7*x-1253*n^6*x^2+5828*n^5*x^3+
6967*n^4*x^4-5098*n^3*x^5-15122*n^2*x^6-7980*n*x^7+300*x^8+16000*n^7-17938*n^6*
x+13177*n^5*x^2-16440*n^4*x^3-9334*n^3*x^4-6474*n^2*x^5+5499*n*x^6+2550*x^7-\
17750*n^6+7100*n^5*x-7025*n^4*x^2+5360*n^3*x^3+14263*n^2*x^4+6482*n*x^5-330*x^6
-1500*n^5+7589*n^4*x+3227*n^3*x^2+2803*n^2*x^3-5233*n*x^4-2026*x^5+7000*n^4-\
3364*n^3*x-4875*n^2*x^2-1846*n*x^3+115*x^4-2000*n^3-716*n^2*x+1858*n*x^2+588*x^
3)/(n-1)/(n-1-x)/(n^2+n*x+x^2-1)/(250*n^9-228*n^8*x-98*n^7*x^2-603*n^6*x^3+635*
n^5*x^4+375*n^4*x^5+98*n^3*x^6-407*n^2*x^7-277*n*x^8-15*x^9-2250*n^8+1824*n^7*x
+686*n^6*x^2+3618*n^5*x^3-3175*n^4*x^4-1500*n^3*x^5-294*n^2*x^6+814*n*x^7+277*x
^8+8250*n^7-5521*n^6*x-2693*n^5*x^2-8410*n^4*x^3+5715*n^3*x^4+2885*n^2*x^5+946*
n*x^6-362*x^7-15750*n^6+7590*n^5*x+6605*n^4*x^2+9520*n^3*x^3-4445*n^2*x^4-2770*
n*x^5-750*x^6+16500*n^5-4057*n^4*x-9145*n^3*x^2-5870*n^2*x^3+797*n*x^4+965*x^5-\
9000*n^4-324*n^3*x+6503*n^2*x^2+2348*n*x^3+473*x^4+2000*n^3+716*n^2*x-1858*n*x^
2-588*x^3)*K(n-1,x)
-n*(n-x)*(250*n^9-228*n^8*x-98*n^7*x^2-603*n^6*x^3+635*n^5*x^4+375*n
^4*x^5+98*n^3*x^6-407*n^2*x^7-277*n*x^8-15*x^9-750*n^7+863*n^6*x-635*n^5*x^2+
635*n^4*x^3-635*n^3*x^4+635*n^2*x^5+652*n*x^6+45*x^7+750*n^5-1042*n^4*x+635*n^3
*x^2-635*n^2*x^3-473*n*x^4-45*x^5-250*n^3+407*n^2*x+98*n*x^2+15*x^3)*(n^2+n*x+x
^2-2*n-x)/(n-1)/(n-1-x)/(n^2+n*x+x^2-1)/(250*n^9-228*n^8*x-98*n^7*x^2-603*n^6*x
^3+635*n^5*x^4+375*n^4*x^5+98*n^3*x^6-407*n^2*x^7-277*n*x^8-15*x^9-2250*n^8+
1824*n^7*x+686*n^6*x^2+3618*n^5*x^3-3175*n^4*x^4-1500*n^3*x^5-294*n^2*x^6+814*n
*x^7+277*x^8+8250*n^7-5521*n^6*x-2693*n^5*x^2-8410*n^4*x^3+5715*n^3*x^4+2885*n^
2*x^5+946*n*x^6-362*x^7-15750*n^6+7590*n^5*x+6605*n^4*x^2+9520*n^3*x^3-4445*n^2
*x^4-2770*n*x^5-750*x^6+16500*n^5-4057*n^4*x-9145*n^3*x^2-5870*n^2*x^3+797*n*x^
4+965*x^5-9000*n^4-324*n^3*x+6503*n^2*x^2+2348*n*x^3+473*x^4+2000*n^3+716*n^2*x
-1858*n*x^2-588*x^3)*K(n-2,x)):

fi:
end:

#start code and explanation by Mark van Hoeij

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:

# Taking the formula inside "MyK" and plugging it into the recurrence inside "K" proves
# that K(n,x) = MyK(n,x) for n = 1,2,3,...

# In MyK(n, x) if we plug in x = n+1 then the first factor (-x+1+n) inside MyK becomes 0,
# and so all that remains from MyK when x = n+1 is this:

subs(x = n+1,  - 1/2*(x+1)^2*n/(3*x-2)/(x-1)*(-x+n)*(3*n^2+2*n*x+x^2+3*n+x));
factor(%);