# Binomial identity in a Change of Basis Matrix

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?

• 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! – darij grinberg Oct 15 '16 at 21:38

## 2 Answers

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*}

• 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... – darij grinberg Oct 15 '16 at 21:40

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.