Prove $\sum_{r=0}^n \binom{n}{r} \binom{n+r}{r} (-2)^r =(-1)^n\sum_{r=0}^n \binom{n}{r}^2 2^r$

Question

Here is a combinatorics question that I am struggling.

Prove $\sum_{r=0}^n \binom{n}{r} \binom{n+r}{r} (-2)^r =(-1)^n\sum_{r=0}^n \binom{n}{r}^2 2^r$

I tried to simply the binomial coefficients on both sides but it does not help.

Is there any possible way to prove it?

Thanks for any comments.

Answer 1

Start with the LHS

$$\sum_{r=0}^n {n\choose r} {n+r\choose r} (-1)^r 2^r = \sum_{r=0}^n {n\choose r} {n+r\choose n} (-1)^r 2^r \\ = \sum_{r=0}^n {n\choose r} (-1)^r 2^r [z^n] (1+z)^{n+r} = [z^n] (1+z)^n \sum_{r=0}^n {n\choose r} (-1)^r 2^r (1+z)^r \\ = [z^n] (1+z)^n (1-2(1+z))^n = [z^n] (1+z)^n (-1-2z)^n \\ = (-1)^n [z^n] (1+z)^n (1+2z)^n.$$

We get for the RHS

$$(-1)^n \sum_{r=0}^n {n\choose r}^2 2^r = (-1)^n \sum_{r=0}^n {n\choose r} {n\choose n-r} 2^r \\ = (-1)^n \sum_{r=0}^n {n\choose r} 2^r [z^{n-r}] (1+z)^n = (-1)^n [z^n] \sum_{r=0}^n {n\choose r} 2^r z^r (1+z)^n \\ = (-1)^n [z^n] (1+z)^n \sum_{r=0}^n {n\choose r} 2^r z^r = (-1)^n [z^n] (1+z)^n (1+2z)^n.$$

The two are identical and we may conclude. (The second one also follows by inspection, we have demonstrated the method here.)

Answer 2

There are two representations for the Legendre polynomials; you can find them on the wiki: $$P_n(x)=\sum_{k=0}^n\binom{n}{k}\binom{n+k}{k}\Big(\frac{x-1}{2}\Big)^k $$ $$P_n(x)=\frac{1}{2^n}\sum_{k=0}^n\binom{n}{k}^2\big(x-1\big)^{n-k} \big(x+1\big)^k\,.$$ Let $x=-3$ in both.