Just to complete the picture, here is a wrap up.

The comments by user61318, Sam Hopkins and Gjergji Zaimi justify the generating function by Ira Gessel
$$\sum_{n\geq0}f_n(2t)x^n=\frac1{(1-x)^{2t}(1-x^2)^{t(2t-1)}},$$
where I replace $t\rightarrow 2t$ for convenience. Expanding the RHS into a Taylor series, we get
$$f_n(2t)=\sum_{k=0}^{\lfloor\frac{n}2\rfloor}\binom{2t^2-t-1+k}k\binom{2t-1+n-2k}{n-2k}.\tag1$$
So, we derive the recurrence $(n+2)f_{n+2}(2t)-2tf_{n+1}(2t)-(4t^2+n)f_n(2t)=0$ for the RHS of (1).
Denote the summand in (1) by $F(n,k)$ (suppressing $t$) and introduce the function
$$G(n,k)=-2k\binom{2t^2-t-1+k}k\binom{2t+1+n-2k}{n-2k+2}.$$
It's routine to check (preferably using a symbolic software) that
\begin{align*}
&(n+2)F(n+2,k)-2tF(n+1,k)-(4t^2+n)F(n,k) \\ =&G(n,k+1)-F(n,k). \tag2
\end{align*}
Summing both sides of (2) over all integers and noting that the RHS telescopes to $0$ reveals the desired recursive relation.

The above proof-technique is called the Wilf-Zeiberger methodology.