I am reading Feller's Introduction to probability theory and its applications. Can you help me to understand a part of his reasoning about Random Walks?
Notation: $S_n=p+q$ , where $p$ is the number of $+1$'s and $q$ number of $-1$'s in the sequence of length n, which elements are either $+1$ or $-1$ ($n=p+q$). $N_{n,x}$ is the number of ways to choose all $+1$'s from the sequence:
$N_{n,x}= \binom{n}{p}=\binom{n}{q}$
Let $n$ and $x$ be positive integers. There are exactly $\frac x n N_{n,x}$ paths $(S_1,... S_n = x)$ from the origin to the point $(n, x)$ such that $S_1 > 0,..., S_n > 0$.
Proof: Clearly there exist exactly as many admissible paths as there are paths from the point $(1, 1)$ to $(n, x)$ which neither touch or cross the $t$-axis. By the reflection principle the number of such paths equals:
$N_{n-1, x-1} - N_{n-1,x+1} = \binom{n-1}{p-1}-\binom{n-1}{p}$
Can you explain why the second term in the right hand sight of the equation is $\binom{n-1}{p}$? I mean why $p$?
Reflection principle: Number of paths from $A$ that lead to the point $(n,x)$ and touch or cross the x axis is equal to the number of paths to the same point from the $A$'s reflection on the x-axis.
It seems:
The number of paths of this type from $(0,0)$ to $(a,b)$ is ${a \choose (a+b)/2}$, where $b$ has the same parity as $a$ and $|b| \le a$
The number of paths of this type from $(1,1)$ to $(a,b)$ is ${a-1 \choose ((a-1)+(b-1))/2}={a-1 \choose (a+b)/2-1}$
The number of paths of this type from $(1,-1)$ to $(a,b)$ is ${a-1 \choose ((a-1)+(b+1))/2}={a-1 \choose (a+b)/2}$
But you are actually interested in paths to $(n, 2p-n)$, so let $a=n$ and $b=2p-n$ i.e. $p=(a+b)/2$ and the three numbers of paths become ${n \choose p}, {n-1 \choose p-1}, {n-1 \choose p}$ respectively. You want the difference between the second and the third
Another way of looking at these: