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)]
$$

We can count the number of paths from $(0,0)$ to $(2n+m,m)$, where each step is $(+1,+1)$ or $(+1,-1)$, and which never go below the $x$-axis, using the reflection principle.

There are $\binom{2n+m}{n}$ paths total, including the "bad" paths which touch the line $y=-1$ at some point. Given a bad path, $P$, define a new path, $P_\text{refl}$ as follows. Find the first point, where $P$ intersects the line $y=-1$, and vertically reflect every step after that point to get $P_{\text{refl}}$.

Since $P$ went from the line $y=-1$ up to the line $y=m$ at the end, the reflected path $P_\text{refl}$ will instead go from $y=-1$ down to $y=-m-2$. That is, $P_\text{refl}$ is a path from $(0,0)$ to $(2n+m,-m-2)$. Furthermore, you can show that this reflection map is a bijection from the set of bad paths to $(2n+m,m)$, to the set of all paths from $(0,0)$ to $(2n+m,-m-2)$. It follows that the number of bad paths is
$$
\binom{2n+m}{n-1}.
$$
Therefore, the number of good paths is
$$
\binom{2n+m}{n}-\binom{2n+m}{n-1}.
$$

## Best Answer

Let $A(n,k)$ be the set of Motzkin paths you describe.

Let $B(n,k)$ be the set of walks from $(0,0)$ to $(n,n-2k)$ whose steps are all $(1,1)$ or $(1,-1)$, and which never go below the $x$ axis.

Define $f:A(n,k)\to B(n,k)$ as follows. Given a Motzkin path, replace all of the horizontal steps on the ground with $(1,1)$ steps. For example,

I claim that $f$ is a bijection. The inverse map is this: given a path $P$ in $B(n,k)$, call an up step from $(x,y)$ to $(x+1,y+1)$ "critical" if $P$ never returns to a height of $y$ after that step. Replacing all critical up steps in $P$ with horizontal steps gives a path $Q$ in $A(n,k)$ for which $f(Q)=P$.

Finally, the reflection principle allows you to enumerate paths in $B(n,k)$ to be exactly $\binom nk-\binom n{k-1}$. That is, take the set of all $\binom{n}k$ paths from $(0,0)$ to $(n,n-2k)$, and subtract out the bad paths which at some point go below the $x$ axis. If you reflect that bad paths at the first time they dip below, you get a bijective correspondence to all paths from $(0,0)$ to $(n,2k-n-2)$, counted by $\binom{n}{k-1}$.