I'm trying to calculate the coefficient values for $f(x) = \sum_{k=0}^n {n \choose k}^2 (1+x)^{2n-2k}(1-x)^{2k}$. TL;DR I don't know where to begin in order to prove:

$$\sum_{k=0}^r (-4)^k{n \choose k}{2n-2k \choose n}{n-2k \choose r-k} = {2r \choose r}{2n-2r \choose n-r}$$

Explanation: writing $f(x)$ as the coefficient of $y^n$ in:

\begin{align*} g(x, y) & = [y + (1 + x)^2]^n[y - (1 + x)^2]^n \\\\ & = [(y + 1 + x^2)^2 - 4x^2]^n \end{align*}

shows that this is an even function in $x$, so any nonzero coefficient of $x^l$ requires $l = 2r$ for some integer $r$. Making this substitution and calculating the coefficient of $y^n$ using the Multinomial Theorem gives

\begin{align*} & [x^{2r}][y^n]\left((y+1+x^2)^2 - 4x^2 \right)^n \\ = & [x^{2r}]\sum_{k=0}^n {2n-2k \choose k; n-2k} (-4)^{k}x^{2k}(1+x^2)^{n-2k} \;\text{(Multinomial Expansion)} \\ = & [x^{r}]\sum_{k=0}^n (-4)^k {n \choose k}{2n-2k \choose n}x^k(1+x)^{n-2k} \;\text{($x^2 \to x$ substitution)} \\ = & \sum_{k=0}^r (-4)^k{n \choose k}{2n-2k \choose n}{n-2k \choose r-k} \end{align*}

At this point, I can tell by numerical calculation of the first few values of $n$ and $r$ that this is equal to ${2r \choose r}{2n-2r \choose n-r}$, but despite many attempts at resolving the sum using generating functions and combinatorial arguments I haven't managed to prove it. I would appreciate any help with this or insight into my methods, the sum, or how to prove the value of the coefficient.


1 Answer 1


Suppose we seek to evaluate the coefficients

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

Recall the generating function of the Legendre polynomials

$$\sum_{n\ge 0} P_n(y) t^n = \frac{1}{\sqrt{1-2yt+t^2}}$$

and the known fact

$$P_n(y) = \left[\frac{y-1}{2}\right]^n \sum_{k=0}^n {n\choose k}^2 \left[\frac{y+1}{y-1}\right]^k.$$

Now put $y= -\frac{x^2+1}{2x}$ to get

$$P_n\left(-\frac{x^2+1}{2x}\right) = (-1)^n \frac{(1+x)^{2n}}{4^n x^n} \sum_{k=0}^n {n\choose k}^2 \left[\frac{(1-x)^2}{(1+x)^2}\right]^k.$$

It follows that

$$f_n(x) = (-1)^n 4^n x^n P_n\left(-\frac{x^2+1}{2x}\right).$$

Using the OGF we have

$$(-1)^n 4^n x^n [t^n] \frac{1}{\sqrt{1+((x^2+1)/x)t+t^2}} \\ = [t^n] \frac{1}{\sqrt{1-4(x^2+1)t+16x^2t^2}} \\ = [t^n] \frac{1}{\sqrt{1-4t}} \frac{1}{\sqrt{1-4x^2t}}.$$

We observe at this point that we must have $q=2r$ and continue with

$$[x^{2r}] [t^n] \frac{1}{\sqrt{1-4t}} \frac{1}{\sqrt{1-4x^2t}} \\ = [x^r] [t^n] \frac{1}{\sqrt{1-4xt}} \frac{1}{\sqrt{1-4t}} = [x^r] \sum_{k=0}^n {2k\choose k} x^k {2n-2k\choose n-k} \\ = {2r\choose r} {2n-2r\choose n-r}.$$

This is the claim. One reference for Legendre polynomials is Gould's Combinatorial Identities (page 38).

  • $\begingroup$ This is perfect -- I had worked backward from the result to get $$[t^n] \frac{1}{\sqrt{1-4t}} \frac{1}{\sqrt{1-4x^2t}}$$ but I couldn't figure out how to bridge the gap since I've never used the generating function of the Legendre Polynomials before. Thanks for the help, and the reference! $\endgroup$ Apr 28, 2022 at 23:39
  • $\begingroup$ Thank you for the kind remark. Good to know it helped. $\endgroup$ Apr 29, 2022 at 0:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .