Reading "Elements of the Random Walk" written by Joseph Rudnick and George Gaspari, i am confused by the recursion relation they gave on page 13. the book says that For 1d discrete random walk with step length $l$ and equal probability of traveling right and left at any site, $$C(N{\rm{ }};{\rm{ }}x,{\rm{ }}y) = C(N - 1{\rm{ }};{\rm{ }}x,{\rm{ }}y - l) + C(N - 1{\rm{ }};{\rm{ }}x,{\rm{ }}y + l) \tag{1}$$ with $C(N{\rm{ }};{\rm{ }}x,{\rm{ }}y)$ is equal to the number of walks that start at x and end up at y.
The book says that the above equation is equivalent to Pascal's rule $$\frac{{N!}}{{n!(N - n)!}} = \frac{{(N - 1)!}}{{(n - 1)!(N - n)!}} + \frac{{(N - 1)!}}{{n!(N - n - 1)!}}$$
I know that $$P(N{\rm{ }};{\rm{ }}x,{\rm{ }}y) = \frac{1}{{{2^N}}}\frac{{N!}}{{n!(N - n)!}}{\rm{ = }}\frac{1}{{{2^N}}}C(N{\rm{ }};{\rm{ }}x,{\rm{ }}y)\tag{2}$$ if $y-x=nl$. The master equation is $$P(N{\rm{ }};{\rm{ }}x,{\rm{ }}y) = \frac{{\rm{1}}}{{\rm{2}}}P(N - 1{\rm{ }};{\rm{ }}x,{\rm{ }}y - l) + \frac{{\rm{1}}}{{\rm{2}}}P(N - 1{\rm{ }};{\rm{ }}x,{\rm{ }}y + l)\tag{3}$$
where $P(N{\rm{ }};{\rm{ }}x,{\rm{ }}y)$ is the probability of the walk that start at x and end up at y. The combination of equation 2 and 3 will give equation 1.
What puzzles me is that as $$C(N - 1{\rm{ }};{\rm{ }}x,{\rm{ }}y + l) = \left( {\begin{array}{*{20}{c}} {N - 1}\\ {n + 1} \end{array}} \right){\rm{ = }}\frac{1}{{{2^{N - 1}}}}\frac{{(N - 1)!}}{{(n + 1)!(N - n - 2)!}}$$
Should equation 1 gives $$\frac{{N!}}{{n!(N - n)!}} = \frac{{(N - 1)!}}{{(n - 1)!(N - n)!}} + \frac{{(N - 1)!}}{{(n + 1)!(N - n - 2)!}}$$
This seems to be different from the Pascal's rule, so where am i wrong. Thanks for your help!
After discussion with @epi163sqrt, I found that my mistake was that I take for granted that $y-x=nl$ for $C(N {\rm{ }};{\rm{ }}x,{\rm{ }}y )$ as i wrote above. Instead it should be $y-x=(2n-N)l$.
I didn't change the origin post in order to help guys who make similar mistake.
Comment: The identity (1) is valid, since we have the situation \begin{align*} C(N;x;y)=\frac{N!}{n!(N-n)!} \end{align*} where we consider according to the book $N$-step walks with
$n$ steps to the right and
$N-n$ steps to the left
When we now look at the right-most term of \begin{align*} C(N;x;y)=C(N-1;x;y-l)+C(N-1;x;y+l) \end{align*} with the interpretation of $n$ given above, we see, that since $y+l$ is to the right of $y$ we have done all $n$ steps to the right. Since the right-most term represents the number of $N-1$-step walks to $y+l$, we have also done $(N-1)-n$ steps to the left, resulting in \begin{align*} \binom{N-1}{n} \end{align*} different walks.