<<RISC`HolonomicFunctions`;

HolonomicFunctions Package version 1.7.3 (21-Mar-2017)
written by Christoph Koutschan
Copyright Research Institute for Symbolic Computation (RISC),
Johannes Kepler University, Linz, Austria

First Proof of Mihailovs’ conjecture

ann1=ToOrePolynomial[{8 (k+3) (k+1)+(7 k^2+53 k+88)**S[k]-(k+8) (k+7)**S[k]^2},OreAlgebra[S[k]]](*the annihilating operator for E_3(n)*)

ann2=Annihilator[(-1)^(n-k) Binomial[n,k],{S[k]}] (* the annihilating operator for (-1)^(n-k) Binomial[n, k] w.r.t. k *)

ann3=DFiniteTimes[ann1,ann2](*the annihilating operator for f(n,k) w.r.t.k *)

ann4=ChangeOreAlgebra[ann3,OreAlgebra[S[n],S[k]]];

ann5=Annihilator[(-1)^(n-k) Binomial[n,k],{S[n],S[k]}](* the annihilator for (-1)^(n-k) Binomial[n, k] *)

ann=Append[ann4,ann5[[2]]](*annihilators for f(n,k)*)

{{P},{Q}}=CreativeTelescoping[ann,S[k]-1,S[n]];(*derive pricipal partP and delta part Q for creative telescoping relation,P is exactly the same as Theorem 1.2*)

Factor[P]

Factor[Q]

cert=ApplyOreOperator[Q,f[k]] (*cerficate for f(n,k)*)

cert0=cert/.{k->0}(*evaluate cert at k=0*)

c0=cert0/.{f[0]->(-1)^n,f[1]->(-1)^(n-1) n}//Together(*verify the evaluation at k=0 is equal to 0*)

Proof of Corollary 4.13 in the article “On sequences associated to invariant theory”

marbergREC= ToOrePolynomial[{(n+ 4) (n + 5)**S[n]^2  - 2 (5 n^2 + 26 n + 30)**S[n] + 9 n (n + 3)},OreAlgebra[S[n]]] // Factor(*the recurrence equation for C_2 with C_2[0] = 1, C_2[1] = 1*)

rec = ApplyOreOperator[marbergREC, f[n]] (* translate marbergREC into recurrence equation *)

RecurrenceTable[{rec == 0, f[0] == 1, f[1] == 1}, f, {n,0, 10} ] (* use the above recurrence equation to compute a few terms *)

marbergREC1 = DFiniteSubstitute[marbergREC, {n -> n + 1}](*the recurrence equation for C_2 with C_2[0] = 1, C_2[1] = 3*)

rec1= ApplyOreOperator[marbergREC1, f[n]](* translate marbergREC1 into recurrence equation *)

RecurrenceTable[{rec1 == 0, f[0] == 1, f[1] == 3}, f, {n,0, 10} ](* use the above recurrence equation to compute a few terms *)

ann0 = DFiniteRE2DE[marbergREC1, n, t] (* the differential equation for the generating function of Marberg sequence*)

ann1 = DFiniteSubstitute[ann0, {t -> x/(k x + 1)}, Algebra -> OreAlgebra[Der[x]]] (* do the algebraic substitution with parameter k*)

ann2 = DFiniteTimes[ann1, Annihilator[1/(k x + 1), {Der[x]}]] (* the differential equation for the generating function of the k-th inverse binomial transform of Marberg sequence*)

REC2 = DFiniteDE2RE[ann2, x, n] // Factor (* the recurrence equation for the k-th inverse binomial transform of Marberg sequence *)

rec5 = Factor[REC2 /. {k -> 3 - l}] (* the recurrence equations for S_l, l = 0, 1, 2, 3 *)

REC2spec0 = REC2 /. {k -> 0} (* specify k by 0 in REC2 *)

rec2 = ApplyOreOperator[REC2spec0, f[n]] //Factor (* compute the corresponding recurrence equation *)

