Deriving a recurrence relation The number of sequences of length $n$ consisting of positive integers such that the opening and ending elements are $1$ or $2$ and the absolute difference between any $2$ consecutive elements is $0$ or 1 is given by $T_{n}$ where
$$T_{n} = \frac{2n+3}{n+3}T_{n-1} + \frac{3n}{n+3}T_{n-2}\;.$$
Moreover $T_{n}$ is $(n+1)^{th}$ Motzkin number.
How to derive above recurrence from the given problem? 
 A: Clearly $T_n$ is the number of sequences of length $n$ of non-negative integers whose first and last elements are in $\{0,1\}$ and whose consecutive terms differ by at most $1$. Sandwiching the sequences between two zeroes gives you the sequences of $y$-coordinates of Motzkin paths of length $n+1$, so $T_n$ is indeed $M_{n+1}$. The recurrence
$$(n+3)T_n=(2n+3)T_{n-1}+3nT_{n-2}$$
therefore corresponds to the Motzkin recurrence
$$(n+2)M_n=(2n+1)M_{n-1}+3(n-1)M_{n-2}\;.\tag{1}$$
A combinatorial proof of this is given in Serge Dulucq & Jean-Guy Penaud, ‘Interprétation bijective d’une récurrence des nombres de Motzkin’, Discrete Mathematics $256$ $(2002)$, $671$-$676$. They first observe that there is a classic bijection between Motzkin paths of length $n$ and complete binary trees with $n+2$ leaves and $n+1$ internal nodes. Let $\mathscr{T}_n$ be the set of such trees. They now consider pointed trees, i.e., trees with one node distinguished. There are $(n+2)M_n$ ways to pick a tree from $\mathscr{T}_n$ and point one of its leaves. There are $(2n+1)M_{n-1}$ ways to pick a tree from $\mathscr{T}_{n-1}$ and point any one of its nodes. And there are $(n-1)M_{n-2}$ ways to pick a tree from $\mathscr{T}_{n-2}$ and point one of its internal nodes. 
Now let $\mathscr{T}_n^\ell$ be the set of trees obtained by pointing a leaf of a tree in $\mathscr{T}_n$, $\mathscr{T}_n^i$ the set of those obtained by pointing an internal node of a tree in $\mathscr{T}_n$, and $\mathscr{T}_n^p$ the set of those obtained by pointing any node of a tree in a tree in $\mathscr{T}_n$. In effect the authors exhibit a bijection between $\mathscr{T}_n^\ell$ and $\mathscr{T}_{n-1}^i\cup 3\mathscr{T}_{n-2}^p$, where $3\mathscr{T}_{n-2}^p$ is the disjoint union of three copies of $\mathscr{T}_{n-2}^p$, thereby establishing $(1)$ and with it your recurrence.
The construction isn’t horrendously complicated, but it’s a bit long and involved to give here in detail, and the diagrams in the paper help a great deal.
