Prove $\sum_k{2k\choose k}^2{2\left(n-k\right)\choose n-k}^2=\sum_k(-1)^k16^k{n-k \choose k}{2\left(n-k\right)\choose n-k}^3$

Question

So I've come across this one :

$$\forall n\in\mathbb{N},\sum\limits_{k=0}^{n}\left[{2k\choose k}{2\left(n-k\right)\choose n-k}\right]^2=\sum\limits_{k=0}^{\left\lfloor{\frac{n}{2}}\right\rfloor}\left(-1\right)^k16^k{n-k \choose k}{2\left(n-k\right)\choose n-k}^3$$ It looks nice, but since I am not really familiar with combinatorics, I have no clue as how to prove it.

What would you suggest ?

Answer 1

Not an answer but too long for a comment. The Maple sumtools package features an implementation of Zeilberger's algorithm, exported through the sumrecursion command. This will produce the same recurrence for the LHS and the RHS. Then we just need to check the two initial values. This is the Maple transcript.

> with(sumtools);
[Hypersum, Sumtohyper, extended_gosper, gosper, hyperrecursion, hypersum,

    hyperterm, simpcomb, sumrecursion, sumtohyper]

> sumrecursion(binomial(2*k,k)^2*binomial(2*n-2*k,n-k)^2, k,S(n));
              3                             2                             3
   256 (n - 1)  S(-2 + n) - 8 (2 n - 1) (2 n  - 2 n + 1) S(n - 1) + S(n) n

> sumrecursion((-1)^k*16^k*binomial(n-k,k)*binomial(2*n-2*k,n-k)^3, k, S(n));
              3                             2                             3
   256 (n - 1)  S(-2 + n) - 8 (2 n - 1) (2 n  - 2 n + 1) S(n - 1) + S(n) n

> A := n -> add(binomial(2*k,k)^2*binomial(2*n-2*k,n-k)^2, k=0..n);
                                 2                           2
   A := n -> add(binomial(2 k, k)  binomial(2 n - 2 k, n - k) , k = 0 .. n)

> seq(A(n), n=1..5);
                          8, 88, 1088, 14296, 195008

> B := n -> add((-1)^k*16^k*binomial(n-k,k)*binomial(2*n-2*k,n-k)^3, k=0..n);
B := n ->

            k   k                                              3
    add((-1)  16  binomial(n - k, k) binomial(2 n - 2 k, n - k) , k = 0 .. n)

> seq(B(n), n=1..5);
                          8, 88, 1088, 14296, 195008

The common recurrence is

$$256\, \left( n-1 \right) ^{3}S \left( n-2 \right) -8\, \left( 2\,n-1 \right) \left( 2\,{n}^{2}-2\,n+1 \right) S \left( n-1 \right) +S \left( n \right) {n}^{3} = 0.$$

This is a classic example from the foreword to the book A=B by Petkovsek, Wilf, and Zeilberger, and identified as such at OEIS A036917.