 North-east lattice path recurrence

For positive integers $a,b$, the north-east lattice path recurrence isThe boundaries have only straight north-east lattice paths. The origin counts the zero-step north-east lattice path once.^[ref]

Proof outline. A north-east lattice path ending at $(a,b)$ has a final step either from $(a-1,b)$ or from $(a,b-1)$. Deleting that step gives a shorter north-east lattice path; appending it reverses the operation. The two classes are disjoint and exhaust all possibilities, so the rule of sum adds their counts. At $(4,3)$, the arrivals from $(3,3)$ contribute $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$, while those from $(4,2)$ contribute $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$: altogether $20+15=35$.

Set $P(a,b)=0$ if either integer coordinate is negative. Then the same recurrence relation applies on the nonnegative axes away from $(0,0)$: one predecessor contributes one, and the other contributes zero. Initialize $P(0,0)=1$ separately; applying the recurrence relation there would incorrectly give zero.

Computing the grid once in increasing order of $a+b$ is dynamic programming: every entry uses two earlier entries. If a specified point is forbidden, set its count to zero, then continue the same recurrence relation at allowed points. This counts north-east lattice paths avoiding the forbidden points, provided the origin and endpoint are allowed. The last-step argument remains valid because appending a step to an allowed endpoint cannot visit any new intermediate integer lattice point.