Number of paths of length $n$ starting from the origin in the $X-Y$ plane. I have to find out the number of paths of length $n$ starting from the origin with movements


*

*$R : (x,y) \rightarrow (x+1,y)$

*$L : (x,y) \rightarrow (x-1,y)$

*$U : (x,y) \rightarrow (x,y+1).$
Also step $R$ is not followed by $L$ and vice-versa.
In a book that I was following has done it in the following way
.
I have some problem understanding it.


*

*First why $a_{n-1} = b_n$ ?

*Secondly why should I only adjoin step $R$ in a path of length $(n-1)$ which ends with $R$ ? I may adjoin $U$ to the path to get a path of length $n$. 

*Also the recurrence relation is not clear to me.


Any help will be very helpful.( If any other way of understanding is possible please let me know) Thank you.
 A: To count $a_n$, the number of paths of length $n$, the author is splitting the set of such paths into the disjoint union of three subsets:


*

*The paths ending in U

*The paths ending in LL, RR or UL

*The paths ending in UR


Note that the latter two cases combine to count all of the paths ending in L or R, as LR and RL are not permitted.
@Jihoon Kang addressed your first concern. For the remaining two, both points are addressed by counting the three subsets above individually.
First, any path ending in U may be preceded by any legal path of length $n-1$, so there are $a_{n-1}$ paths in the first subset.
Second, given any path of length $n-1$, there is a unique way to complete it such that the path ends with one of LL, RR, or UL. You are correct that it is legal to follow a U with an R, but that would create a path that is not in the second subset, so it is not counted here. The number of paths in this subset is $a_{n-1}$.
Finally, a path ending in UR can be obtained by adding UR to any path of length $n-2$, so there are $a_{n-2}$ paths in this subset.
Since the set of paths of length $n$ is the disjoint union of these three subsets, we get the recurrence $a_n = 2a_{n-1} + a_{n-2}$ by simply summing the sizes of the three subsets.
