Number of lattice paths between two vertical lines There are two vertical lines, $l_1$ from $(0,0)$ to $(0,n)$ and $l_2$ from $(m,0)$ to $(m, n)$.
Prove that the number of north-east lattice paths that start on the line $l_1$ and end on the line $l_2$ are: $$\binom{n+m+2}{n}$$
My initial thought is that smallest possible lattice path would just be a set of horizontal steps and would be of length $m$ and the biggest path would be have $n+m$ steps in total. I am not quite sure how to frame a summation that would give the above combination equation.
 A: Let $P$ be the set of lattice paths from $\ell_1$ to $\ell_2$ using only steps to the north and steps to the east, and let $Q$ be the set of such paths from $\langle -1,0\rangle$ to $\langle m+1,n\rangle$. A path in $Q$ must comprise $m+2$ steps to the east and $n$ steps to the north; these $n+m+2$ steps can occur in any order, and any sequence of such steps is a path in $Q$, so $|Q|=\binom{n+m+2}n$. I claim that there is a bijection between $Q$ and $P$, so that $|P|=\binom{n+m+2}n$ as well.
Suppose that $q\in Q$; $q$ begins with $k$ steps to the north for some $k$ such that $0\le k\le n$, but eventually it must take a step to the east. At that point it intersects $\ell_1$ at $\langle 0,k\rangle$. It continues until it hits $\ell_2$ at some point $\langle m,\ell\rangle$ such that $k\le\ell\le n$. It may proceed north for a bit on $\ell_2$, but at some point $\langle m,j\rangle$ it must go east to $\langle m+1,j\rangle$ and continue north to $\langle m+1,n\rangle$. Let $p_q$ be the part of $q$ from $\langle 0,k\rangle$ to $\langle m,j\rangle$; clearly $p_q\in P$. Conversely, if $p\in P$ starts at $\langle 0,k\rangle$ and ends at $\langle m,j\rangle$, we can extend it to a $q\in Q$ by adding $k$ steps to the north followed by one to the east before $p$ and one to the east followed by $n-m$ to the north after $p$; then clearly $p=p_q$. Thus, the correspondence $q\leftrightarrow p_q$ is a bijection between $Q$ and $P$, and $|P|=\binom{n+m+2}n$.
A: There are
$$
\binom{m+j-i}{m}
$$
ways to start at point $(0,i)$ and finish at point $(m,j)$, so that the total number of ways is
$$
\sum_{0\le i\le j\le n}\binom{m+j-i}{m}=\sum_{k=0}^n(n+1-k)\binom{m+k}m=\binom{m+n+2}n.
$$
The last equality can be proved by induction. Indeed the equality is obviously valid for $n=0$ and arbitrary $m$. Assume it is valid for some $n$. Then it is valid for $n+1$ as well:
$$\begin{align}
\sum_{k=0}^{n+1}(n+2-k)\binom{m+k}m
&=\sum_{k=0}^{n+1}(n+1-k)\binom{m+k}m+\sum_{k=0}^{n+1}\binom{m+k}k\\
&\stackrel{I.H.}=\binom{m+n+2}n+\binom{m+n+2}{n+1}\\
&=\binom{m+n+3}{n+1},
\end{align}$$
where we used the hockey-stick identity.
