I was reading Noga Alon's book. I found that there was a Putnam competition question asking to prove that the expected value of a random walk is
$$\mathbb{E}[|S_n|]=n2^{1-n}\binom{n-1}{\lfloor(n-1)/2\rfloor}.$$
Here, $S_{n} = X_{1} + X_{2} + \cdots X_{n}$, where $X_{i}$ are independent uniform random numbers in $\left\{-1,+1\right\}$. Can someone provide a proof for that?
Hint:
Consider a walker moving on an infinite one-dimensional uniform lattice (i.e. a line split into discrete points). Suppose the walker starts at the origin ($x=0$) and then moves a short distance $\delta$ either left or right in a short time $\Delta t$. The motion is assumed to be completely random, so the probabilities of moving both left and right are $\frac12.$ After one time step, the walker can either be at a distance $\delta$ to the left or right of the origin, with probability $\frac12$ each After the next time step, the walker will either be at a distance $2\delta$ to the left or right of the origin (with probability $\frac14$ each) or will have returned to the origin (with probability $\frac12$). Note that, after an even (odd) number of steps, the walker can only be at an even (odd) distance away from the origin. Continuing in this way, the probability that a walker will be at a distance $m\delta$ to the right of the origin after $n$ time steps is given by $${{\left( \frac{1}{2} \right)}^{n}}\left( \begin{matrix} n \\ \lfloor \frac{n-m}{2} \rfloor \\ \end{matrix} \right) $$