Counting North-East Lattice Paths I have been assigned the following homework problem: > Let $f(m,n)$ be the number of north-east lattice paths which exist from $(0,0)$ to $(m,n)$. > > (i) Show that $f(m,n) = f(m-1,n) + f(m,n-1)$. > > (ii) Show by induction that $f(m,n) = \binom{n+m}{n}$. I've been reading around (the concept of north-east lattice paths is entirely new to me), but still cannot seem to wrap my head around an approach to this problem. Any help would be greatly appreciated!

Assuming $m,n >0$, we have the picture below. The only ways to get to $(m,n)$ are to start at $(m-1,n)$ and go east or start at $(m,n-1)$ and go north.

Since the last segment of the path is distinct, for $m,n>0$ we have $f(m,n) = f(m-1,n)+f(m,n-1)$.

![enter image description here](

If $m=0$ and $n>0$, we see that there is only one path and $f(0,n) = n$. Similarly, $f(m,0) = m$.

Using induction, we see that once we specify the south west boundary values, that all the other values are uniquely defined.

It is easy to check that $f(0,n) = \binom{n}{n}$ and $f(m,0) = \binom{m}{m}$, and since $\binom{n+m}{n} = \binom{n+m-1}{n} + \binom{n+m-1}{n-1} $, we see that $g(m,n) = \binom{n+m}{n}$ satisfies the difference equation and the boundary conditions, hence $f=g$.