Suppose $\{X_n\}_{n = 1}^\infty$ is a sequence of i.i.d. random variables, such that $P(X_1 = -1) = P(X_1 = 1) = \frac{1}{2}$. Suppose $S_n = \Sigma_{k = 1}^n X_k$. How can I find $P_n := P(\exists m \in \mathbb{N}_0 \text{ such that } S_n = m^2)$?
I have an assumption, that $\lim_{n \to \infty} P_n = 0$, but don't know, how to prove it.
It is easy to see, that $$P(S_n = k) = \begin{cases} \frac{C_n^k C_{n - k}^{\frac{n - k}{2}}}{2^n} & \quad \text{, if } n - k \text{ is even } \\ 0 & \quad \text{, if } n - k \text{ is odd }\end{cases}$$
From the aforementioned formula we can conclude, that
$$P_n = \begin{cases} \Sigma_{k = 0}^{\lceil \sqrt{\frac{n}{2}} \rceil} \frac{C_n^{4k^2} C_{n - 4k^2}^{\frac{n - 4k^2}{2}}}{2^n} & \quad \text{, if } n \text{ is even } \\ \Sigma_{k = 0}^{\lceil \sqrt{\frac{n}{2}} \rceil} \frac{C_n^{4k^2 - 4k + 1} C_{n - 4k^2 + 4k - 1}^{\frac{n - 4k^2 + 4k - 1}{2}}}{2^n} & \quad \text{, if } n \text{ is odd }\end{cases}$$
Now, if you want to show, that $\lim_{n \to \infty} P_n = 0$, you can do this via Stirling approximation