Getting probability greater than 1? Consider a random walk starting at a positive integer $k$. Now, trying to calculate the probability of returning to zero (from $k$), I did the following:
\begin{align}
P&(\text{returning to zero})  \\
&=P(\text{returning to zero in } k\text{ steps})  \\
&\quad+ P(\text{returning to zero in } k+2\text{ steps} )  \\
&\quad+ P(\text{returning to zero in } k+4\text{ steps} ) \\
&\quad+\cdots  \\
&=\Bigl({1\over 2}\Bigr)^k  \\
&\quad+\Bigl({1\over 2}\Bigr)^{k+2}{k+2\choose 2}  \\
&\quad+\Bigl({1\over 2}\Bigr)^{k+4}{k+4\choose 4}  \\
&\quad+\cdots  \\
&=\Bigl({1\over 2}\Bigr)^k\sum_{j=0}^\infty\Bigl({1\over 2}\Bigr)^{2j}{k+2j\choose 2j}
\end{align}
Now as I put some numbers in Desmos, it is very clear that this evaluates to greater than $1$. Clearly, I’ve made some mistake.
 A: Clue :
$P$(Returning to zero in $k+2$ steps) should be $(\frac12)^{k+2}(k+1)$
Returning to zero in $k$ steps can only be done by taking the path $$k, k-1, \dots, 0$$
Returning to zero in $k+2$ steps can only be done by deviating exactly once from the '$k$ steps path'. So it's something like $$k, k-1, \dots, n, n+1, n, \dots, 0$$
There are $k+1$ integers between $0$ and $k$, leading to the result stated on top.
Now, if the walk is also allowed on the negatives, then there are $k+2$ possible deviations, because you can also go : $$k, \dots, 0, -1,0$$
But it's never ${k+2 \choose 2}$
I hope this was helpful.
A: Your first mistake is that the number of ways to walk from $k$ to $0$ in $k+2j$ steps should be $\binom{k+2j}j$, not $\binom{k+2j}{2j}$.
Furthermore, in order to have the probabilities of the events sum to $1$, the events need to be disjoint, so the event where you return to $0$ in $k+2j$ steps must be exclude returning to $0$ at any previous time. You want to find the probability of returning to $0$ for the first time in $k+2j$ steps.
In order to return to $0$ for the first time in $k+2j$ steps, you need to move from $k$ to $1$ in $k+2j-1$ steps without reaching $0$, then step down. To calculate the number of ways to do this, you need to use a clever trick called the reflection principle. 
Here's how the reflection principle works. Let us instead count the "bad" paths from $k$ to $1$ with a length of $k+2j-1$ which do reach $0$ at some point. If you take such a bad path, and negate each of its steps after the first point it reaches $0$, then it turns out you get a path from $k$ to $-1$ with a length of $k+2j-1$. Furthermore, this process is reversible; given any path from $k$ to $-1$ with a length of $k+2j-1$, if you negate each of the steps after the first time the path reaches $0$ (which must exist), then you get a "bad" path from $k$ to $0$. Therefore, the number of bad paths is just the number of paths from $k$ to $-1$, which is
$$
\binom{k+2j-1}{j-1}
$$
Therefore, the number of good paths is the total number of paths from $k$ to $1$ minus the number of bad paths, so
$$
\binom{k+2j-1}{j} - \binom{k+2j-1}{j-1}=\frac{k}{k+j}\binom{k+2j-1}{j}
$$
Finally, we multiply the number of paths by the probability $(1/2)^{k+2j-1}$ of each path occurring, times an extra $1/2$ to account for the final down step to move from $1$ to $0$. The result is
$$
P(\text{reaching $0$ for first time in $k+2j$ steps})=\left(\frac12\right)^{k+2j}\cdot\frac{k}{k+j}\binom{k+2j-1}{j}
$$
You can check that this series converges, though you will find it converges quite slowly (the sum of the first million terms is $\approx 0.998307$).
