Let $\displaystyle X_{0},X_{1},.....$ be a discrete time Markov chain on state space S.

Charikaar tosses a fair coin. If it shows heads he takes one step North. If it shows tails he takes one step South. This process is performed repeatedly.

Show that the probability that after 2k coin tosses Charikaar is back where he started is $\displaystyle 2^{-2k}\binom {2k} {k}$

I think this is Random walk on integers but I am not sure what is the state space in this example ... can the state space be S={.....,-3,-2,-1,0,1,2,3,.....}? he starts at zero and moves left and right? Can you please help me get started with the answer. Thanks