Problem source

A point moves in unit steps on the $x$-axis starting from the origin. At each step the point is equally likely to move in the positive or negative direction. The probability that after $s$ steps it is at one of the points $x=2,x=3,x=4$ or $x=5$ is $\mathrm{P}(s).$ Show that $\mathrm{P}(5)=\frac{3}{16},$ $\mathrm{P}(6)=\frac{21}{64}$ and 
\[
\mathrm{P}(2k)=\binom{2k+1}{k-1}\left(\frac{1}{2}\right)^{2k}
\]
where $k$ is a positive integer. Find a similar expression for $\mathrm{P}(2k+1).$ 
Determine the values of $s$ for which $\mathrm{P}(s)$ has its greatest value.

Solution source

After $5$ steps we can get to:

\begin{array}{c|c}
x & \text{ways} \\ \hline 
5 & 1 \text { - go positive every time}\\
4 & 0 \\
3 & \binom{5}{1} \text { - go positive every time but 1} \\
2 &0 \\ \hline
& 6
\end{array}

Therefore there are $\frac{6}{2^5} = \frac{3}{16}$ ways to get to $\{2,3,4,5\}$

After $6$ steps we can get to:

\begin{array}{c|c}
x & \text{ways} \\ \hline 
5 & 0 \\
4 & \binom{6}{1} \text { - go positive every time but 1}\\
3 & 0  \\
2 & \binom{6}{2} - \text{ - go positive every time but 2} \\ \hline
& 21
\end{array}

Therefore there are $\frac{21}{2^6} = \frac{21}{64}$ ways to get to $\{2,3,4,5\}$

After $2k$ steps we can reach $2$ or $4$. 

To get to $2$ we must take $k+1$ positive steps and $k-1$ negative steps, ie $\binom{2k}{k-1}$. 
To get to $4$ we must take $k+2$ positive steps and $k-2$ negative steps, ie $\binom{2k}{k-2}$

Therefore there are $\binom{2k+1}{k-1}$ routes, ie a probability of $\frac{1}{2^{2k}} \binom{2k+1}{k-1}$

After $2k+1$ steps we can reach $3$ or $5$. 

To get to $3$ we must take $k+2$ positive steps and $k-1$ negative steps, ie $\binom{2k+1}{k-1}$. 
To get to $5$ we must take $k+3$ positive steps and $k-2$ negative steps, ie $\binom{2k+1}{k-2}$

Therefore there are $\binom{2k+2}{k-1}$ routes, ie a probability of $\frac{1}{2^{2k+1}} \binom{2k+2}{k-1}$

To find the maximum of $P(s)$ notice that

\begin{align*}
&& \frac{P(2k+1)}{P(2k)} &= \frac12 \frac{\binom{2k+2}{k-1}}{\binom{2k+1}{k-1}} \\
&&&= \frac12 \frac{(2k+2)!(k-1)!(k+2)!}{(2k+1)!(k-1)!(k+3)!} \\
&&&= \frac12 \frac{2k+2}{k+3} = \frac{k+1}{k+3} < 1
\end{align*}

So we should only look at the even terms.



\begin{align*}
&& \frac{P(2k+2)}{P(2k)} &= \frac14 \frac{\binom{2k+3}{k}}{\binom{2k+1}{k-1}} \\
&&&= \frac14 \frac{(2k+3)!(k-1)!(k+2)!}{(2k+1)!k!(k+3)!} \\
&&&= \frac14 \frac{(2k+3)(2k+2)}{k(k+3)} \\
&&&= \frac{(2k+3)(k+1)}{2k(k+3)} \geq 1 \\
\Leftrightarrow && (2k+3)(k+1) &\geq 2k(k+3) \\
\Leftrightarrow && 2k^2+5k+3 &\geq 2k^2+6k \\
\Leftrightarrow && 3 &\geq k \\
\end{align*}

Therefore the maximum is when $s = 2\cdot 3$ or $s = 2\cdot 4$ which we computed earlier to be $\frac{21}{64}$