number of paths in the Cartesian plane which don't intersect the line $y = x+1/2$

Question

a problem asks to find the number of paths, consisting of solely rightward and upward movements, starting from the origin to point $(a, b)$ (where $a$ and $b$ are positive integers and $a \geq b$) which don't intersect the line $y = x+ 1/2$. I have approached this by considering all the paths without the constraint which amount to $${a+b \choose{a}}$$ since every path has length $a+b$ and consists of exactly $a$ rightward steps. Now, to find the number of paths that intersect the line, I considered all the paths which intersect the line at different $x$ values and summed them all. For instance, at $x = 0$, the path must move up by one to intersect the line ending up at point $(0, 1)$ and, from there, $${a+b-1 \choose{a}}$$ paths will bring to point $(a, b)$. Repeating this for values of $0\leq x<b$ we obtain the following summation of illegal paths: $$\sum\limits_{i = 0}^{b-1} {a+b-(2i+1) \choose{a-i}} $$ so my final answer is $$n_{\textrm{paths}} = {a+b \choose{a}}-\sum\limits_{i = 0}^{b-1} {a+b-(2i+1) \choose{a-i}}.$$ Unfortunately, the answer proposed is instead $$n_{\textrm{paths}} = {a+b \choose{a}} - {a+b \choose{b-1}}$$ which is not equivalent to the expression above. Where is the flaw in my reasoning?

Answer 1

In the $i^{th}$ term of your summation, you are counting the "bad" paths which intersect the line $y=x+\frac12$ when they move from $(i,i)$ to $(i,i+1)$. To specify such a path, you need to choose

1. A path from $(0,0)$ to $(i,i)$, and

2. A path from $(i,i+1)$ to $(a,b)$.

You are correct that the number of ways to do the second task is $\binom{a+b-(2i+1)}{a-i}$. However, you have not accounted for the number of ways to do the first part, which is $\binom{2i}i$.

However, it is still not as simple as $$ n_\text{paths}=\binom{a+b}{a}-\sum_{i=0}^{b-1}\binom{2i}i\binom{a+b-(2i+1)}{a-i} $$ The problem now is that you are double counting the bad paths which cross the line twice. For example, when $(a,b)=(4,3)$, then the below path would be subtracted in both the $i=0$ and $i=2$ terms of the sum.

        • – • – •  
        |         ↖ (4,3)
        •
        |
• – • – •
|
•   
   ↖ (0,0)

One way to fix the double counting would be to break up the bad paths based on the first time that they cross the line $y=x+\frac12$. However, then instead of $\binom{2i}i$, you would need to count the number of ways to reach $(i,i)$ without crossing $y=x+\frac12$ on the way, which is just as hard as your original problem.

Instead, a better way to count the number of bad paths is to use the reflection principle.