2
$\begingroup$

I need the following identity in my research and have a rather ugly proof but cannot find anything more elegant.

If $L\colon\mathbb{Q}[m]\to\mathbb{Q}[m]$ is a linear map which satisfies $L\left(\binom{m}{c+d}\right)=L\left(\binom{m}{c}\right)L\left(\binom{m}{d}\right)$ for all integer $c,d\geq0$, then $L$ also satisfies $L\left(\binom{m+a+b}{c+d}\right)=L\left(\binom{m+a}{c}\right)L\left(\binom{m+b}{d}\right)$ for all integer $a,b,c,d\geq0$.

We shall proceed by induction on $a+b$. For the base case where $a+b=0$, $a=b=0$ and the result is a re-indexed form of the assumption on $L$. Now suppose that the result holds for all $a+b=n$ and that $a+b=n+1$. Without loss of generality, $a\geq1$. Then by Pascal's identity and the inductive assumption, \begin{align*} L\left(\binom{m+a+b}{c+d}\right)&=L\left(\binom{m+(a-1)+b}{(c-1)+d}\right)+L\left(\binom{m+(a-1)+b}{c+d}\right)\\ &=L\left(\binom{m+(a-1)}{c-1}\right)L\left(\binom{m+b}{d}\right)+L\left(\binom{m+(a-1)}{c}\right)L\left(\binom{m+b}{d}\right)\\ &=L\left(\binom{m+(a-1)}{c-1}+\binom{m+(a-1)}{c}\right)L\left(\binom{m+b}{d}\right)\\ &=L\left(\binom{m+a}{c}\right)L\left(\binom{m+b}{d}\right) \end{align*} which shows the inductive step and completes the proof. Does anyone have a better proof of this? Furthermore, is this the sort of result one would include in a paper or exclude as obvious enough for the reader to conclude?

$\endgroup$
  • $\begingroup$ There is no reason to require the target of $L$ to be $\mathbb{Q}\left[m\right]$. It can just as well be any ring. Other than that, nice lemma and very nice proof! $\endgroup$ – darij grinberg Oct 15 '16 at 21:38
3
$\begingroup$

Vandermonde's identity and diagonal summation can be used to give a non-inductive proof: \begin{align*} L\left(\binom{m+a}{c}\right)L\left(\binom{m+b}{d}\right)&=L\left(\sum_{i=0}^c\binom{m}{i}\binom{a}{c-i}\right)L\left(\sum_{j=0}^d\binom{m}{j}\binom{b}{d-j}\right)\\ &=\sum_{i=0}^c\sum_{j=0}^d\binom{a}{c-i}\binom{b}{d-j}L\left(\binom{m}{i}\right)L\left(\binom{m}{j}\right)\\ &=\sum_{k=0}^{c+d}L\left(\binom{m}{k}\right)\sum_{i=0}^c\binom{a}{c-i}\binom{b}{d-(k-i)}\\ &=L\left(\sum_{k=0}^{c+d}\binom{m}{k}\binom{a+b}{c+d-k}\right)\\ &=L\left(\binom{m+a+b}{c+d}\right). \end{align*}

$\endgroup$
  • $\begingroup$ This is a nice proof, which has the additional advantage that it works for any two integers $a$ and $b$ (not necessarily nonnegative). However, I wouldn't call it simpler than the induction proof in the original post... $\endgroup$ – darij grinberg Oct 15 '16 at 21:40
1
$\begingroup$

One person's opinion, but I don't think you're going to come up with a more elegant proof (not sure why you think yours is not!), and I think you should include this as a lemma. Though the proof is straightforward, I don't think it's obvious.

$\endgroup$

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.