Sum of multinomals = sum of binomials: why?

For convenience set $m=n-2k$. Then \begin{equation} \begin{split} \binom{n-2k+j}{j,k-2j,n-3k+2j} &= \binom{m+j}{j,k-2j,m-k+2j} \\ &= \binom{m+j}{m} \binom{m}{k-2j} \\ &= [t^j](1-t)^{-(m+1)} \cdot [t^{k-2j}](1+t)^m \\ &= [t^{2j}](1-t^2)^{-(m+1)} \cdot [t^{k-2j}](1+t)^m \end{split} \end{equation} where $[t^a]p$ is the coefficient of $t^a$ in the formal power series $p=p(t)$. Note that $[t^{2j+1}](1-t^2)^{-(m+1)} = 0$. So the left hand side is \begin{equation} \begin{split} [t^k](1-t^2)^{-(m+1)}(1+t)^m &= [t^k](1-t)^{-(m+1)}(1+t)^{-1} \\ &= \sum_{j=0}^k [t^{k-j}](1-t)^{-(m+1)} \cdot [t^j](1+t)^{-1} \\ &= \sum_{j=0}^k \binom{m+k-j}{m} (-1)^j \\ &= \sum_{j=0}^{\lfloor k/2 \rfloor} \binom{m+k-2j}{m} (-1)^{2j} + \binom{m+k-2j-1}{m} (-1)^{2j+1} \\ &= \sum_{j=0}^{\lfloor k/2 \rfloor} \binom{m+k-2j}{m}-\binom{m+k-2j-1}{m} \\ &= \sum_{j=0}^{\lfloor k/2 \rfloor} \binom{m+k-2j-1}{m-1} \end{split} \end{equation} as desired.

As functions of $k$, it appears that both sides satisfy the recurrence \begin{align} & 4(-n+2\,k+1) (-n+2k) A(n,k) \\[6pt] & {} + (8k^2-8\,kn+n^2+10k-9n) A(n,k+1)\\[6pt] & {} + (k+2)(-n+k) A(n,k+2)=0 \end{align} with $A(n,0) = 1$, $A(n,1) = n-2$.