Probability of landing in $\mathbb{N}\cup \{0\}$ Here's a question I'm struggling with:

A man is standing on $0 \in \mathbb{R}$. He tosses $n$ coins. For H he
  takes a right step and for T he takes a left step. What is the
  probability that at the end of the process he's standing on a
  non-negative integer?

Here's my attempt.
Let $P(n\text{ is odd}) = p$ and $P(n\text{ is even}) = 1-p$
If $n$ is odd we know that he can't go back to zero. The number of paths that ends at $\mathbb{R}^+$ is equal to those that ends at $\mathbb{R}^-$ so the probability in this case is $\dfrac{2^n}{2}$.
If $n$ is even we need to cound the number of string where $H \ge T$ and so the probability is $$\frac{\sum_{k=n/2}^{n}\binom{n}{k}}{2^n}$$
and so in general we get
$$(1-p)\cdot \frac{2^n}{2} + p\cdot \frac{\sum_{k=n/2}^{n}\binom{n}{k}}{2^n}$$
Am I right? Thanks!
 A: Let $H$ be the random variable "number of heads after $n$ coin tosses. Let also $p$ equal the probability of landing on a non-negative integer. Obviously $X\sim B(n,\frac{1}{2})$. You are right to note that if $n$ is odd, we cannot go back to $0$. Thus, by symmetry, we can conclude that in this case the probability of being on the right of $0$ is $p=1/2$.
On the other hand, if $n$ is even, our symmetry corresponds to $P(H>n/2)+P(H<n/2)+P(H=n/2)=1$ and $P(H>n/2)=P(H<n/2)$.
Since $P(H=n/2)=$$n\choose n/2$$(1/2)^{n}$, we conclude that for even $n$, $$p=\left(1-\binom{n}{n/2}2^{-n}\right)/2+\binom{n}{n/2}2^{-n}=1/2+\binom{n}{n/2}2^{-n}/2$$
I'm struggling to work out whether or not our answers are the same - I'm not sure what you mean by $P(n$ is even$)$ etc.
A: At this point, I should probably be talking in an answer, instead of a comment.
We can't do the version where $n$ is to be determined randomly as part of the process because we don't have any well-defined probability distribution for $n$. If we did, we could sum over the possible values of $n$, taking for each term the probability of getting that $n$ times the probability of landing at $0$ or higher if we get that $n$, and that would get us the total probability of landing at $0$ or higher. However, we don't have a distribution like that, nor is there any "natural" choice for such a distribution, so the problem only makes sense if $n$ is a parameter, and that's how I'm going to approach it.
If $n$ is odd, then the probability is $\frac{1}{2}$, not $\frac{2^n}{2}$; the latter isn't even between $0$ and $1$ for $n>1$. For even $n=2m$, we can simplify your sum by realizing that
$$\binom{2m}{0}+\binom{2m}{1}+\dots+\binom{2m}{m-1}+\binom{2m}{m+1}+\dots+\binom{2m}{2m}=2^{2m}-\binom{2m}{m}$$
counts all of the possibilities for not landing on $0$, and that we need to include exactly the ones from $\binom{2m}{m+1}$ on, which make up exactly half of the total sum. The rest of the possibilities we need to include are the ones in which the man lands on $0$, and there are $\binom{2m}{m}$ of these, so our final probability should be
$$\frac{1}{2^{2m}}\cdot(2^{2m-1}+\frac{1}{2}\binom{2m}{m})=\frac{1}{2^n}\cdot(2^{n-1}+\frac{1}{2}\binom{n}{n/2})=\frac{1}{2}+\frac{1}{2^{n+1}}\binom{n}{n/2},$$
which is again equal to the formula you gave above.
