Derivation of the D-finite recurrence equation for A176604 and related sequences ============================================== Georg Fischer, Jan 26 2020 There are 85 sequences in the range A176604-A177203 whose names contain essentially 3 parameters j, k and a(1)=m (a(0) is always 1): Sequence defined by the recurrence formula a(n+1)=sum(a(p)*a(n-p)+k,p=0..n)+j for n>=1, with here a(0)=1, a(1)=0, k=0 and j=1. For the general case with arbitrary j, k and m we show the derivation of the D-finite recurrence by means of a Mathematica session: We fetch the package of Wolfram Koepf from <http://www.mathematik.uni-kassel.de/~koepf/Publikationen/SpecialFunctions.m>, store it in the local Mathematica directory structure, and start a fresh MMA session. <<SpecialFunctions` We rewrite the formula for the g.f. by expanding the fraction with (1-x), since the SpecialFunctions package crashes with the original formula. gf=(-Sqrt[1-6*x+(13-4*m)*x^2+(-12-8*k-4*j+8*m)*x^3+(4+4*k+4*j-4*m)*x^4])/(2*x*(1-x)); For this g.f. compute the differential equation: de=HolonomicDE[gf,f[x]] which is: (-1+5*x-9*x^2+(7-4*k-2*j)*x^3+(-2+2*j)*x^4) * f[x] - (-1+x)*x*(-1+6*x+(-13+4*m)*x^2+(12+8*k+4*j-8*m)*x^3+(-4-4*k-4*j+4*m)*x^4) * f'[x] == 0 With re=DEtoRE[de,f[x],a[n]] we get: 4 (1 + k + j - m) n a[n] + 2 (-9 - 6 k - 3 j + 6 m - 8 n - 6 k n - 4 j n + 6 m n) a[1 + n] - (-57 - 12 k - 6 j + 24 m - 25 n - 8 k n - 4 j n + 12 m n) a[2 + n] + (-66 + 12 m - 19 n + 4 m n) a[3 + n] + (33 + 7 n) a[4 + n] - (6 + n) a[5 + n] == 0 Here we shift n to n-5, initialize a[2..4] and finally get the following program: (* A176604: a(1)=0, k=0 and j=1. 1, 0, 1, 3, 7, 16, 39, 102, 279, 782, 2227, 6427, 18769, 55376 *) m:=0; k:=0; j:=1; RecurrenceTable[{a[0]==1, a[1]==m, a[2]==1, a[3]==3, a[4]==7, + (+20+20*k+20*j-20*m+(- 4- 4*k-4*j+ 4*m)*n)*a[n-5] - (+62+48*k+34*j-48*m+(-16-12*k-8*j+12*m)*n)*a[n-4] + (+68+28*k+14*j-36*m+(-25- 8*k-4*j+12*m)*n)*a[n-3] - (+29 - 8*m+(-19 + 4*m)*n)*a[n-2] - ( -2 +( 7 )*n)*a[n-1] + ( +1 +( 1 )*n)*a[n ] == 0},a,{n,0,20}] ----------------------- In the special case of A176604, we see that the differential equation has a common factor (x-1) which can be cancelled out: m=0; j=1; k=0; Factor[ (-1+5*x-9*x^2+(7-4*k-2*j)*x^3+(-2+2*j)*x^4) * f[x] - (-1+x)*x*(-1+6*x+(-13+4*m)*x^2+(12+8*k+4*j-8*m)*x^3+(-4-4*k-4*j+4*m)*x^4) * f'[x] == 0] (-1 + x)*((1-- 4*x + 5*x^2 - 2*x^3 + 2*j*x^3)*f[x] + (x - 6*x^2 + 13*x^3 - 12*x^4 - 4*j*x^4 + 4*x^5 + 4*j*x^5)*f'[x]) == 0 de=((1-4*x...)*f[x] + (x-6*x^2 ... )*f'[x]) == 0 re=DEtoRE[de,f[x],a[n]] 4*(1+j)*n*a[n] -2*(7+j+6*n+2*j*n)*a[1+n] +(31+13*n)*a[2+n] -2*(11+3*n)*a[3+n] +(5+n)*a[4+n] == 0 By shifting n -> n-4 we get: 8*(n-4)*a[n-4]-16(n-3)a[n-3]+(13n-21))*a[n-2]-2(3n-1))*a[n-1]+(n+1)*a[n]==0 which is exactly the recurrence given by Richard J. Mathar: (n+1)*a(n) +2*(-3*n+1)*a(n-1) +(13*n-21)*a(n-2) +16*(-n+3)*a(n-3) +8*(n-4)*a(n-4)=0 ----------------------- By setting k, j and m and a[2..4], all remaining 84 sequences can be computed. The following list shows their parameters: A-number a(0) m k j ------------------------- A176604 1 0 0 1 A176605 1 1 0 1 A176606 1 3 0 1 A176607 1 4 0 1 A176609 1 5 0 1 A176610 1 0 1 1 A176611 1 1 1 1 A176612 1 2 1 1 A176645 1 4 1 1 A176648 1 5 1 1 A176675 1 0 0 -1 A176677 1 1 0 -1 A176678 1 2 0 -1 A176749 1 3 0 -1 A176750 1 4 0 -1 A176751 1 5 0 -1 A176752 1 0 0 -2 A176753 1 1 0 -2 A176754 1 2 0 -2 A176755 1 3 0 -2 A176756 1 4 0 -2 A176757 1 5 0 -2 A176759 1 0 1 -1 A176828 1 2 1 -1 A176829 1 3 1 -1 A176830 1 4 1 -1 A176832 1 5 1 -1 A176854 1 0 -1 0 A176855 1 1 -1 0 A176856 1 2 -1 0 A176857 1 3 -1 0 A176858 1 4 -1 0 A176859 1 5 -1 0 A176952 1 0 -1 -1 A176953 1 1 -1 -1 A176954 1 2 -1 -1 A176956 1 3 -1 -1 A176957 1 4 -1 -1 A176958 1 5 -1 -1 A176959 1 0 -1 1 A176962 1 2 -1 1 A176964 1 3 -1 1 A176966 1 4 -1 1 A176967 1 5 -1 1 A177110 1 0 -2 0 A177111 1 1 -2 0 A177113 1 2 -2 0 A177115 1 3 -2 0 A177117 1 4 -2 0 A177118 1 5 -2 0 A177122 1 6 1 1 A177123 1 7 1 1 A177124 1 8 1 1 A177125 1 9 1 1 A177126 1 10 1 1 A177127 1 6 0 1 A177128 1 7 0 1 A177129 1 8 0 1 A177130 1 9 0 1 A177131 1 10 0 1 A177162 1 6 0 -1 A177163 1 7 0 -1 A177165 1 8 0 -1 A177166 1 9 0 -1 A177167 1 10 0 -1 A177168 1 6 0 -2 A177169 1 7 0 -2 A177170 1 8 0 -2 A177171 1 9 0 -2 A177172 1 10 0 -2 A177175 1 6 1 -1 A177177 1 7 1 -1 A177178 1 8 1 -1 A177179 1 9 1 -1 A177180 1 10 1 -1 A177181 1 6 -1 -1 A177182 1 7 -1 -1 A177183 1 8 -1 -1 A177184 1 9 -1 -1 A177185 1 10 -1 -1 A177197 1 6 -1 1 A177198 1 7 -1 1 A177199 1 8 -1 1 A177200 1 9 -1 1 A177203 1 10 -1 1