[proofplan]
We express the position $S_n$ as the sum of its $n$ independent $\{-1,1\}$-valued increments. A path reaches $k$ precisely when the number of $+1$ increments exceeds the number of $-1$ increments by $k$, which forces the number of $+1$ increments to be $(n+k)/2$. Independence gives probability $2^{-n}$ for each fixed increment sequence, and the [binomial coefficient](/page/Binomial%20Coefficient) counts the admissible sequences. If $(n+k)/2$ is not an integer between $0$ and $n$, no sequence of increments can end at $k$.
[/proofplan]
[step:Replace the walk by the sum of its independent increments]
Fix $n\in\mathbb N$ and $k\in\mathbb Z$. Define the [random variable](/page/Random%20Variable)
\begin{align*}
T_n:\Omega\to\mathbb R
\end{align*}
by
\begin{align*}
T_n(\omega)=\sum_{i=1}^{n}X_i(\omega).
\end{align*}
By the defining property of the simple symmetric random walk, $S_n=T_n$ almost surely. Therefore the events $\{S_n=k\}$ and $\{T_n=k\}$ differ by a subset of the null event $\{S_n\neq T_n\}$, and hence
\begin{align*}
\mathbb P(S_n=k)=\mathbb P(T_n=k).
\end{align*}
It remains to compute the distribution of $T_n$.
[/step]
[step:Describe each endpoint by the number of positive increments]
For a sign vector $\sigma=(\sigma_1,\ldots,\sigma_n)\in\{-1,1\}^n$, define its number of positive entries by
\begin{align*}
N_+(\sigma)=\#\{i\in\{1,\ldots,n\}:\sigma_i=1\}.
\end{align*}
If $N_+(\sigma)=m$, then exactly $n-m$ entries of $\sigma$ are equal to $-1$, so
\begin{align*}
\sum_{i=1}^{n}\sigma_i=m-(n-m).
\end{align*}
Thus
\begin{align*}
\sum_{i=1}^{n}\sigma_i=2m-n.
\end{align*}
Consequently, a sign vector can have total sum $k$ only when
\begin{align*}
m=\frac{n+k}{2}.
\end{align*}
[/step]
[step:Count the admissible sign vectors when the parity and range conditions hold]
Assume that $n+k$ is even and $|k|\leq n$. Define
\begin{align*}
m=\frac{n+k}{2}.
\end{align*}
Since $n+k$ is even, $m\in\mathbb Z$. Since $|k|\leq n$, we have $-n\leq k\leq n$, and therefore $0\leq m\leq n$.
For each $\sigma=(\sigma_1,\ldots,\sigma_n)\in\{-1,1\}^n$, define the event
\begin{align*}
A_\sigma=\bigcap_{i=1}^{n}\{X_i=\sigma_i\}.
\end{align*}
The events $(A_\sigma)_{\sigma\in\{-1,1\}^n}$ are pairwise disjoint. Let
\begin{align*}
E=\bigcap_{i=1}^{n}\{X_i\in\{-1,1\}\}
\end{align*}
Then $\mathbb P(E)=1$, and on $E$ the family $(A_\sigma)_{\sigma\in\{-1,1\}^n}$ partitions $E$. By independence of $X_1,\ldots,X_n$ and by the symmetric increment law,
\begin{align*}
\mathbb P(A_\sigma)=\prod_{i=1}^{n}\mathbb P(X_i=\sigma_i).
\end{align*}
For every $i\in\{1,\ldots,n\}$, $\mathbb P(X_i=\sigma_i)=1/2$, so
\begin{align*}
\mathbb P(A_\sigma)=2^{-n}.
\end{align*}
The event $\{T_n=k\}$ is the disjoint union of those $A_\sigma$ for which $N_+(\sigma)=m$. There are exactly $\binom{n}{m}$ such sign vectors, since choosing their positive positions is the same as choosing an $m$-element subset of $\{1,\ldots,n\}$. Therefore
\begin{align*}
\mathbb P(T_n=k)=\binom{n}{m}2^{-n}.
\end{align*}
Substituting
\begin{align*}
m=\frac{n+k}{2}
\end{align*}
gives
\begin{align*}
\mathbb P(S_n=k)=2^{-n}\binom{n}{(n+k)/2}.
\end{align*}
[guided]
We now compute the probability by separating two issues: which increment patterns end at $k$, and how likely each pattern is. Because $n+k$ is even, the number
\begin{align*}
m=\frac{n+k}{2}
\end{align*}
is an integer. Because $|k|\leq n$, we have $-n\leq k\leq n$, and therefore
\begin{align*}
0\leq \frac{n+k}{2}\leq n.
\end{align*}
Thus $m$ is a valid number of positive increments.
For a fixed sign vector $\sigma=(\sigma_1,\ldots,\sigma_n)\in\{-1,1\}^n$, define
\begin{align*}
A_\sigma=\bigcap_{i=1}^{n}\{X_i=\sigma_i\}.
\end{align*}
This is the event that the first $n$ increments follow exactly the pattern $\sigma$. The events $A_\sigma$ are pairwise disjoint: two different sign vectors disagree in at least one coordinate, so their corresponding increment requirements cannot both hold. Their union is all of $\Omega$ up to a null set, because each $X_i$ is equal to either $1$ or $-1$ almost surely.
Independence is used at precisely this point. Since $X_1,\ldots,X_n$ are independent, the probability of the simultaneous increment pattern factors:
\begin{align*}
\mathbb P(A_\sigma)=\prod_{i=1}^{n}\mathbb P(X_i=\sigma_i).
\end{align*}
Each factor is $1/2$, because each increment is symmetric and takes the values $1$ and $-1$ with equal probability. Hence
\begin{align*}
\mathbb P(A_\sigma)=2^{-n}.
\end{align*}
It remains to count how many patterns end at $k$. If a sign vector has $m$ positive entries, then it has $n-m$ negative entries, so its total increment is
\begin{align*}
m-(n-m)=2m-n.
\end{align*}
This equals $k$ exactly when $m=(n+k)/2$. Therefore $\{T_n=k\}$ is the disjoint union of all $A_\sigma$ such that $N_+(\sigma)=m$. Choosing such a sign vector is equivalent to choosing which $m$ of the $n$ positions carry the value $1$, so the number of such vectors is $\binom{n}{m}$. Summing the equal probabilities over this disjoint collection gives
\begin{align*}
\mathbb P(T_n=k)=\binom{n}{m}2^{-n}.
\end{align*}
Since $\mathbb P(S_n=k)=\mathbb P(T_n=k)$ and $m=(n+k)/2$, this becomes
\begin{align*}
\mathbb P(S_n=k)=2^{-n}\binom{n}{(n+k)/2}.
\end{align*}
[/guided]
[/step]
[step:Show that all other endpoints are impossible]
Assume that $n+k$ is odd or $|k|>n$. Let
\begin{align*}
E=\bigcap_{i=1}^{n}\{X_i\in\{-1,1\}\}
\end{align*}
Then $\mathbb P(E)=1$. On $E$, if $T_n=k$, then for the realised sign vector $\sigma=(X_1,\ldots,X_n)$ there is an integer $m=N_+(\sigma)$ with
\begin{align*}
0\leq m\leq n
\end{align*}
and
\begin{align*}
k=2m-n.
\end{align*}
This implies
\begin{align*}
m=\frac{n+k}{2}.
\end{align*}
If $n+k$ is odd, then
\begin{align*}
\frac{n+k}{2}
\end{align*}
is not an integer, contradicting $m\in\mathbb Z$. If $|k|>n$, then $k<-n$ or $k>n$, so
\begin{align*}
\frac{n+k}{2}<0
\end{align*}
or
\begin{align*}
\frac{n+k}{2}>n
\end{align*}
contradicting
\begin{align*}
0\leq m\leq n
\end{align*}.
Thus no sign vector can produce total sum $k$, and therefore
\begin{align*}
\mathbb P(T_n=k)=0.
\end{align*}
Using again $\mathbb P(S_n=k)=\mathbb P(T_n=k)$, we obtain
\begin{align*}
\mathbb P(S_n=k)=0.
\end{align*}
This proves both cases of the stated distribution formula.
[/step]
