Does this equation hold in general?

Question

I have a conjecture, that the following holds for arbitrary integers $n$, $k$ such that $0\leq k \leq n$:

$$\sum_{a=0}^{n} \sum_{b=\max[0,a-(n-k)]}^{\min[k,a]} \sum_{c=\max[0,a-(n-k)]}^{\min[k,a]} a (n-a)!a!{k\choose{b}}{k\choose{c}}{n-k\choose{a-b}}{n-k\choose{a-c}}(-1)^{b+c}=2^{n-1}nk!(n-k)!$$

So far, I haven't been able to find a counter-example or to prove it. I checked for many values of $n$ and $k$ numerically and I found that it is true for $n\leq 200$.

Answer 1

Thanks to Sudix I found this answer that helped me find out the solution, which I will repeat here for the sake of completeness (I corrected one mistake in the expression for $a_{m,k}$).

So, first let us re-label the summation indices in the conjecture to coincide with the notation of the cited answer that we will use ($k\rightarrow m$, $a\rightarrow k$, $b\rightarrow r$ and note what Sudix also pointed out, that the the sums are summing the same thing, therefore it is squared):

$$\sum_{k=0}^{n} k {n\choose{m}}{n\choose{k}}^{-1} \left(\sum_{r=\max[0,k+m-n]}^{\min[m,k]} (-1)^{r} {m\choose{r}}{n-m\choose{k-r}}\right)^2=2^{n-1}n$$

The credit for this proof goes to Dan Carmon.

Let $V$ be the space of homogeneous polynomial of degree $n$ in 2 variable $x$ and $y$ and let $T$ be the linear map defined as: $T(p)(x,y)=p(x+y,x-y)$.

Now note that: $T^{2}(p)(x,y)=T(p)(x+y,x-y)=p((x+y)+(x-y)),(x+y)-(x-y))=p(2x,2y)=2^{n}p(x,y)$

Let $A$ be the matrix representation of the linear transformation $T$ with the base $\left \{ x^{n},x^{n-1}y,...,xy^{n-1},y^{n} \right.\left. \right \}$

$\sum_{k=0}^{n}a_{m,k}x^{n-k}y^{k}=T(x^{n-m}y^{m})=(x-y)^{m}(x+y)^{n-m}\\=\sum_{k=0}^{n}\sum_{r=max(0,k+m-n)}^{min(m,k)}(-1)^{r}\binom{m}{r}\binom{n-m}{k-r}x^{n-k}y^{k}$

We are getting closer to end because now we know that $a_{m,k}=\sum_{r=max(0,k+m-n)}^{min(m,k)}(-1)^{r}\binom{m}{r}\binom{n-m}{k-r}$

and with sum (some) manipulation $\binom{m}{r}\binom{n-m}{k-r}\binom{n}{m}=\frac{m!(n-m)!n!}{r!(m-r)!(k-r)!(n-m-k+r)!(m-n)!m!}\\=\frac{n!}{r!(m-r)!(k-r)!(n-m-k+r)!}=\frac{n!(n-k)!k!}{r!(m-r)!(k-r)!(n-m-k+r)!k!(n-k)!}=\binom{k}{r}\binom{n-k}{m-r}\binom{n}{k}$

So $\binom{n}{m}a_{m,k}=\binom{n}{k}a_{k,m}$

The identity we seek to prove is equivalent to $\sum_{k=0}^{n}\frac{\binom{n}{m}a_{m,k}^{2}}{\binom{n}{k}}=2^{n}$

but the last identity yield:

$\sum_{k=0}^{n}\frac{\binom{n}{m}a_{m,k}^{2}}{\binom{n}{k}}=\sum_{k=0}^{n}a_{m,k}a_{k,m}=\left [ A^{2} \right ]_{m,m}=\left [ 2^{n} I\right ] _{m,m}=2^{n} $

$\blacksquare$

Note, that with the expression for $a_{m,k}$ we can rewrite what we have to prove:

$$\sum_{k=0}^{n} k {n\choose{m}}{n\choose{k}}^{-1} a_{m,k}^2=2^{n-1}n\tag{1}\label{1}$$

It is important to note that everything that has been said in the proof before stays valid. Therefore, using that $\binom{n}{m}a_{m,k}=\binom{n}{k}a_{k,m}$ we can write that $$\sum_{k=0}^{n} k {n\choose{m}}{n\choose{k}}^{-1} a_{m,k}^2=\sum_{k=0}^{n}k \,a_{m,k}a_{k,m}\tag{2}\label{2}$$

Let us note, that

$$a_{m,k}a_{k,m}=a_{m,n-k}a_{n-k,m}\tag{3}\label{3}$$ (see proof below)

Consider the following identity (we are summing the very same thing going through the same indices just from the other direction) $$\sum_{k=0}^{n}k \,a_{m,k}a_{k,m}=\sum_{k=0}^{n}(n-k) \,a_{m,n-k}a_{n-k,m}\tag{4}\label{4}$$

