<<HolonomicFunctions.m

HolonomicFunctions package by Christoph Koutschan, RISC-Linz, Version 1.5.1 (09.08.2011)
⟶ Type  ?HolonomicFunctions  for help

f[x_,y_]:=(((x-1)(y-1))/(1-2x-2y+3x y))

1/x f[x,y/x]//Factor

{annF,Q} =CreativeTelescoping[(((-1+x) (x-y))/(x (-x+2 (x^2)+2 y-3 x y))),Der[x],Der[y]]//Factor

annA =DFiniteDE2RE[annF,{y},{n}]

recA = ApplyOreOperator[annA,α[n]]

<< Hyper.m

Hyper[recA[[1]],α[n]]

RSolve[{recA[[1]]==0,α[0]==1,α[1]==2},α[n],n]

<< Asymptotics.m

Asymptotics[recA[[1]],α[n]]

Clear[a];
a[0]:=1;
a[1]:=2;
a[n_Integer]:=a[n]=-((9 (-2+n) a[-2+n])/n)+((2 (-3+5 n) a[-1+n])/n);

data = Table[a[nn],{nn,50}];

Clear[A];
A[n_]:=((9^n)/(Sqrt[n]));

asymptdata = Table[A[nn],{nn,50}];

ListLogPlot[{data,asymptdata}]

asymptdata/data//N

ListPlot[asymptdata/data]

$RecursionLimit = 10^5;

N[A[100]/a[100],100]

Clear[q];
q[n_]:=A[n]/a[n];

Clear[c];
c[k_,n_,b_]:=(2^k b[2n]-b[n])/(2^k-1);

N[c[1,50,q],100]

N[q[50],100]

N[q[100],100]

N[q[900],100]

ListPlot[{Table[c[1,nn,q],{nn,1,50}],asymptdata/data}]

(* average complexity example *)

ac[n_]:=3^(-4n) 1/(2n-1) Sum[Binomial[2n,k]^2 k(n-k+n k)2^(2k),{k,0,2n}];

ann = Annihilator[ Sum[3^(-4n) 1/(2n-1)Binomial[2n,k]^2 k(n-k+n k)2^(2k),{k,0,2n}],{S[n]}]//Factor

rec = ApplyOreOperator[ann,AC[n]]

Asymptotics[rec[[1]],AC[n]]