# Identity of Binomial sum

I found this identity recently when I was trying to find a formula for a trace of power of $$2\times 2$$ matrices, \begin{align*} n \sum_{k = 0}^n \frac{(-1)^k}{2n - k} {2n - k, \choose k} x^k y^{2n - 2k} = \frac{1}{2^{2n}} \sum_{k =0}^n {2n\choose 2k} y^{2k} (y^2 - 4x)^{n - k}. \end{align*} Both sides equal to half of trace of a matrix with determinant $$x$$ and trace $$y$$.

I have tried expanding the $$y^2 - 4x$$ using binomial identity and got \begin{align*} &\frac{1}{2^{2n}} \sum_{k = 0}^n {2n\choose 2k} y^{2k} \sum_{m = 0}^{n - k}{n - k\choose m}(-1)^m(4x)^m y^{2n - 2k - 2m} \\ &= \frac{1}{2^{2n}} \sum_{k = 0}^n \sum_{m = 0}^{n - k} {2n \choose 2k}{n - k\choose m}(-1)^m (4x)^m y^{2n - 2m} \end{align*} This is where I got stuck. Any idea?

Update: I tried to expand the last form, \begin{align*} \frac{1}{2^{2n}}&\Bigg[\sum_{m = 0}^n {2n\choose 0}{n\choose m}(-1)^m(4x)^my^{2n - 2m}\\ +&\sum_{m = 0}^{n - 1} {2n\choose 2}{n - 1\choose m}(-1)^m(4x)^my^{2n - 2m}\\ +&\sum_{m = 0}^{n - 2} {2n\choose 4}{n - 2\choose m}(-1)^m(4x)^my^{2n - 2m}\\ +&\vdots\\ +&\sum_{m = 0}^{n - n} {2n\choose 2n}{n - n\choose m}(-1)^m(4x)^my^{2n - 2m}\Bigg], \end{align*} and got that the coefficient of $$x^k y^{2n - 2k}$$ in above expression is just $$\frac{1}{2^{2n}}\sum_{m = 0}^{n - k}{2n\choose 2m}{n - m\choose k} (-1)^k 4^k.$$ This left me with proving that $$\frac{n}{2n - k} {2n - k\choose k} =\sum_{m = 0}^{n - k}{2n\choose 2m}{n - m\choose k} 2^{2k - 2n}.$$ Again, I got stuck at this point. Any hint?

We seek to show that

$$n\sum_{k=0}^n \frac{(-1)^k}{2n-k} {2n-k\choose k} x^k y^{2n-2k} = \frac{1}{2^{2n}} \sum_{k=0}^n {2n\choose 2k} y^{2k} (y^2-4x)^{n-k}.$$

We compare the coefficient on $$[x^q]$$ of the LHS and the RHS where $$0\le q\le n$$ and show that they are equal. We must therefore show that

$$n \frac{(-1)^q}{2n-q} {2n-q\choose q} y^{2n-2q} = [x^q] \frac{1}{2^{2n}} \sum_{k=0}^n {2n\choose 2k} y^{2k} (y^2-4x)^{n-k}.$$

The RHS is

$$[x^q] \frac{1}{2^{2n}} \sum_{k=0}^n {2n\choose 2n-2k} y^{2n-2k} (y^2-4x)^{k} \\ = \frac{1}{2^{2n}} \sum_{k=q}^n {2n\choose 2n-2k} y^{2n-2k} [x^q] (y^2-4x)^{k} \\ = \frac{1}{2^{2n}} \sum_{k=q}^n {2n\choose 2k} y^{2n-2k} {k\choose q} (-4)^q y^{2k-2q} \\ = y^{2n-2q} \frac{1}{2^{2n}} \sum_{k=q}^n {2n\choose 2k} {k\choose q} (-4)^q.$$

We have reduced the claim to

$$n \frac{(-1)^q}{2n-q} {2n-q\choose q} = \frac{1}{2^{2n}} \sum_{k=q}^n {2n\choose 2k} {k\choose q} (-4)^q.$$

The RHS is

$$\frac{1}{2^{2n}} \sum_{k=q}^n {k\choose q} (-4)^q [z^{2n-2k}] (1+z)^{2n} \\ = \frac{(-1)^q}{2^{2n-2q}} [z^{2n}] (1+z)^{2n} \sum_{k=q}^n {k\choose q} z^{2k}.$$

Now when $$k$$ exceeds $$n$$ we get zero from the coefficient extractor, which enforces the range:

$$\frac{(-1)^q}{2^{2n-2q}} [z^{2n}] (1+z)^{2n} \sum_{k\ge q} {k\choose q} z^{2k} \\ = \frac{(-1)^q}{2^{2n-2q}} [z^{2n}] z^{2q} (1+z)^{2n} \sum_{k\ge 0} {k+q\choose q} z^{2k} \\ = \frac{(-1)^q}{2^{2n-2q}} [z^{2n}] z^{2q} (1+z)^{2n} \frac{1}{(1-z^2)^{q+1}} \\ = \frac{(-1)^q}{2^{2n-2q}} [z^{2n-2q}] (1+z)^{2n-q-1} \frac{1}{(1-z)^{q+1}} \\ = \frac{(-1)^q}{2^{2n-2q}} \sum_{p=0}^{2n-q-1} {2n-q-1\choose p} {2n-2q-p+q\choose q} \\ = \frac{(-1)^q}{2^{2n-2q}} \sum_{p=0}^{2n-q-1} {2n-q-1\choose 2n-q-1-p} {2n-q-p\choose q}.$$

Then we have

$${2n-q-1\choose 2n-q-1-p} {2n-q-p\choose q} = \frac{(2n-q-1)! (2n-q-p)}{p! \times q! \times (2n-2q-p)!} \\ = \frac{1}{2n-q} \frac{(2n-q)! (2n-q-p)} {p! \times q! \times (2n-2q-p)!} \\ = \frac{1}{2n-q} {2n-q\choose q} {2n-2q\choose p} (2n-q-p).$$

Substituting we find (here we have included the value for $$p=2n-q$$, which is zero):

$$\frac{(-1)^q}{2^{2n-2q}} \frac{1}{2n-q} {2n-q\choose q} \sum_{p=0}^{2n-q} {2n-2q\choose p} (2n-q-p).$$

Working with the remaining sum we note that $$(2n-2q)^\underline{p} = 0$$ when $$p\gt 2n-2q$$ and $$2n-q\ge 2n-2q$$ so we may continue with

$$\sum_{p=0}^{2n-2q} {2n-2q\choose p} (2n-q-p) = (2n-q) 2^{2n-2q} - \sum_{p=1}^{2n-2q} {2n-2q\choose p} p \\ = (2n-q) 2^{2n-2q} - (2n-2q) \sum_{p=1}^{2n-2q} {2n-2q - 1\choose p-1} \\ = (2n-q) 2^{2n-2q} - (2n-2q) 2^{2n-2q-1} = (2n-q) 2^{2n-2q} - (n-q) 2^{2n-2q} \\ = n 2^{2n-2q}.$$

Substituting we at last obtain

$$n \frac{(-1)^q}{2n-q} {2n-q\choose q}$$

which was to be shown.