Skip to main content
added 334 characters in body
Source Link
Carlo Beenakker
  • 188.1k
  • 18
  • 448
  • 651

As described in Analytic Combinatorics by Flajolet and Sedgewick, page 4, athe pole $t_0$ of the generating function gives$F(t)$ of smallest absolute value governs the exponential asymptotics $P_n\sim t_0^n$$P_n\sim (1/t_0)^n$. In this case $t_0=x+\sqrt{x^2-1}$$t_0=x-\sqrt{x^2-1}$, hence $P_n\sim (x+\sqrt{x^2-1})^n$. The

To obtain the subexponential factor can also be obtained from the generating functionone expands $F(t)$ around $t_0$, but that requires more work $$F(t)\simeq 2^{-1/2}(x^2-1)^{-1/4}t_0^{-1/2}(1-t/t_0)^{-1/2}$$ $$=2^{-1/2}(x^2-1)^{-1/4}t_0^{-1/2}\sum_{n = 0}^{\infty}\frac{(2n - 1)!!}{2^n n!}(t/t_0)^n$$ $$\simeq (2\pi )^{-1/2}(x^2-1)^{-1/4}\sum_{n}n^{-1/2}(1/t_0)^{n+1/2}\,t^n,$$ which gives precisely the large-$n$ asymptotics for $P_n$ quoted in the OP.

As described in Analytic Combinatorics by Flajolet and Sedgewick, page 4, a pole $t_0$ of the generating function gives the exponential asymptotics $P_n\sim t_0^n$. In this case $t_0=x+\sqrt{x^2-1}$. The subexponential factor can also be obtained from the generating function, but that requires more work.

As described in Analytic Combinatorics by Flajolet and Sedgewick, page 4, the pole $t_0$ of the generating function $F(t)$ of smallest absolute value governs the exponential asymptotics $P_n\sim (1/t_0)^n$. In this case $t_0=x-\sqrt{x^2-1}$, hence $P_n\sim (x+\sqrt{x^2-1})^n$.

To obtain the subexponential factor one expands $F(t)$ around $t_0$, $$F(t)\simeq 2^{-1/2}(x^2-1)^{-1/4}t_0^{-1/2}(1-t/t_0)^{-1/2}$$ $$=2^{-1/2}(x^2-1)^{-1/4}t_0^{-1/2}\sum_{n = 0}^{\infty}\frac{(2n - 1)!!}{2^n n!}(t/t_0)^n$$ $$\simeq (2\pi )^{-1/2}(x^2-1)^{-1/4}\sum_{n}n^{-1/2}(1/t_0)^{n+1/2}\,t^n,$$ which gives precisely the large-$n$ asymptotics for $P_n$ quoted in the OP.

Source Link
Carlo Beenakker
  • 188.1k
  • 18
  • 448
  • 651

As described in Analytic Combinatorics by Flajolet and Sedgewick, page 4, a pole $t_0$ of the generating function gives the exponential asymptotics $P_n\sim t_0^n$. In this case $t_0=x+\sqrt{x^2-1}$. The subexponential factor can also be obtained from the generating function, but that requires more work.