2
$\begingroup$

I am trying to assess the aymptotic behavior for large $n$ of the sequence $(a_n)_{n=1}^\infty$ defined by the recursion \begin{align} a_{n} &= (n+1) a_{n-1} - n a_{n-2}-1, \ \forall n\ge3 \\ a_2 &= 2a_1-3. \end{align} This recursion originates from this question on stats.stackexchange.com.

Define the generating function $f(x):=\sum_{n=0}^\infty a_nx^n,$. $g(x):=x^2f(x)$ satisfies the ODE $$g'-\Big(\frac1{x^2}+\frac1x+\frac1{1-x}\Big)g=\Big(\frac x{1-x}\Big)^2-\frac{a_0}{1-x}+(2a_0-a_1)\frac x{1-x}$$ Multiply both sides by $e^h=\frac{1-x}xe^{\frac1x}$ where $h(x):=\frac1x+\ln\frac{1-x}x$ and get $$\frac{d}{dx}\Big(\frac{1-x}xe^{\frac1x}g\Big)=e^{\frac1x}\Big(\frac x{1-x}-\frac{a_0}x+(2a_0-a_1)\Big).$$ Now $e^{\frac1x}$ seems to prevent me from solving the ODE in a "closed" form.

I read somewhere the complex analysis may help to derive the large $n$ asymptotics of $a_n$. How does one procede?

$\endgroup$
1
$\begingroup$

Partial answer to an interesting problem. However, without $a_0$ and $a_1$ specified, one can't even determine the sign of the asymptotics. By dropping the -1 on the right-hand side of the equation, the recursion can be solved (in Mathematica) in terms of 'subfactorials.' That is

$$a_n = \kappa_1+ \kappa_2 \sum_{k=0}^n k! $$

where the $\kappa$ are related somehow to $a_0$ and $a_1.$ Naturally the second term will dominate. Choosing $a_0=0$ and using numerical and symbolic computations I was able to determine

$$ a_n \sim (a_1+2-e)\sum_{k=0}^n k! \quad ,\quad (a_0 = 0)$$

To make it absolutely clear, this step lacked rigor. The sum may be approximated by $ \sum_{k=0}^n k! \sim n! (n-1)/n .$ As a check, for $a_1=2,$ by the time $n=10,$ the relative error is about 1 part in a million. What would be an interesting study is what happens to the asymptotics when $a_1 = e-2;$ it appears to be slowly growing, like $\cal{o}(n^{1/4}).$ We therefore have a region where, even with one constant simply specified, a non-uniformity appears. With two free constants, this problem might be a real bear to get a handle on.

Update: The second formula is a proposed asymptotic solution for $a_n = (n+1)a_{n-1}-n \ a_n -1$ for $a_0=0$ and away from the region $a_1=e-2.$ The first asymptotic form was deduced by using Mathematica's RSolve command. To check, and to generate numerical data for my guess, I did the following: $$\text{ Clear[a]; a[0]=0; a[1]=1; a[n_]:=a[n]=(n+1)a[n-1]-n*a[n-2]-1;}$$

$$\text{tb=Table[a[n],{n,0,30}]/Table[ Sum[k!,{k,0,n}],{n,0,30}]}$$ The output is $$ \text{N[tb]={0, .5, .5, .4, .323529, ... 0.281718}} $$ One of the last numbers looked a lot like $e$ minus a rational, so I used $$ \text{FindIntegerNullVector[{1,E,0.281718...}]}$$ to confirm my suspicion. Doing this for many $a_1$ led to the conjecture; it is not a proof I don't have enough motivation to go further.

$\endgroup$
3
  • $\begingroup$ (1) Sorry, I edited the problem a bit. Could you please review and adjust your solution? $a_0=0$. (2) I want to ascertain that your second equation comes from the original recursion without dropping the −1 on the RHS, unlike your first equation, right? (2) Are there any hints from Mathematica as to how these expressions are derived? (3) For the critical value of $a_1$, can Mathematica or any other method zoom in for further analysis? (4) Would you mind posting your detailed Mathematica scripts and output in your answer so that I can learn the corresponding Mathematica scripts? Thank you. $\endgroup$ – Hans Oct 10 '19 at 6:42
  • $\begingroup$ +1. So the second expression comes from you conjecting from numerical computation and not from Mathematica, right? $\endgroup$ – Hans Oct 10 '19 at 18:04
  • $\begingroup$ The first expression is not a conjecture but the recursion has the -1 removed and two free constants. The second expression is a conjecture, but guided by the first because I expect the answer to be a perturbation. My expectation was surprised by the fact that there is a nonuniformity when $a_1$ is approx. e-2. $\endgroup$ – skbmoore Oct 10 '19 at 19:02
0
$\begingroup$

Define $b_n:=a_n-a_{n-1}$. The original recursion turns into $$b_n=nb_{n-1}-1$$ which is solvable with a generating function.

$\endgroup$
1
  • $\begingroup$ do you consider this a complete solution? if so, you should mark this answer accepted. $\endgroup$ – mathworker21 Nov 4 '19 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.