Consider Motzkin paths with the following weight:


All up-steps and the horizontal steps on height $0$ have weight $1$, all down-steps have weight $t$ and the horizontal steps on even heights have weight $1-t$ while those on odd heights have weight $t-1.$


Computations suggest that the weight $c\_n(t)$ of all paths of length $n$ is
$$c\_n(t)=\sum\_j\binom{\lfloor{\frac{n-1}{2}}\rfloor}{\lfloor{\frac{j-1}{2}}\rfloor}\binom{\lfloor{\frac{n}{2}}\rfloor}{\lfloor{\frac{j}{2}}\rfloor}t^{j-1}.$$


Is there a simple way to prove this? The use of continued fractions seems to be rather hard.


Could it help that $c\_n(t)$ is the special case for $q=-1$ of the q-Narayana polynomials


$\sum{\binom{n}{j}\_q \binom{n-1}{j}\_q \frac{q^{j^2+j}}{[j+1]\_q} t^j}$?



A special class of weighted Motzkin paths
Let $F\_k(x)$ be a generating function for the total weight of Motzkin paths of length $n$ starting and ending at height $k$ and not going below that height. Let $G\_k(x)$ be a similar generating function with an additional restriction that paths do not come to height $k$, except at the beginning and at the end. Then $c\_n(t)$ is the coefficient of $x^n$ in $F\_0(x)$.


Clearly, we have $F\_{k+2}(x)=F\_k(x)$ for any $k\geq 1$, and $G\_{k+2}(x)=G\_k(x)$ for any $k\geq 0$. Taking into account up and down steps, we also have
$$G\_k(x) = 1 + tx^2F\_{k+1}(x),$$
which we will use for $k\in\{0,1\}$.
Finally, taking into account the weight of horizontal steps, we have
$$\begin{cases}
F\_0(x) = \frac{1}{1-(G\_0(x)-1+x)},\\
F\_1(x) = \frac{1}{1-(G\_1(x)-1+(t-1)x)},\\
F\_2(x) = \frac{1}{1-(G\_0(x)-1+(1-t)x)}.
\end{cases}
$$


This gives us a system of 5 equations w.r.t. $F\_0(x), F\_1(x), F\_2(x)$ and $G\_0(x), G\_1(x)$. Solving it, we get
$$F\_0(x) = \frac{1-2tx+\left(t^{2}-1\right) x^{2}-\sqrt{1-2\left(1+ t^{2}\right) x^{2}+\left(1-t^2\right)^2 x^{4}}}{2 x \left(-1+\left(1+t \right) x \right) t}.$$
Extracting the coefficient of $x^n$ is now a technical task.




---


**ADDED.** Proving the required identity can be done in three straightforward steps:


1. Notice that the sum in question equals the coefficient of $z^n$ in
$$\big((1+z^2)(1+z^2t^2)\big)^{n/2} (1+z^2t) \big(z ((1+z^2)(1+z^2t^2))^{-1/2} + (1+z^2t^2)^{-1}\big).$$
2. Apply Lagrange–Bürmann formula to turn the above expression into a generating function.
3. Verify that the obtained generating function is the same as $F\_0(x)$.


