Let X$_i$ be a random variable defined as X$_i$ = 1 if w$_i$ = Head and; X$_i$ = $-$1 if w$_i$ = Tail; P(T)=P(H)=0.5
Define discrete-time stochastic process M(n) as M(0)=0, M(n) = $\sum_{i=1}^{n}$ X$_i$
Fix positive integers k and n, what is P(M(n)=k) ?
Should it be (0.5)$^k$$\times$$\frac{(n-k)!}{(\frac{n-k}{2})!(\frac{n-k}{2})!}$(0.5)$^{\frac{n-k}{2}}$(0.5)$^{\frac{n-k}{2}}$? My idea is like there must exist k steps to move forward to arrive at k. Afterwards, there should be equally steps move back or forward. Is it right? But what if n-k is not even? Any idea to solve this problem? Is there any formula to solve this type of problems?
You are almost right! Basically, all you've done wrong is that you have implicitly said the first $k$ (or, a particular choice of $k$) steps must be 'forward'.
In order to get $M(n) = k$, you need to have $k$ more $+1$s than $-1$s. (Let's assume that $k \ge 0$ for the moment; $k \le 0$ is similar.) This means we need $(n-k)/2$ down ($-1$) and $(n+k)/2$ up ($+1$). Each trajectory has the same probability, since $P(up) = \tfrac12 = P(down)$, and the probability is $2^{-n}$. Now, how many such trajectories are there? We simply need to choose $(n-k)/2$ of the $n$ to be down, and the remaining $(n+k)/2$ are then up: this is, by definition, $\binom{n}{(n-k)/2}$. $$ P(M(n) = k) = \binom{n}{(n-k)/2} 2^{-n}. $$
As you point out, there is an issue if $n-k$ is not even. Note that $M(n)$ has the same parity (ie even/odd) as $n$: $n$ is odd if and only if $M(n)$ is odd. Hence $P(M(n) = k) = 0$ when $n - k$ is odd.