RecurrenceTable[{rec2 ==0, f[0] == 1, f[1] == 3}, f, {n, 0, 10}](* use the above recurrence equation to compute a few terms, which are same as Marberg sequences *)

OreReduce[REC2spec0,marbergREC1](* specification at k = 0 of REC2 derives the recurrence of Marberg sequence*)

REC2spec1 = REC2 /. {k -> 1}(* specify k by 1 in REC2 *)

rec2 = ApplyOreOperator[REC2spec1, f[n]] //Factor(* compute the corresponding recurrence equation *)

RecurrenceTable[{rec2 ==0, f[0]==1, f[1]==2, f[2]==6}, f, {n, 0, 10}] (* use the above recurrence equation to compute a few terms *)

annBaxter = Annihilator[(Binomial[n + 1, k -1] Binomial[n +1, k] Binomial[n + 1, k+1])/(Binomial[n +1, 1] Binomial[n +1, 2]), {S[k], S[n]}]

{{P1},{Q1}}=CreativeTelescoping[annBaxter,S[k]-1,S[n]];

P1 // Factor (* P1 is the recurrence equation for Baxter permutation *)

P2 = DFiniteSubstitute[{P1}, {n -> n + 1}][[1]]

RecurrenceTable[{ApplyOreOperator[P2, f[n]] == 0, f[0]==1, f[1]==2}, f, {n, 0, 10}] (* compute a few terms of Baxter permutation *)

OreReduce[REC2spec1, {P2}] (* specification at k = 1 of REC2 derives the recurrence of Baxter permutation *)

REC2spec2 = REC2 /. {k -> 2}(* specify k by 2 in REC2 *)

rec2 = ApplyOreOperator[REC2spec2, f[n]] //Factor(* compute the corresponding recurrence equation *)

RecurrenceTable[{rec2 ==0, f[0]==1, f[1]==1, f[2]==3, f[3] == 9}, f, {n, 0, 10}] (* use the above recurrence equation to compute a few terms *)

rec3 = ToOrePolynomial[{(n + 5)*(n+6)**S[n]^3 - 2*(n+ 3)*(2*(n+3)+1)**S[n]^2 - (n+3-2)*(19*(n+3)-9)**S[n]-14*(n+3 -3)*(n+3-2)}, OreAlgebra[S[n]]] //Factor

rec4 = DFiniteSubstitute[rec3, {n-> n+1}] // Factor (* input the recurrence equation of A236408 *)

RecurrenceTable[{ApplyOreOperator[rec4, f[n]] ==0, f[0]==1, f[1]==1, f[2]==3}, f, {n, 0, 10}](* use the above recurrence equation to compute a few terms *)

OreReduce[REC2spec2,rec4](* specification at k = 2 of REC2 derives the recurrence of A236408 *)

REC2spec3 = REC2 /. {k -> 3}(* specify k by 3 in REC2 *)

rec2 = ApplyOreOperator[REC2spec3, f[n]] //Factor(* compute the corresponding recurrence equation *)

RecurrenceTable[{rec2 ==0, f[0]==1, f[1]==0, f[2]==2, f[3] == 2}, f, {n, 0, 10}](* use the above recurrence equation to compute a few terms *)

rec3 = ToOrePolynomial[{(n +3 +4)*(n+3+3)**S[n]^3-(n + 3)*(n+3-1)**S[n]^2 -12*(2*(n+3)+1)*(n+3 -1)**S[n] -36*(n+3-1)*(n+3-2)}, OreAlgebra[S[n]]] //Factor(* input the recurrence equation of A151366 *)

RecurrenceTable[{ApplyOreOperator[rec3, f[n]] ==0, f[0]==1, f[1]==0, f[2]==2}, f, {n, 0, 10}](* use the above recurrence equation to compute a few terms *)

OreReduce[REC2spec3,rec3](* specification at k = 3 of REC2 derives the recurrence of A151366 *)