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)$.
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$.
By applying the distributive property, we see that
$$
(1+x+x^2)^n=\sum_{i_1=0}^2\sum_{i_2=0}^2\cdots \sum_{i_n=0}^2 x^{i_1}x^{i_2}\cdots x^{i_n}\tag1
$$
In words, for each $k\in \{1,\dots,n\}$, $i_k$ represents the power of $x$ selected from the $k^\text{th}$ copy of $(1+x+x^2)$.
To calculate $t_n$, we only care about summands in $(1)$ which contribute to $x^n$. For each way of choosing the sequence $(i_1,\dots,i_n)$ defining a term in the sum, there is a contribution of $+1$ to the coefficient of $x^{i_1+\dots+i_n}$. This proves $t_n$ is the number of valid sequences. That is,
$$
t_n=\#\{(i_1,i_2,\dots,i_n)\mid \forall k: i_k\in \{0,1,2\}, i_1+\dots+i_n=n\}
$$
Here is where the bijective proof comes in. We have represented $t_n$ in terms of sequences of $\{0,1,2\}$ with length $n$. If you subtract one from each entry of such a sequence, you get a sequence with entries in $\{-1,0,1\}$, corresponding to the possible $y$-coordinates of a step for your lattice paths. That is, the bijection from the $\{0,1,2\}$-sequences counted by $t_n$ to the lattice paths counted by $T_n$ is
$$
(i_1,i_2,\dots,i_n)\mapsto [(1,i_1-1),(1,i_2-1),\dots,(1,i_n-1)]
$$
Best Answer
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$.