Proof that the Eulerian Numbers $A(n,m)$ are asymptotic to $(m+1)^n$ when $m$ is fixed and $n\rightarrow\infty$

Question

This is stated in many places but seldom proved. The goal is to prove that, for fixed $m\geq 0$, $$\lim_{n\rightarrow\infty}A(n,m)\sim (m+1)^n$$ where $A(n,m)$ are the Eulerian Numbers, namely, the number of permutations of $\{1,2,\ldots,n\}$ with exactly $k$ "ascents" (places where the element is greater than the previous one).

Answer 1

Let us prove that $$\lim_{n\rightarrow\infty}\frac{A(n,m)}{(m+1)^n}=1.$$ We use the formula for the Eulerian Numbers provided in the book Concrete Mathematics: $$A(n,m)=\sum_{k=0}^m\binom{n+1}{k}(m+1-k)^n(-1)^k.$$ Dividing the equation above by $(m+1)^n$ we have: \begin{eqnarray} \frac{A(n,m)}{(m+1)^n}&=& \sum_{k=0}^m\binom{n+1}{k}\frac{(m+1-k)^n}{(m+1)^n}(-1)^k\\ &=& \sum_{k=0}^m\binom{n+1}{k}\left(\frac{m+1-k}{m+1}\right)^n(-1)^k\\ &=& \sum_{k=0}^m\binom{n+1}{k}\left(1-\frac{k}{m+1}\right)^n(-1)^k\\ %&=& %1+\sum_{k=1}^m\binom{n+1}{k}\left(1-\frac{k}{m+1}\right)^n(-1)^k\\ \end{eqnarray} Let $a_{n,k}:=\binom{n+1}{k}\left(1-\frac{k}{m+1}\right)^n(-1)^k$, thus $\frac{A(n,m)}{(m+1)^n}=\sum_{k=0}^ma_{n,k}$. If $k=0$ then $a_{n,k}=1$. We are going to prove that, when $k\neq 0$, $a_{n,k}\rightarrow 0$.

Consider the series $\sum_{n=0}^\infty a_{n,k}$. We will prove that this series converges if $k\neq 0$ using the ratio test: $$\left|\frac{a_{n+1,k}}{a_{n,k}}\right|= \frac{\binom{n+2}{k}\left(1-\frac{k}{m+1}\right)^{n+1}(-1)^k} {\binom{n+1}{k}\left(1-\frac{k}{m+1}\right)^n(-1)^k}= \frac{n+2}{n+2-k}\left(1-\frac{k}{m+1}\right)$$ Note that, when $n\rightarrow\infty$, $\frac{n+2}{n+2-k}\rightarrow 1$. So $\left|\frac{a_{n+1,k}}{a_{n,k}}\right|\rightarrow 1-\frac{k}{m+1}$. If $k\neq 0$ then $1-\frac{k}{m+1}<1$. Therefore, by the ratio test, the series $\sum_{n=0}^\infty a_{n,k}$ converges. It follows that $a_{n,k}\rightarrow 0$ when $n\rightarrow\infty$.

So we have $\frac{A(n,m)}{(m+1)^n}=\sum_{k=0}^ma_{n,k}$ with $a_{n,0}=1$ and $a_{n,k}\rightarrow 0$ when $k\neq 0$ and $n\rightarrow\infty$. This means that $$\lim_{n\rightarrow\infty}\frac{A(n,m)}{(m+1)^n}= \lim_{n\rightarrow\infty}\sum_{k=0}^ma_{n,k}=1 %\lim_{n\rightarrow\infty}1+\sum_{k=1}^m\lim_{n\rightarrow\infty}a_{n,k}= %1+\sum_{k=1}^ma_{n,k}= $$