On a symmetrical random walk, I am trying to deduce
P[$M_{n}$ = k] = $(\frac{1}2)^n$ ${n \choose \frac{n+k}2}$
where n is the total number of steps and ${n \choose \frac{n+k}2}$ is the number of paths possible knowing the integers n,k.
we know that for each n and k, the # of steps up can be calculated using $\frac{n+k}2$ an the number of steps down can be calculated using $\frac{n-k}2$.
With that, totaling n = $\frac{n+k}2$ + $\frac{n-k}2$
This may be an easy question but I don't see how to deduce it.. Please help.
If you can directly apply the result of Binomial distribution, you may try the following:
Let $M_n = \sum_{i=1}^n X_n$ where $X_i$ represent each individual step with support $\Pr\{X_i = 1\} = p, \Pr\{X_i = -1\} = 1 - p$. Note $$ X_i \stackrel {d} {=} 2B_i - 1, i = 1, 2, \ldots, n$$ where $B_i \sim \text{Bernoulli}(p)$. Therefore summing them up $$ M_n \stackrel {d} {=} 2\sum_{i=1}^n B_i - n$$ and we know that $\sum_{i=1}^n B_i \sim \text{Binomial}(n, p)$. As a result, $$ \begin{align*} \Pr\{M_n = k\} & = \Pr\left\{2\sum_{i=1}^n B_i - n = k\right\} \\ & = \Pr\left\{\sum_{i=1}^n B_i = \frac {n + k} {2} \right\} \\ & = \binom {n} {\frac {n + k} {2}} p^{\frac {n + k} {2}}(1 - p)^{\frac {n - k} {2}} \end{align*}$$ where $k = -n, -n + 1, \ldots, 0, \ldots, n - 1, n$. In particular put $p = \frac {1} {2}$, you immediately got your result.