In $\mathbb Z$ and $\mathbb Z^2$, a finitely supported probability measure $\mu$ yields a recurrent random walk if and only if it is centered, meaning that
$$\sum_{x\in \mathbb Z^d}x\mu(x)=0.$$
This is usually proved using Fourier transforms.
Indeed, you can prove that the $n$th power convolution of $\mu$ satisfies the local following local limit theorem:
$$\mu^{*n}(e)\sim CR^{-n}n^{d/2}$$
and $R=1$ if and only if $\mu$ is centered.
Actually, $R$ is the inverse of the minimum of the function
$$\phi(u)=\sum_{x\in \mathbb Z^d}\mu(x)\mathrm{e}^{u\cdot x}.$$
This function is strictly convex and it reaches its minimum where its gradient vanishes.
You can check that the gradient is given by
$$\nabla \phi(u)=\sum_{x\in \mathbb Z^d}x\mu(x)\mathrm{e}^{u\cdot x}.$$
Thus, the minimum is reached at 0 if and only if
$$\sum_{x\in \mathbb Z^d}x\mu(x)=0$$
that is $\mu$ is centered. In other words, the minimum is equal to $\phi(0)=1$ if and only if $\mu$ is centered.
Now, if $d\geq 3$, you see that $\mu^{*n}(e)$ is always summable, whether $R=1$ or not, but if $d\leq 2$, then $\mu^{*n}(e)$ is summable if and only if $R>1$, if and only if $\mu$ is non centered.
Finally, summability of $\mu^{*n}$ is by definition equivalent to finiteness of the Green function, which is equivalent to the random walk being transient.
For all the details I have not proved,
see for example Woess's book random walks on infinite graphs and groups, in particular Chapter III.13 for local limit theorems on $\mathbb Z^d$.
Technical hint: $\binom n {n/2} \sim c 2^n/\sqrt n$. Which you can see by using Stirling's formula or by just knowing that about half of the mass in Pascal's triangle is within $\pm \sqrt n$ of the middle.
Conceptual hint: you are calculating the expected number of returns to $0$ ever. If it is finite, that means ...
Best Answer
I'd reason like this:
we know from the general theory that
$$\mathbb{E}[N] = \lim_{t \to 1}\int_{[-\pi,\pi]}\frac{dk}{\sqrt{2\pi}(1-t \varphi(k))}$$ where $\varphi(k)$ is the characteristic function of $X_1$ and $N = \sum_{n \ge 0}\mathbb{I}_{S_n = S_0}$.
First we notice that
$$ \varphi(k) = \sum_{n \ne 0}\frac{e^{ikn}}{2} \bigg[ \frac{1}{|n|^{\alpha}} -\frac{1}{(|n| + 1)^{\alpha}} \bigg] = \sum_{n = 1}^{\infty} \cos(nk) \bigg[ \frac{1}{|n|^{\alpha}} -\frac{1}{(|n| + 1)^{\alpha}} \bigg]$$
Then
$$ 1 - \varphi(k) = \sum_{n = 1}^{\infty} (1-\cos(nk)) \bigg[ \frac{1}{|n|^{\alpha}} -\frac{1}{(|n| + 1)^{\alpha}} \bigg] \le \sum_{n \ge 1} \frac{1-\cos(nk)}{n^{\alpha}}$$
Remembering the inequality $\cos(x) \ge 1 - x^2 / 2$, we finally obtain $$ 1 -\varphi(k) \le \sum_{n \ge 1} \frac{k^2}{2 n^{\alpha -2}} = C k^2$$
when it is convergent, hence when $\alpha > 3$. By Fatou's Lemma we can say that $$ \liminf_{t \to 1}\int_{[-\pi,\pi]}\frac{dk}{\sqrt{2\pi}(1-t \varphi(k))} \ge \int_{[-\pi,\pi]}\frac{dk}{\sqrt{2\pi}(1-\varphi(k))} = \infty$$
Therefore it is recurrent whenever $\alpha > 3$.