Let $m \in \mathbb{N}$ and consider a $2 \times $ rectangular grid with corners at $(0,0), (2,0), (0,),$ and $(2,)$ in the Cartesian plane. Let's call the points $(,)$ in this grid "vertices" and the horizontal and vertical lines connecting two vertices "edges". An ant walks from one vertex to the next along the edges of this grid.
At each vertex $(,)$, the ant has only two choices for its next move - it can move to $(+1,)$ or $(, +1)$. By finding two ways to count the number of paths the ant can follow to get from $(0,0)$ to $(2,)$, construct a combinatorial proof of the identity $$ \sum_{t=0}^m {m \choose t} {2m \choose t} = {3m \choose m} $$
Hint: You may wish to consider the straight line connecting $(0,)$ and $(,0)$.
I am having trouble formulating a combinatorial proof. My work and attempts:
To prove the identity, we will count the number of paths from (0,0) to (2m,m) in two ways.
RHS: First, we observe that each path from $(0,0)$ to $(2m,m)$ must consist of exactly $3m$ steps, of which $2m$ are rightward steps from $(x,y)$ to $(x+1,y)$ and $m$ are upward steps from $(x,y)$ to $(x,y+1)$. Therefore, the number of paths from $(0,0)$ to $(2m,m)$ is given by the number of ways to choose $m$ steps out of $3m$ steps to be upward, which is the same as choosing $2m$ to be rightward.
LHS: I am trying to apply the hint here by considering the number of times the path intersects the diagonal line connecting $(0,0)$ and $(2m,m)$, but still did not figure it out.
Any help would be appreciated!
Continuing with your approach:
LHS: We condition on the number of rightward moves in the first $m$ steps, which can vary from $0$ to $m$. If $t$ of the first $m$ moves are rightward, then $m - t$ of the first $m$ steps are upwards, so $t$ of the final $2m$ steps must be upwards. Hence, the number of paths from $(0, 0)$ to $(2m, m)$ which pass through the point $(t, m - t)$ is $$\binom{m}{m - t}\binom{2m}{t} = \binom{m}{t}\binom{2m}{t}$$ Hence, the number of admissible paths from $(0, 0)$ to $(2m, m)$ is $$\sum_{t = 0}^{m} \binom{m}{t}\binom{2m}{t}$$
Sanity Check: Note that $$\sum_{t = 0}^{m} \binom{m}{t}\binom{2m}{t} = \sum_{t = 0}^{m} \binom{m}{m - t}\binom{2m}{t} = \binom{3m}{m}$$ by Vandermonde's identity.
Note: Observe that the point $(t, m - t)$ is on the diagonal line connecting $(0, m)$ to $(m, 0)$, so we have implicitly used the hint.