<<RISC`Asymptotics`

Asymptotics Package version 0.3
written by Manuel Kauers
Copyright Research Institute for Symbolic Computation (RISC),
Johannes Kepler University, Linz, Austria

?Asymptotics

QuickSort: compute homogeneous recurrence starting from (n+1)a[n+1]-(n+2)a[n]==2n (Exercise)

recQS=n(n+2) a[n+2]-(2n^2+5n+1)a[n+1]+(n+1)(n+2)a[n]

Asymptotics[recQS,a[n]]

Rook diagnoal sequence

Asymptotics[(n+2)a[n+2]-2(5n+7)a[n+1]+9n a[n],a[n]]

the dominant term is ((9^n)/(Sqrt[n]))- How can we estimate the constant for the asymptotic behaviour?

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

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

data = Table[β[n]/α[n],{n,1,2000}];

N[Last[data],50]
N[3 Sqrt[Pi/2],50]

ListPlot[data]

Asymptotics[(n+3)a[n] - (3n+1)a[n+1]+(2n+2)a[n+2],a[n], Order -> 1]

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

g[n_]:=((1+(38/n))/(n^4));

data = Table[g[n]/f[n],{n,1500}];

N[Last[data],50]

ListPlot[data]