#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(%);