Equivalence of two binomial sums

Question

Earlier (Coefficient of terms in expansions) when $f(x)=(1+x+x^2)^n=\sum_{k=0}^{2n} A_k x^k$, $A_k$ has been obtained as $$A_k=\sum_{j=0}^{k} {n\choose j} {j \choose k-j}.......(1)$$ Alternatively, we can obtain $A_k$ by noting that $f(x)=(1-\omega x)^n (1-\omega^2x)^n$ and using the Cauchy product of two series as $$A_k=(-\omega^2)^k \sum_{j=0}^{k} \omega^{-j} {n \choose j} {n \choose k-j}......(2)$$

Here $\omega$ is the cube root of unity.

The question here is: Can we prove the equivalence of these two expressions of $A_k$ as an identity, independently and directly(otherwise)?

Edit: Both (1) and (2) can give $A_k$ only for $0\le k\le n$, for $k>n$ we use the particular feature of the series of $f(x)$ which is $A_{2n-k}=A_k$.

Answer 1

The representation (2) of $A_k$ is for $0\leq k\leq n$: \begin{align*} \color{blue}{A_k}&=[x^k]\left(1+x+x^2\right)^n=[x^k]\left(1-\omega x\right)^n\left(1-\omega^2 x\right)^n\\ &\color{blue}{=\left(-\omega^2\right)^k\sum_{j=0}^k(-\omega)^j\binom{n}{j}\binom{n}{k-j}}\tag{1} \end{align*} Due to symmetry of the polynomial we have $A_k = A_{2n-k}$ where $0\leq k\leq n$.

We obtain from (1) as indicated in the comment by @JeanMarie \begin{align*} \color{blue}{A_k}&\color{blue}{=\sum_{j=0}^n\binom{n}{j}\binom{n}{k-j}(-\omega)^j\left(-\omega^2\right)^{k-j}}\tag{2}\\ &=\sum_{j=0}^{n}\binom{n}{j}(-\omega)^j[z^{k-j}]\left(1-\omega^2z\right)^n\tag{3}\\ &=[z^k]\left(1-\omega^2z\right)^n\sum_{j=0}^n\binom{n}{j}(-\omega z)^j\tag{4}\\ &=[z^k]\left(1-\omega^2z\right)^n(1-\omega z)^n\tag{5}\\ &=[z^k]\left(1-\left(\omega+\omega^2\right)z+\omega^3z^2\right)^n\\ &\,\,\color{blue}{=[z^k]\left(1+z+z^2\right)^n}\tag{6} \end{align*} according to the claim.

Comment:

• In (2) we set the upper limit of the sum to $n$ which does not change anything, since $\binom{n}{k-j}=0$ if $j>k$ according to a common convention.

• In (3) we use the coefficient of operator to denote the coefficient of $z^k$ of a series. This way we can write $[z^k](1+z)^n=\binom{n}{k}$.

• In (4) we use the linearity of the coefficient of operator and apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

• In (5) we apply the binomial theorem.

• In (6) we recall the following properties of the third root of unity $\omega=e^{2i\pi/3}=-1/2(1-i\sqrt{3})$: $\omega+\omega^2=-1$ and $\omega^3=1$.