In search of a binomial identity proof

Question

The following has strong experimental evidence.

Question. For $n\geq3k$, is this identity true? 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}{n-2k-1,k-2j}.$$

Answer 1

I use a common notation $[x^ay^b]f(x,y)$ for a coefficient of $x^ay^b$ in the series $f(x,y)$.

LHS equals $[t^kz^{n-2k}]\sum_{j=0}^{k/2} (t^2+tz+z)^{n-2k+j}$, and we may extend the summation for $j$ from $2k-n$ to $\infty$ as our monomial $t^kz^{n-2k}$ does not appear in other summands. That is, $$LHS=[t^kz^{n-2k}]\sum_{s=0}^{\infty} (t^2+tz+z)^{s}=[t^kz^{n-2k}]\frac1{1-t^2-tz-z^2}=\\ =[t^kz^{n-2k}]\frac1{2-z}\left(\frac1{1+t}+\frac1{1-t-z}\right)=[z^{n-2k}]\left(\frac{(-1)^k}{2-z}+\frac1{(1-z)^{k+1}(2-z)}\right). $$ As for RHS, it equals, where $m=[k/2]$, $$ [x^{n-2k-1}]\sum_{j=0}^{m}(1+x)^{n-k-2j-1}=[x^{n-2k-1}](1+x)^{n-k-1}\sum_{j=0}^{m} (1+x)^{-2j}=\\ [x^{n-2k-1}](1+x)^{n-k-1}\frac{1-(1+x)^{-2m-2}}{1-(1+x)^{-2}}=[x^{n-2k}]\frac{(1+x)^{n-k+1}-(1+x)^{n-k-1-2m}}{2+x}. $$ Looks similar, but still bit different. Well, do not give up and prove that two expressions are equal. Denoting $z=-x$ in the expression for LHS we have to prove that $$ (1)\,\,\,\,[x^{n-2k}]\frac{(-1)^{n+k}-(1+x)^{n-k+1}+(-1)^n(1+x)^{-k-1}+(1+x)^{n-k-1-2m}}{2+x}=0. $$ Expand a geometric progression $$\frac{(-1)^{n+k}+(-1)^n(1+x)^{-k-1}}{2+x}=\sum_{s=0}^k(-1)^{n+s}(1+x)^{s-k-1}.$$ We may add if necessary a summand corresponding to $s=k+1$ (it has zero coefficient of $x^{n-2k}$ in any case) and get $$ (-1)^{n+1}x\sum_{s=0}^m (1+x)^{2s-k-1}. $$ A coefficient of $x^{n-2k}$ equals $$(-1)^{n+1}\sum_{s=0}^m\binom{2s-k-1}{n-2k-1}=\sum_{s=0}^m\binom{n-k-2s-1}{n-2k-1}.$$ But two other terms of (1) give $$\frac{-(1+x)^{n-k+1}+(1+x)^{n-k-1-2m}}{2+x}=-x(1+x)^{n-k-1-2m}\sum_{t=0}^{m}(1+x)^{2t}.$$ We see that a coefficient of $x^{n-2k-1}$ succesfully cancels with the previous expression.