Expectation of symmetry random walk to the power of $2k$. Let $\{X_n\}_{n=1}^{\infty}$ be i.i.d random variables,which satisfies $\mathbb{P}(X_1=1)=\frac{1}{2},\mathbb{P}(X_1=-1)=\frac{1}{2}$, $S_n = X_1+X_2+\ldots+X_n$.
Then for any positive integer $k$, whether or not
$$
\lim_{n\to \infty}\frac{\mathbb{E}(S_n^{2k})}{n^k}
$$
converges.If it converges, compute the limit.
I guess the answer is converge.We have $\mathbb{E}(X_i)=0, E(X_i^2)=1$.For $k=1, S_n^2=\sum_i X_i^2+\sum_{i\neq j}X_iX_j, \mathbb{E}(S_n^2)=n.$
In this case,the limit is $1.$ But for bigger $k$, I'm not sure how to deal with $S_n^{2k}$.
Since c.f. of $S_n$ is $f(t)=\cos^{n}t , \mathbb{E}(S_n^{2k})=(-1)^kf^{(2k)}(0)$ . But compute $f^{(2k)}(0)$ is also not easy.
 A: The answer is $(2k-1)!!=\prod\limits_{j=1}^k (2j-1)$
Note $$\mathbb{E}[S_n^{2k}] = \mathbb{E}[(X_1+\cdots+X_n)^{2k}] = \sum_{(a_1,\cdots,a_k)\in \{1, \cdots, n\} ^k} \mathbb{E} \left[\prod\limits_{j=1}^n X_{a_j}\right] =\sum_{\substack{i_1,\cdots,i_n \text{ even } \\ i_1+\cdots+i_n=2k}} \#((a_1,\cdots,a_k) \text{ has } i_j \text{ j's} \forall j=1,\cdots,n)\mathbb{E}\left[\prod_{j=1}^n X_j^{i_j} \right] = \sum_{\substack{i_1,\cdots,i_n \text{ even } \\ i_1+\cdots+i_n=2k}} \#((a_1,\cdots,a_k) \text{ has } i_j \text{ j's} \forall j=1,\cdots,n)$$
For each multiset of $n$ even nonnegative numbers with sum $2k$, there are $O(n^{\# i_j > 0})$ ways for $\{i_1,\cdots,i_n\}$ to be that multiset, and $$\#((a_1,\cdots,a_k) \text{ has } i_j \text{ j's} \forall j=1,\cdots,n)$$ is bounded because it is the number of permutations of a string with $i_j j$'s for all $j=1,\cdots,n$, which has at length $2k$.
This is $o(n^k)$ unless our multiset contains $k$ 2's. In this case, there are $\binom nk$ ways to have $i_1,\cdots,i_n \in \{0,2\}$ with $\sum i_j = 2k$. For each such way, there are $(2k)!/(2!)^k$ ways to have the multiset $\{a_1,\cdots,a_n\} $ be equal to a string with $i_j$ j's, because there are $(2k)!/(2!)^k$ permutations of a string of length $2k$ that contain $k$ distinct letters, each appearing exactly twice.
$$\frac{\mathbb{E}[S_n^{2k}]}{n^k} = \frac{(2k)!2^{-k}\binom nk + o(n^k)}{n^k} =  \prod\limits_{j=1}^k (2j-1)+
 o(1) \to \prod\limits_{j=1}^k (2j-1)$$
Remark: by the Central Limit Theorem, this implies that if $X\sim N(0,1)$, then $\mathbb{E} [X^{2k}]=(2k-1)!!=\prod\limits_{j=1}^k (2j-1)$
