I am trying to prove the following asymptotic formula for $a_n$, the number of closed paths of length $n$ on the hexagonal lattice (paths starting and ending at the same hexagon): $$a_n\sim \frac{6^n \sqrt{3}}{2\pi n}$$
I have already proven an analogous formula for a square lattice using binomial coefficients. Does anyone know of an elementary/intuitive way to prove the above?
Even better, if anyone knows of a way to prove the exact formula $$a_n=\sum_{i=0}^n (-2)^{n-i}\binom{n}{i}\sum_{j=0}^i \binom{i}{j}^3$$ I can probably figure out how to derive the asymptotic formula from this.
Both of these formulae can be found on OEIS. The sequence $a_n$ is A002898.
I don't know how to prove the exact formula you mention, but there is a straightforward way to get the asymptotic expression. As mentioned in OEIS, $a_n$ is the coefficient of $1$ in the expression $(x+1/x+y+1/y+x/y+y/x)^n$. Let $n_1, n_2, n_3, n_4, n_5, n_6$ be the number of times that $x, 1/x, y, 1/y, x/y, y/x$ respectively occurs in the above expression. The 6 $n_i$ must all be non-negative integers, and we have the following 3 constraint equations:
$n_1+ n_2+ n_3+ n_4+ n_5+ n_6 = n$, the total number of steps is $n$,
$n_1-n_2+n_5-n_6=0$, the net power of $x$ is $0$,
$n_3-n_4-n_5+n_6=0$, the net power of $y$ is $0$.
We can choose $n_1, n_2, n_3$ to be independent variables, with:
$n_4=n_1-n_2+n_3$
$n_5=(n-3n_1+n_2-2n_3)/2$, and
$n_6=(n-n_1-n_2-2n_3)/2$.
In order that $n_5, n_6$ be integral we need $n-n_1-n_2$ be an even integer.
We can put $a_n=\sum_{n_i} n!/(n_1!n_2!n_3!n_4!n_5!n_6!)$, where the sum over $n_i$ is subject to the constraint equations.
To obtain an asymptotic formula, we use Sterling's asymptotic expression for the factorials:
$n!\sim (2\pi n)^{1/2}n^ne^{-n}$, and we replace the sums by integrals. The maximum for the multinomial occurs when all $n_i$ are equal to $n/6$, we have $n!/(n/6)!^6 \sim (2\pi n)^{-5/2}6^{n+3}$. We put $n_1=n/6+x_1$, $n_2=n/6+x_2$, $n_3=n/6+x_3$, $n_4=n/6+x_1-x_2+x_3$, $n_5=n/6+(-3x_1+x_2-2x_3)/2$, and $n_6=n/6+(-x_1-x_2-2x_3)/2$. The second derivative of $log((n/6+x)!)$ with respect to $x$ is $6/n$. Carrying out the six second order partial derivatives we get $n!/(n_1!n_2!n_3!n_4!n_5!n_6!)\sim n!/((n/6)!^6Exp[\frac{-1}{2}\frac{6}{n}\begin{pmatrix}x_1 & x_2 & x_3\end{pmatrix}M\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}$, where
$M=\begin{pmatrix}9/2 & -3/2 & 3 \\ -3/2 & 5/2 & -1 \\ 3 & -1 & 4 \end{pmatrix}$
Doing the Gaussian integral gives $(2\pi n)^{3/2}6^{-3/2}/Determinant[M]$. There is an additional factor of $1/2$ because $n-n_1-n_2$ must be an even integer and so only $1/2$ the points in the sum over $n_1$ and $n_2$ count. The determinant of $M$ is $18$. Putting all these factors together we get $\frac{6^n \sqrt 3 }{2 \pi n}$.