Probability for reaching position during 2 or 3 step random walk A boy is standing at $x=0$ and he wants to go position at $x=n$, he can jump either 2 or 3 steps forwards. The probability of taking 2 steps is $p$ and probability of taking 3 steps is $1-p$. What is probability that he arrive exactly at $x=n$?
For example, $n=5$ and $p=0.2$:
1st way: 2+3, probability $=0.2\times 0.8=0.16$.
2nd way: 3+2, probability $= 0.8\times0.2=0.16$.
Total probability $=0.16+0.16=0.32$.
 A: Let $a_n$ be the probability of landing on $n$. The event "we land on $n$" can happen in two ways: (i) we land on $n-2$ and then make a jump of $2$ or (ii) We land on $n-3$ and then make a jump of $3$. That yields the recurrence
$$a_n=pa_{n-2}+(1-p)a_{n-3}.\tag{1}$$
The initial conditions are  $a_1=0, a_2=p, a_3=1-p$ (or, if one prefers, one can use $a_0=1$.)   Recurrence (1) gives us an efficient algorithm for computing $a_n$ exactly if  $n$ is not too large.
We now outline how to get a closed form for $a_n$. The characteristic equation of (1) is $x^3-px-(1-p)=0$. This has the obvious root $1$. Then we divide the polynomial by $x-1$, obtaining a quadratic with roots $\frac{-1\pm \sqrt{4p-3}}{2}$. Thus the general solution of the recurrence is
$$a_n=A\left(\frac{-1+ \sqrt{4p-3}}{2}\right)^n +B\left(\frac{-1- \sqrt{4p-3}}{2}\right)^n +C$$
for some constants $A, B, C$. These  can be evaluated by using the initial conditions.
Remark: The formula has some unpleasant features. For $p\lt 3/4$, it involves powers of non-real numbers. One can sneak around that by using trigonometric functions and the deMoivre formula.
