A special class of weighted Motzkin paths 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: It's going to be useful to say that horizontal steps at height $0$ have weight $u$ so that we can derive a recurrence: therefore I shall consider $c_n(t, u)$ and look to specialise it to $u=1$ later.
It's also going to be useful to define an irreducible Motzkin path as either one which begins with an up-step, ends with a down-step, and doesn't touch the axis except at its endpoints; or, as a special case, the unique one-step path. Then every Motzkin path consists of a sequence of irreducible Motzkin paths.
An irreducible path of length $n > 1$ consists of an up-step, a Motzkin path of length $n - 2$ displaced up by one unit, and finally a down-step. The displacement up by a unit requires that $u$ be substituted with $t-1$ (height $0$ becomes height $1$) and that every horizontal step other than on height $0$ result in a multiplication by $-1$. The number of horizontal steps has the same parity as $n$; therefore the sum of the weights of all irreducible paths of length $n > 1$ is $(-1)^n\, t\, c_{n-2}(t, 1-t)$ and by summing over the length of the first irreducible path we get the recurrence $$c_n(t, u) = u c_{n-1}(t, u) + \sum_{j=2}^n (-1)^j\, t\, c_{j-2}(t, 1-t)\, c_{n-j}(t, u)$$
Perhaps it is sensible to define $k_n(t) = c_n(t, 1-t)$; then
$$k_n(t) = (1-t) k_{n-1}(t) + \sum_{j=2}^n (-1)^j\, t\, k_{j-2}(t)\, k_{n-j}(t)$$
$$c_n(t) = c_{n-1}(t) + \sum_{j=2}^n (-1)^j\, t\, k_{j-2}(t)\, c_{n-j}(t)$$
Experimentally we seem to have $$k_n(t) = \sum_{i \ge 0} (-1)^i \binom{\lfloor \frac n2 \rfloor}{\lfloor \frac i2 \rfloor} \binom{\lfloor \frac{n+1}2 \rfloor}{\lfloor \frac{i+1}2 \rfloor} t^i$$
Since $k_n$ is self-contained this can in principle be proven by induction: the sums of binomial coefficients need to be case-split out by parity to get rid of the floors, but then there should be no difficulty handling them automatically with Zeilberger's algorithm. Having done that, the same applies to the recurrence for $c_n$ in terms of $k_n$. The case-splitting makes it tedious, but it is elementary.
A: 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:

*

*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).$$


*Apply Lagrange–Bürmann formula to turn the above expression into a generating function.


*Verify that the obtained generating function is the same as $F_0(x)$.
