Getting exactly $n$ points from coin tossing 
Possible Duplicate:
A probability question 

Needing a little help with the following problem,

A player tosses a fair coin and is to score one point for every head turned up and two points for every tail. He is to play until his score reaches or passes $n$. Find the probability that his score is exactly $n$. 

Here's how I would approach the problem.
Let $X$ be the number of points scored in the coin toss. Then $X = X_{1} + \cdots + X_{i}$.
$$
X_{j} =
\begin{cases}
1, & \text{if the } i^{\rm th} \text{ trial is a success},
\\
2, & \text{otherwise}.
\end{cases}
$$
So $E[X] = i \cdot E[X_{1}] = ??$
Here is where I got stuck...
Anybody got any idea on how to proceed? 
 A: Let $P_n$ be the probability that our random walk passes through $n$. Since the first step is $1$ or $2$, each with probability $1/2$,  we have
$$P_{n+1}=\frac{1}{2}P_n+\frac{1}{2}P_{n-1},\qquad(\ast)$$
with initial conditions $P_0=1$, $P_1=1/2$. Solve the recurrence, say by using the characteristic equation procedure.
We get
$$P_n=\frac{2}{3}+\frac{1}{3}(-1/2)^n.  $$  
Comment:   Instead of using the characteristic equation method to solve $(\ast)$, we can use a trick. Rewrite $(\ast)$ as 
$$P_{n+1}-P_n=-\frac{1}{2}(P_n-P_{n-1}).$$
Let $y_n=P_n-P_{n-1}$. Then $(y_n)$ is a geometric sequence with common ratio $-1/2$. Summing the geometric progression, we find that
$$P_n=\frac{1-(-1/2)^{n+1}}{3/2}.$$
A: You can score exactly $n$ in two ways: by scoring exactly $n-1$, and then throwing a head; or by not scoring $n-1$ (in which case you are forced to score $n$). So if $P_n$ is the probability of scoring exactly $n$, we get
$$P_n = \frac{1}{2}P_{n-1} + (1 - P_{n-1})$$
or
$$P_n = 1 - \frac{1}{2}P_{n-1}$$
Starting from $P_0 = 1$, you can calculate a few values, and see if you can find the pattern. What does it tend to?
