Probability 2 Random Walkers Will Meet (1D) Each walker has chance $p$ to move right and change $q=1-p$ to move left. What is the probability they will meet again after N steps? I've simplified it down to just essentially a single walker where the displacement increases/decreases with probability $p-p^2$ and stays the same with probability $2p^2-2p+1$, but I'm not sure how to handle the displacement when it stays the same. If that term wasn't there I could write the probability of taking so many steps in one direction and then rewrite in terms of displacement and simplify that down to a solution, but that method doesn't account for the chance of no change in displacement.
edit: They start at the same spot
 A: Suppose $X_n$ is the coordinate of the first man after $n$ steps, and $Y$ - of the second one. Suppose $Z_n = X_n - Y_n$. Then your problem is equivalent to finding $P(Z_N = 0)$.
We see, that $$Z_n - Z_{n-1} = \begin{cases} 2 & \quad \text{ with probability } pq \text{ (the first one makes a step right and the other a step left) } \\ 0 & \quad \text{ with probability } p^2 + q^2 \text{ (they move in the same direction) } \\ -2 & \quad \text{ with probability } pq \text{ (the first one makes a step left and the other a step right) } \end{cases}$$
And each step is assumed to be made independently.
Suppose $N_1$ is the number of the occurrences of the first case, $N_2$ - of the second case, and $N_3$ - of the third case. Then, in case $Z_N = 0$ we have $N = N_1 + N_2 + N_3$ and $N_1 = N_3$. There are $C_{N}^{N_2}C_{N - N_2}^{\frac{N - N_2}{2}}$ such configurations for any fixed $N_2$, such that $N \equiv N_2 (\text{mod }2)$ (and $0$ otherwise). And the probability of each of them is $(p^2 + q^2)^{N_2}(pq)^{N - N_2}$. Thus, we have 
$$P(Z_N = 0) = \begin{cases} \Sigma_{i = 0}^{\frac{N}{2}} C_{N}^{2i}C_{N - 2i}^{\frac{N}{2} - i}(p^2 + q^2)^{2i}(pq)^{N - 2i} & \quad N \text{ is even} \\ \Sigma_{i = 0}^{\frac{N-1}{2}} C_{N}^{2i+1}C_{N - 2i-1}^{\frac{N-1}{2} - i}(p^2 + q^2)^{2i+1}(pq)^{N - 2i-1} & \quad N \text{ is odd}\end{cases}$$
That is your answer.
