(*******************************************************************) (* Examples for using the package GeneratingFunctions *) (*******************************************************************) In[1]:= <{"ogf","egf","revogf","revegf"}] Out[114]= {{-a[n] - a[1 + n] + a[2 + n] == 0, a[0] == 0, a[1] == 1}, revegf} In[115]:= GuessRE[Table[ChebyshevU[k,x],{k,0,10}],a[n]] Out[115]= {{a[n] - 2 x a[1 + n] + a[2 + n] == 0, a[0] == 1, a[1] == 2 x}, ogf} In[116]:=GuessRE[S2L[Series[Sin[x],{x,0,15}],x],a[n],Hypergeom->True] Out[116]= 2 {{a[n] + (2 + 3 n + n ) a[2 + n] == 0, a[0] == 0, a[1] == 1}, ogf} (* GuessDifferentialEquation (GuessDE) *) In[120]:= GuessDE[{1,2,6,22,91,408,1938,9614,49335,260130,1402440,7702632, 42975796,243035536,1390594458,8038677054,46892282815,275750636070, 1633292229030,9737153323590},f[x],Inhomog->True] Out[120]= 2 {{12 + 12 (-1 + 5 x) f[x] + 18 (-x + 6 x ) f'[x] + 2 3 (-4 x + 27 x ) f''[x] == 0, f[0] == 1, f'[0] == 2}, ogf} (* GuessRationalFunction (GuessRatF) *) In[130]:= GuessRatF[{0,1,1,2,3,5,8,13},x] Out[130]= x {----------, ogf} 2 1 - x - x (* GuessAlgebraicEquation (GuessAE) *) In[140]:= GuessAlgebraicEquation[{1,1,2,5,14,42,132,429,1430,4862,16796, 58786,208012,742900,2674440,9694845,35357670,129644790},f[x]] Out[140]= 2 {{1 - f[x] + x f[x] == 0, f[0] == 1}, ogf} (************* Implementation of closure properties *******************) (* RecurrenceEquationPlus (REPlus) *) (* RecurrenceEquationHadamard (REHadamard) *) (* RecurrenceEquationCauchy (RECauchy) *) In[210]:= REPlus[{u[n+1]==(1+n)*u[n],u[1]==1},{u[1+n]==2*u[n],u[1]==1},u[n]] Solve::svars: Warning: Equations may not give solutions for all "solve" variables. Solve::svars: Warning: Equations may not give solutions for all "solve" variables. Out[210]= 2 2 {2 (n + n ) u[n] + (2 - 3 n - n ) u[1 + n] + 3 (-1 + n) u[2 + n] == 0, u[0] == -, u[1] == 2, u[2] == 4, 2 u[3] == 10} In[211]:= fib={f[n]==f[n-1]+f[n-2],f[0]==0,f[1]==1} Out[211]= {f[n] == f[-2 + n] + f[-1 + n], f[0] == 0, f[1] == 1} In[212]:= fact={f[n]==n*f[n-1],f[0]==1} Out[212]= {f[n] == n f[-1 + n], f[0] == 1} In[213]:= RecurrenceEquationPlus[fib,fact,f[n]] Out[213]= 2 3 {(3 + 7 n + 5 n + n ) f[n] + 2 3 (3 + 5 n + 4 n + n ) f[1 + n] + 2 3 2 (-3 - 9 n - 6 n - n ) f[2 + n] + (2 n + n ) f[3 + n] == 0 , f[0] == 1, f[1] == 2, f[2] == 3, f[3] == 8} In[220]:= RecurrenceEquationHadamard[fib,fact,f[n]] Out[220]= 2 {(-2 - 3 n - n ) f[n] + (-2 - n) f[1 + n] + f[2 + n] == 0, f[0] == 0, f[1] == 1} In[230]:= RecurrenceEquationCauchy[fib,fact,f[n]] Out[230]= {(4 + 5 n + (-1 + n) n) f[n] + (2 (1 + n) + n (1 + n)) f[1 + n] + (-2 (2 + n) - (1 + n) (2 + n)) f[2 + n] + (2 + n) f[3 + n] == 0, f[0] == 0, f[1] == 1} (* DifferentialEquationPlus (DEPlus) *) (* DifferentialEquationHadamard (DEHadamard) *) (* DifferentialEquationCauchy (DECauchy) *) In[240]:= si={f[x]+f''[x]==0,f[0]==0,f'[0]==1} Out[240]= {f[x] + f''[x] == 0, f[0] == 0, f'[0] == 1} In[241]:= atan={f'[x]==1/(1+x^2),f[0]==0} Out[241]= 1 {f'[x] == ------, f[0] == 0} 2 1 + x In[242]:= DEPlus[si,atan,f[x]] CanDE::denom: Warning. The input equation will be multiplied by its denominator. Out[242]= 3 5 {2 (-11 x + 14 x + x ) f'[x] + 2 4 6 (-1 + 7 x + 9 x + x ) f''[x] + 3 5 (3) 2 (-11 x + 14 x + x ) f [x] + 2 4 6 (4) (-1 + 7 x + 9 x + x ) f [x] == 0, f[0] == 0, (3) f'[0] == 2, f''[0] == 0, f [0] == -3} In[250]:=DEHadamard[si,atan,f[x]] CanDE::denom: Warning. The input equation will be multiplied by its denominator. Out[250]= (3) {-(x f'[x]) + 2 f''[x] + x f [x] == 0, f[0] == 0, f'[0] == 1, f''[0] == 0} In[260]:=DECauchy[si,atan,f[x]] CanDE::denom: Warning. The input equation will be multiplied by its denominator. Out[260]= 2 4 6 8 {(10 + 26 x + 11 x + 4 x + x ) f[x] + 3 5 7 4 (3 x + 5 x + 3 x + x ) f'[x] + 2 4 6 8 2 (6 + 16 x + 9 x + 4 x + x ) f''[x] + 3 5 7 (3) 4 (3 x + 5 x + 3 x + x ) f [x] + 2 4 6 8 (4) (2 + 6 x + 7 x + 4 x + x ) f [x] == 0, f[0] == 0, (3) f'[0] == 0, f''[0] == 2, f [0] == 0} (* AlgebraicEquationToDifferentialEquation (AE2DE) *) In[270]:= AlgebraicEquationToDifferentialEquation[{y==1+y^2*z,y[0]==1},y[z]] Out[270]= 2 {1 + (-1 + 2 z) y[z] + (-z + 4 z ) y'[z] == 0, y[0] == 1} In[271]:= AE2DE[-x^2+y^2,y[x]] Out[271]= y[x] - x y'[x] == 0 In[272]:= AE2DE[56*a^3+7*a^3*y^3-14*y*z,y[z]] Out[272]= 2 9 3 -(z y[z]) + 3 z y'[z] + 2 (-54 a + z ) y''[z] == 0 (* AlgebraicCompose (ACompose) *) In[280]:= AlgebraicCompose[f[x]+f''[x],f^2-x==0,f[x]] Out[280]= f[x] + 2 f'[x] + 4 x f''[x] == 0 In[281]:= ACompose[x(f[x]-f'[x])+ f'[x]-f''[x],f==1/(x-1),f[x]] CanAE::denom: Warning. The input equation will be multiplied by its denominator. Out[281]= 2 3 4 -f[x] + (-3 x + 8 x - 7 x + 2 x ) f'[x] + 2 3 4 5 (-1 + 5 x - 10 x + 10 x - 5 x + x ) f''[x] == 0 (* RecurrenceEquationSubsequence (RESubsequence) *) In[290]:= RESubsequence[{a[n]==a[n-1]/n,a[0]==1},a[n],3*n+2] CanRE::denom: Warning. The input equation will be multiplied by its denominator. Out[290]= {-a[n] + 3 (1 + n) (4 + 3 n) (5 + 3 n) a[1 + n] == 0, 1 a[0] == -} 2 In[291]:= RESubsequence[{f[n]+f[1+n]-f[n+2],f[0]==0,f[1]==1},f[n],2*n-5] RE2L::negative: Warning. The recurrence is extended to (some) negative integers. Out[291]= {f[n] - 3 f[1 + n] + f[2 + n] == 0, f[0] == 5, f[1] == 2} (* RecurrenceEquationShadow (REShadow) *) In[300]:= REShadow[{3*n+(n+1/2)*a[n]==(n^2+n+1)*a[n+2],a[0]==1,a[1]==1},a[n]] RE2L::negative: Warning. The recurrence is extended to (some) negative integers. Out[300]= 2 {6 (-2 - n) + (-2 - 2 (-2 - n) - 2 (-2 - n) ) a[n] + (1 + 2 (-2 - n)) a[2 + n] == 0, a[0] == 1, a[1] == -8} (* RecurrenceEquationInterlace (REInterlace) *) In[310]:= REInterlace[{f[n]==f[n-2]+f[n-1],f[0]==0,f[1]==1}, {f[n]==n*f[n-1],f[0]==1},f[n]] Out[310]= 2 3 {(5 + 11 n + 7 n + n ) f[n] + 2 3 (11 + 7 n + 5 n + n ) f[2 + n] + 2 3 (1 - 15 n - 9 n - n ) f[4 + n] + 2 2 (-3 + 2 n + n ) f[6 + n] == 0, f[0] == 0, f[1] == 1, f[2] == 1, f[3] == 1, f[4] == 1, f[5] == 2, f[6] == 2, f[7] == 6} (* HomogenousRecurrenceEquation (HomogenousRE) *) In[320]:= HomogenousRE[{b[k]==k*b[k-2]+1/k,b[0]==b[1]==1},b[k]] CanRE::denom: Warning. The input equation will be multiplied by its denominator. Out[320]= 2 2 {(-4 - 4 k - k ) b[k] + (9 + 6 k + k ) b[1 + k] + (2 + k) b[2 + k] + (-3 - k) b[3 + k] == 0, b[0] == 1, 5 b[1] == 1, b[2] == -} 2 (* HomogenousDifferentialEquation (HomogenousDE) *) In[330]:= HomogenousDE[{f'[x]==1/(1+x^2),f[0]==0},f[x]] CanDE::denom: Warning. The input equation will be multiplied by its denominator. Out[330]= 2 {-2 x f'[x] - (1 + x ) f''[x] == 0, f[0] == 0, f'[0] == 1} (********************** Defining sequences **************************) (* DefineSequence (DefineS) *) In[410]:= F=DefineSequence[{f[n]==f[n-2]+f[n-1],f[0]==0,f[1]==1},f[n]] Out[410]= RE[{{0, -1, -1, 1}, {0, 1}}, f[n]] (* Multiplication with rational function *) In[420]:= F*n/(n+1) CanRE::denom: Warning. The input equation will be multiplied by its denominator. Out[420]= 2 2 RE[{{0, -((1 + n) (2 + n)), -(n (2 + n) ), 1 2 n (1 + n) (3 + n)}, {0, -, -}}, f[n]] 2 3 (* Partial summation *) In[430]:= PSum[F] Out[430]= RE[{{0, 1, 0, -2, 1}, {0, 1, 2}}, f[n]] (* Forward difference *) In[440]:= Delta[F] Out[440]= RE[{{0, -1, -1, 1}, {1, 0}}, f[n]] (* Proof of Cassini's identity *) In[450]:= Shift[F,1]*Shift[F,-1]-F^2-DefineS[{a[n]+a[n-1]==0,a[0]==1},a[n]] RE2L::negative: Warning. The recurrence is extended to (some) negative integers. Out[450]= RE[{{0, 1, -2, -2, 1}, {0, 0, 0}}, a[n]] (* Identifying sequences *) In[460]:= rhs=DefineS[{a[n]+a[n-1]==0,a[0]==1},a[n]] Out[450]= RE[{{0, 1, 1}, {1}}, a[n]] In[451]:= Shift[F,1]*Shift[F,-1]-F^2==rhs RE2L::negative: Warning. The recurrence is extended to (some) negative integers. Out[451]=True In[452]:= rhs=DefineS[a[n]+a[n-1]==0,a[n]] Out[452]= RE[{{0, 1, 1}, {}}, a[n]] In[452]:= Shift[F,1]*Shift[F,-1]-F^2==rhs RE2L::negative: Warning. The recurrence is extended to (some) negative integers. EqualRE::Initials: Attention. In the output, a[i] denotes element i in the sequence, which is given by the difference of the left hand side and the right hand side of the input equation. Out[453]= a[0] == 0 && a[1] == 0 && a[2] == 0 In[454]:= A=DefineS[{n^2*(2+n)^2*a[n]+(48+4*n-5*n^2)*(3+4*n+n^2)*a[1+n]- 4*(2+n)*(448+268*n+47*n^2+2*n^3)*a[2+n]+ 12*(1260+1207*n+431*n^2+68*n^3+4*n^4)*a[3+n]==0, a[0]==0,a[1]==1/180,a[2]==1/2240,a[3]==1/18900},a[n]] Out[454]= 2 3 4 2 3 4 RE[{{0, 4 n + 4 n + n , 144 + 204 n + 49 n - 16 n - 5 n , 2 3 4 -3584 - 3936 n - 1448 n - 204 n - 8 n , 2 3 4 1 1 1 15120 + 14484 n + 5172 n + 816 n + 48 n }, {0, ---, ----, -----}}, a[n]] 180 2240 18900 In[455]:= B=DefineS[GuessRE[RE2L[A,20],a[n],2,4,Hypergeom->True][[1]],a[n]] Out[455]= 2 3 4 2 3 4 1 RE[{{0, -4 n - 4 n - n , 30 n + 52 n + 26 n + 4 n }, {0, ---}}, a[n]] 180 In[456]:= A==B EqualRE::IntegerRoots: Warning. The result is correct, provided that the polynomial $LeadingPolynomial= 2 2 12 (28 + 15 n + 2 n ) (45 + 19 n + 2 n ) contains no integer root greater -1. Out[456]= True (*RecurrenceEquationPlus (REPlus) *) In[470]:= G=DefineS[{g[m]+(m^2+3)*g[m+1]==1,g[0]==1},g[m]] Out[470]= 2 RE[{{-1, 1, 3 + m }, {1}}, g[m]] In[471]:= H=REPlus[G,F] Out[471]= 2 3 4 RE[{{0, 78 + 96 m + 51 m + 12 m + m , 2 3 4 5 6 191 + 218 m + 208 m + 130 m + 54 m + 12 m + m , 2 3 4 5 -229 - 418 m - 324 m - 142 m - 29 m - 2 m , 2 3 4 5 6 -377 - 566 m - 587 m - 366 m - 134 m - 26 m - 2 m , 2 2 3 4 (12 + 6 m + m ) (22 + 26 m + 21 m + 8 m + m )}, 5 59 {1, 1, -, --}}, g[m]] 4 28 (* RecurrenceEquationOut (REOut) *) In[480]:= REOut[H] Out[480]= 2 3 4 {(78 + 96 m + 51 m + 12 m + m ) g[m] + 2 3 4 5 6 (191 + 218 m + 208 m + 130 m + 54 m + 12 m + m ) 2 3 4 g[1 + m] + (-229 - 418 m - 324 m - 142 m - 29 m - 5 2 3 2 m ) g[2 + m] + (-377 - 566 m - 587 m - 366 m - 4 5 6 134 m - 26 m - 2 m ) g[3 + m] + 2 2 3 4 (12 + 6 m + m ) (22 + 26 m + 21 m + 8 m + m ) g[4 + m] \ 5 59 == 0, g[0] == 1, g[1] == 1, g[2] == -, g[3] == --} 4 28 (********************** Defining functions **************************) (* DefineFunction (DefineF) *) In[510]:= si=DefineFunction[{f[x]==-f''[x],f[0]==0,f'[0]==1},f[x]] Out[510]= DE[{{0, 1, 0, 1}, {0, 1}}, f[x]] In[511]:= atan=DefineF[{g'[z]==1/(1+z^2),g[0]==0},g[z]] CanDE::denom: Warning. The input equation will be multiplied by its denominator. Out[511]= 2 DE[{{-1, 0, 1 + z }, {0}}, g[z]] (* Multiplication with rational function *) In[520]:= si/(x-1) CanDE::denom: Warning. The input equation will be multiplied by its denominator. Out[520]= DE[{{0, -1 + x, 2, -1 + x}, {0, -1}}, f[x]] (* Integration *) In[530]:= Integrate[atan] Out[530]= 2 DE[{{0, 0, 0, 2 z, 1 + z }, {0, 0, 1}}, g[z]] (* Differentiation *) In[540]:=D[si] Out[540]= DE[{{0, 1, 0, 1}, {1, 0}}, f[x]] (* Truncated Power Series *) In[550]:=Series[atan,15] Out[550]= 3 5 7 9 11 13 15 z z z z z z z 16 z - -- + -- - -- + -- - --- + --- - --- + O[z] 3 5 7 9 11 13 15 (* Proof of Sin[x]^2+Cos[x]^2==1 *) In[560]:= si^2+D[si]^2-1 Out[560]= DE[{{0, 0, 4, 0, 1}, {0, 0, 0}}, f[x]] (* Identifying two functions to be equal *) In[570]:= si^2+D[si]^2==1 Out[570]= True In[571]:= ratf=DefineF[{c*f[x]+(-1+c*x)*f'[x]==0,f[0]==c},f[x]] Out[571]= DE[{{0, c, -1 + c x}, {c}}, f[x]] In[572]:= ratf==1/(1-x) CanDE::denom: Warning. The input equation will be multiplied by its denominator. Out[572]= 2 -1 + c == 0 && -1 + c == 0 (* DifferentialEquationPlus (DEPlus) *) In[580]:= g=DEPlus[si,atan] Out[580]= 3 5 DE[{{0, 0, 2 (-11 x + 14 x + x ), 2 2 4 3 5 (1 + x ) (-1 + 8 x + x ), 2 (-11 x + 14 x + x ), 2 2 4 (1 + x ) (-1 + 8 x + x )}, {0, 2, 0, -3}}, f[x]] (* DifferentialEquationOut (DEOut) *) In[590]:= DEOut[g] Out[590]= 3 5 {2 (-11 x + 14 x + x ) f'[x] + 2 4 6 (-1 + 7 x + 9 x + x ) f''[x] + 3 5 (3) 2 (-11 x + 14 x + x ) f [x] + 2 4 6 (4) (-1 + 7 x + 9 x + x ) f [x] == 0, f[0] == 0, (3) f'[0] == 2, f''[0] == 0, f [0] == -3} (************************************************************************)