<< GeneratingFunctions.m

(* Example 3.7: closure properties addition *)

REPlus[{q[n+2]-2x q[n+1]+q[n]==0,q[0]==1,q[1]==x},{q[n+1]-(1+x)q[n]==0,q[0]==1},q[n]]

(* help: *)

?REPlus

?RE*

(* 
Generating function for Legendre polynomials:
Input: three term recurrence for Legendre polynomials
Output: differential equation for the generating function 
*)

ode = RE2DE[{(n+2)p[n+2]-(2n+3)x p[n+1]+(n+1)p[n]==0,p[0]==1,p[1]==x},p[n],F[z]]

DSolve[ode,F[z],z]

(* without initial conditions *)

RE2DE[{(n+2)p[n+2]-(2n+3)x p[n+1]+(n+1)p[n]==0},p[n],F[z]]

(* Legendre kernel polynomials for y=1: first using closure properties, then guessing and proving *)

prod = REHadamard[{(n+2)s[n+2]-(2n+3) x s[n+1] + (n+1) s[n]==0, s[0]==1,s[1]==x},{(2n+1) s[n+1]-(2n+3) s[n]==0,s[0]==1/2},s[n]]

sum = RECauchy[prod,{s[n+1]-s[n]==0,s[0]==1},s[n]]

data = Table[Factor[Sum[(2k+1)/2 LegendreP[k,x],{k,0,n}]],{n,0,30}];

Take[data,3]

guess = GuessRE[data,s[n]]

(* now proving - need to adapt initial values *)

minusguess = {guess[[1,1]],s[0]==-(1/2),s[1]==-(1/2) (1+3 x)}

zero=REPlus[sum,minusguess,s[n]]

Factor[Last/@Take[zero,-3]]

(* end of proof *)

?GuessRE

(* Guessing: a simple example *)

Clear[c,ans];
c[i_,n_,d_]:=c[i,0]+Sum[c[i,i1] n^i1,{i1,1,d}];
ans[a_,n_,{order_,deg_}]:=Sum[c[i2,n,deg] a[n+i2],{i2,0,order}];

(* ansatz for a recurrence of order 2 with coefficients of maximal degree 2 satisfied by a given sequence a[n] *)

ans[a,n,{2,2}]

b[n_]:=Binomial[2n,n] (-4)^n;

data = Table[b[n],{n,0,20}]

sys =Table[ans[b,n,{1,1}]==0,{n,0,6}]

sol = First[Solve[sys]]

rec =ans[B,n,{1,1}]/.sol

rec=Collect[rec,B[_],Factor]

First[GuessRE[Table[b[n],{n,0,20}],B[n]]]