What is the probability that the pawn will be at the origin after 2n moves

Question

Let's say we are on two-dimensional lattice. The pawn can move in every direction by length one. (it can move up, down, right, left or diagonally with equal probabilities) What is the probability that the pawn will be at the origin after exactly 2n moves? I solved it for pawn moving only diagonally, which in my opinion would be $${{2n}\choose{n}}^2(\frac{1}{2})^{4n}$$ because we have to do exactly n moves up and down and left and right, which probabilities are $\frac{1}{2}$ and are independent of each other. But I can't squeeze the harder version.

Answer 1

Suppose in addition to the eight options of moving orthogonally and diagonally, we give the chess piece a ninth option to stay put. Let $a_n$ be the number of paths which return to the origin with this ninth option. You can show that $$ a_n = b_n^2, $$ where $b_n$ is the number of sequences of $n$ numbers each equal to one of $\{-1,0,+1\}$ whose sum is zero. Here $b_n$ is a much simpler Markov chain for which you can hopefully solve its return probabilities. One solution is \begin{align} b_n &=[x^0](x^{-1}+1+x)^n \\&=[x^n](1+x+x^2)^n \\&=[x^n](1-x^3)^n(1-x)^{-n} \\&=\sum_{i=0}^{\lfloor n/3\rfloor}(-1)^i\binom{n}{i}\binom{2n-1-3i}{n-1} \end{align}

However you want neither $a_n$ nor $b_n$, you want $c_n$. To count $c_n$, simply take $a_n$, subtract the bad paths where some step is the new "stay put" option, add back in the doubly subtracted paths, etc. This is the principle of inclusion exclusion. The result is $$ c_n = \sum_{k=0}^n(-1)^k\binom{n}ka_{n-k} $$