Using \eqref{3} we have that

$$\sum_{k=0}^{n}k \,a_{m,k}a_{k,m}=\sum_{k=0}^{n}(n-k) \,a_{m,k}a_{k,m}\tag{5}\label{5}$$ $$2\sum_{k=0}^{n}k \,a_{m,k}a_{k,m}=n\sum_{k=0}^{n} \,a_{m,k}a_{k,m}\tag{6}\label{6}$$ We know from the proof that $\sum_{k=0}^{n} \,a_{m,k}a_{k,m}=2^n$. Therefore, we have that $$\sum_{k=0}^{n}k \,a_{m,k}a_{k,m}=n2^{n-1}$$ which is exactly what we wanted (see \eqref{2}).

Now let us prove \eqref{3}.

$$a_{m,k}=\sum_{r=max(0,k+m-n)}^{min(m,k)}(-1)^{r}\binom{m}{r}\binom{n-m}{k-r}\tag{7}\label{7}$$ $$a_{m,n-k}=\sum_{r=max(0,m-k)}^{min(m,n-k)}(-1)^{r}\binom{m}{r}\binom{n-m}{n-k-r}=\sum_{r=max(0,m-k)}^{min(m,n-k)}(-1)^{r}\binom{m}{m-r}\binom{n-m}{k+r-m}$$

Now if we introduce $s=m-r$ and we take care of the limits we get \eqref{7} and an extra $(-1)^m$ factor, that is $a_{m,k}=(-1)^m a_{m,n-k}$. It is easy to check that also $a_{k,m}=(-1)^m a_{n-k,m}$. Therefore, $$a_{m,k}a_{k,m}=(-1)^{2m} a_{m,n-k}a_{n-k,m}=a_{m,n-k}a_{n-k,m}$$.

Thank you for all your help! A nice combinatorical solution as InterstellarProbe suggested would still be desirable though.

Answer 2

Not an answer:

First, we can simplify the sums as follows: $$ \sum_{a=0}^{n} \sum_{b=\max[0,a-(n-k)]}^{\min[k,a]} \sum_{c=\max[0,a-(n-k)]}^{\min[k,a]} a (n-a)!a!{k\choose{b}}{k\choose{c}}{n-k\choose{a-b}}{n-k\choose{a-c}}(-1)^{b+c} \\= \\ \sum_{a=0}^{n} \sum_{b=0}^{\infty} \sum_{c=0}^{\infty} a (n-a)!a!{k\choose{b}}{k\choose{c}}{n-k\choose{a-b}}{n-k\choose{a-c}}(-1)^{b+c} \\=\\ \sum_{a=0}^{n}a (n-a)!a! \sum_{b=0}^{\infty} \sum_{c=0}^{\infty} {k\choose{b}}{k\choose{c}}{n-k\choose{a-b}}{n-k\choose{a-c}}(-1)^{b+c} \\=\\ n!\sum_{a=0}^{n}a {\binom n a}^{-1} \sum_{b=0}^{\infty} \sum_{c=0}^{\infty} {k\choose{b}}{k\choose{c}}{n-k\choose{a-b}}{n-k\choose{a-c}}(-1)^{b+c} $$ Now let's look at the inner sums (I'm representing them as generating functions, that's why I add the variable $x$. Later on, we can evaluate the generating function at $x=1$): $$ \sum_{b=0}^{\infty} \sum_{c=0}^{\infty} {k\choose{b}}{k\choose{c}}{n-k\choose{a-b}}{n-k\choose{a-c}}(-1)^{b+c} x^b x^c \\=\\ \sum_{b=0}^{\infty} \sum_{c=0}^{\infty} \left((-1)^b {k\choose{b}} {n-k\choose{a-b}} x^b\right) \left((-1)^{c}{k\choose{c}}{n-k\choose{a-c}} x^c \right) \\=\\ \left(\sum_{b=0}^{\infty} (-1)^b {k\choose{b}} {n-k\choose{a-b}} x^b\right) \left(\sum_{c=0}^{\infty} (-1)^{c}{k\choose{c}}{n-k\choose{a-c}} x^c \right) \\=\\ \left(\sum_{b=0}^{\infty} (-1)^b {k\choose{b}} {n-k\choose{a-b}} x^b\right)^2 $$ We replace the inner sums by the easier formula: $$ n!\sum_{a=0}^{n}a {\binom n a}^{-1} \left(\sum_{b=0}^{\infty} (-1)^b {k\choose{b}} {n-k\choose{a-b}} x^b\right)^2 $$

This sum however is, up to the factor $a$, equal to the sum in this question.

As the formulas and the result are similar the chances are that one can use the idea of the answer in the linked question to arrive at a result, or alternatively transform the sum.