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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.