Sum of multinomals = sum of binomials: why? I stumbled on the following identity, which has been checked numerically.

Question. Is this true? If so, any proof?
  $$\sum_{j=0}^{\lfloor\frac{k}2\rfloor}\binom{n-2k+j}{j,k-2j,n-3k+2j}
=\sum_{j=0}^{\lfloor\frac{k}2\rfloor}\binom{n-k-2j-1}{k-2j}.$$

Here, $\binom{m}{a,b,c}$ is understood as $\frac{m!}{a!\,b!\,c!}$.
 A: 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$.
A: 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.
