How to generalize (and not to generalize) the Chu--Vandermonde identity
We consider two different interpretations of the Chu--Vandermonde identity: as an identity for polynomials, and as an identity for infinite matrices. Each interpretation leads to a class of possible generalizations, and in both cases we obtain a complete characterization of the solutions.
\section*{1. Introduction.}

One of the most celebrated formulae of elementary combinatorics
is the Chu--Vandermonde identity
\begin{equation}
   \sum_{k=0}^n \binom{x}{k} \binom{y}{n-k}  \;=\;  \binom{x+y}{n}
 \label{eq.vandermonde}
\end{equation}
(where $n$ is a nonnegative integer);%
\begin{CJK}{UTF8}{bsmi}
it was found by Chu Shih-Chieh (Zh\={u} Sh\`{\i}ji\'e, 朱世杰)%
\end{CJK}
sometime before 1303 \cite{Zhu_2006}
and was rediscovered circa 1772 by Alexandre-Th\'eophile Vandermonde
\cite{Vandermonde_1772}.
If we take $x$ and $y$ to be nonnegative integers,
this identity has a well-known combinatorial interpretation and proof:
we can choose an $n$-person committee from a group of $x$ women and $y$ men
in $\binom{x+y}{n}$ ways;
on the other hand, if this committee is to have $k$ women and $n-k$ men,
then the number of ways is $\binom{x}{k} \binom{y}{n-k}$;
summing over all possible values of $k$ gives the result.
But now, having proven the identity for nonnegative integer $x$~and~$y$,
we can shift gears and regard $x$~and~$y$ as algebraic indeterminates:
then both sides of \reff{eq.vandermonde} are polynomials in $x$~and~$y$
(of total degree~$n$),
which agree whenever $x$~and~$y$ are nonnegative integers;
since two polynomials that agree at infinitely many points must be equal,
it follows that \reff{eq.vandermonde} holds as a polynomial identity
in $x$~and~$y$.

We thus see already from this brief account that the Chu--Vandermonde identity
can be given at least two distinct interpretations.
On the one hand, we can regard $x$~and~$y$ as indeterminates;
then \reff{eq.vandermonde} is the identity
\begin{equation}
    \sum_{k=0}^n f_k(x) \, f_{n-k}(y)  \;=\;  f_n(x+y)
 \label{eq.fksum}
\end{equation}
for the polynomials
\begin{equation}
   f_n(x)  \;=\;  \binom{x}{n}  \;\stackrel{\rm def}{=}\; {x^{\underline{n}} \over n!}
           \;\stackrel{\rm def}{=}\; {x(x-1) \cdots (x-n+1) \over n!}
           \;\in\; {\mathbb Q}[x]
   \;.
 \label{def.f.binomial}
\end{equation}
(Of course, $x$ and $y$ can then be specialized, if we wish,
to specific values in any commutative ring containing the rationals,
such as the real or complex numbers.)
On the other hand, we can restrict $x$ and $y$ to be nonnegative integers;
then \reff{eq.vandermonde} is the identity
\begin{equation}
   \sum_{j=0}^n L_{ij} \, L_{\ell,n-j}  \;=\;  L_{i+\ell,n}
 \label{eq.identity.L}
\end{equation}
for the infinite lower-triangular Pascal matrix
\cite{Call_93,Aceto_01,Edelman_04}
$L = (L_{ij})_{i,j \ge 0}$ defined by
\begin{equation}
   L_{ij}  \;=\;  \binom{i}{j}
   \;.
 \label{def.L.pascal}
\end{equation}

At this point it is natural to ask for generalizations of
\reff{eq.fksum}/\reff{def.f.binomial}
and \reff{eq.identity.L}/\reff{def.L.pascal}, respectively.
Are there other sequences ${\bm{f}} = (f_n)_{n \ge 0}$
of polynomials (or formal power series) satisfying \reff{eq.fksum},
and if so, can we classify them all?
Likewise, are there other lower-triangular matrices $L = (L_{ij})_{i,j \ge 0}$
satisfying \reff{eq.identity.L}, and if so, can we classify them?
The answer to the first question is well known,
and we will review it here (and extend it slightly).
Then we will give a negative answer to the second question,
but with an interesting twist;
some of these latter results seem to be new.

\bigskip

\section*{2. Convolution families.}

Let $R$ be a commutative ring,
and let ${\bm{f}} = (f_n)_{n \ge 0}$
be a sequence of formal power series $f_n(x) \in R[[x]]$.
We will call ${\bm{f}}$ a {\em convolution family}\/
\cite{Knuth_92} (see also \cite{Labelle_80,Zeng_96})
if it satisfies \reff{eq.fksum};
and we will call ${\bm{f}}$ a {\em weak convolution family}\/
if it satisfies \reff{eq.fksum} restricted to $x=y$:
\begin{equation}
    \sum_{k=0}^n f_k(x) \, f_{n-k}(x)  \;=\;  f_n(2x)
   \;.
 \label{eq.fksum.weak}
\end{equation}
We use the notation $[t^n] \, F(t)$
to denote the coefficient of $t^n$ in the formal power series (or polynomial)
$F(t) \in R[[t]]$.
We then have the following characterization of (weak) convolution families:

\begin{proposition}[Characterization of convolution families]
   \label{prop.convfamily}
Let $R$ be a commutative ring containing the rationals,
and let $\Psi(t) = \sum_{n=0}^\infty \psi_n t^n \in R[[t]]$
be any formal power series.
Then
\begin{equation}
   f_n(x)  \;=\;  [t^n] \, e^{x \Psi(t)}
 \label{eq.fn.G.H}
\end{equation}
defines a convolution family in $R[[x]]$.
Moreover, $\widetilde{f}_n(x) \stackrel{\rm def}{=} f_n(x) / e^{\psi_0 x}$
are polynomials in $x$ with $\deg \widetilde{f}_n \le n$
and satisfying $\widetilde{f}_n(0) = 0$ for $n \ge 1$.
[In~particular, the $f_n$ are themselves polynomials for all $n$
 if and only if $\psi_0$ is nilpotent,
 and are polynomials of degree at most $n$ for all $n$
 if and only if $\psi_0 = 0$.]

Conversely, let $R$ be a commutative ring containing the rationals
in which the only idempotents are 0 and 1
(for instance, an integral domain or a local ring),
and let ${\bm{f}} = (f_n)_{n \ge 0}$ be a weak convolution family in $R[[x]]$.
Then either ${\bm{f}}$ is identically zero,
or else there exists a unique formal power series $\Psi \in R[[t]]$
such that \reff{eq.fn.G.H} holds.
In~particular, ${\bm{f}}$ is actually a convolution family,
and the foregoing statements about $\widetilde{f}_n$ hold.
\end{proposition}

\par\medskip\noindent{\sc Proof.\ }
By taking the coefficient of $t^n$ on both sides of the identity
$e^{x \Psi(t)} e^{y \Psi(t)} = e^{(x+y) \Psi(t)}$,
we see, using \reff{eq.fn.G.H}, that
\begin{equation}
    \sum_{k=0}^n f_k(x) \, f_{n-k}(y)  \;=\;  f_n(x+y)
    \;,
\end{equation}
or in other words that ${\bm{f}}$ is a convolution family.
Moreover, it is easy to see that
$f_n(x)/e^{\psi_0 x} = [t^n] \, e^{x [\Psi(t) - \psi_0]}$
is a polynomial in $x$ of degree at most $n$,
which has zero constant term for $n \ge 1$.
For the statements in brackets, ``if'' is easy,
and ``only if'' follows by looking at $n=0$.


For the converse, let us use the notation $f_{nk} = [x^k] \, f_n(x)$.
By using \reff{eq.fksum.weak} specialized to $n=0$ and $x=0$,
we see that $f_{00}^2 = f_{00}$;
so the hypothesis on $R$ implies that either $f_{00} = 0$ or $f_{00} = 1$.
If $f_{00} = 0$, then a simple inductive argument using
\reff{eq.fksum.weak} specialized to $n=0$
shows that $f_{0k} = 0$ for all $k$, i.e., $f_0 = 0$;
and then a second inductive argument using \reff{eq.fksum.weak}
shows that $f_n = 0$ for all $n$.
So we can assume that $f_{00} = 1$.
Define the bivariate ordinary generating function
$F(x,t) = \sum_{n=0}^\infty f_n(x) \, t^n \in R[[x,t]]$.
Since $F$ has constant term $f_{00} = 1$,
we can define $L(x,t) = \log F(x,t) \in R[[x,t]]$,
which has constant term 0.
The identity \reff{eq.fksum.weak}, translated to generating functions,
says that $F(x,t)^2 = F(2x,t)$, or equivalently that $2 L(x,t) = L(2x,t)$.
Writing $L(x,t) = \sum_{k=0}^\infty \ell_k(t) \, x^k$,
we see that $\sum_{k=0}^\infty (2 - 2^k) \, \ell_k(t) \, x^k = 0$
as a power series in $x$,
hence that $\ell_k(t) = 0$ for all $k \neq 1$.
It follows that $L(x,t) = x \Psi(t)$ for some $\Psi \in R[[t]]$.
Therefore $f_n(x) = [t^n] \, e^{x \Psi(t)}$,
as claimed in \reff{eq.fn.G.H}.
Indeed, \reff{eq.fn.G.H} says precisely that $L(x,t) = x \Psi(t)$,
so $\Psi$ is uniquely determined by ${\bm{f}}$.
\hbox{\hskip 6pt\vrule width6pt height7pt depth1pt \hskip1pt}\bigskip

\bigskip

\noindent
{\bf Examples of convolution families.}
1.  The binomial theorem corresponds to $f_n(x) = x^n/n!$
and $\Psi(t) = t$.

2.  The Chu--Vandermonde identity corresponds to
$f_n(x) = \binom{x}{n} = x^{\underline{n}}/n!$
and $\Psi(t) = \log(1 + t)$.

3.  The ``dual Chu--Vandermonde identity'' corresponds to
$f_n(x) = \binom{x+n-1}{n} = x^{\overline{n}}/n!$
and $\Psi(t) = -\log(1 - t)$.

4.  Define the univariate Bell polynomials
$B_n(x) = \sum_{k=0}^n \stirlingsubset{n}{k} x^k$,
where the Stirling number $\stirlingsubset{n}{k}$
is the number of partitions of an $n$-element set into $k$ nonempty blocks
\cite{Graham_94}.
Then $f_n(x) = B_n(x)/n!$ corresponds to $\Psi(t) = e^t - 1$.

\bigskip

\noindent
See \cite{Knuth_92} for many further examples.

\bigskip
\bigskip

\noindent
{\bf Remarks.}
1.  Proposition~\ref{prop.convfamily} is a slight extension of
\cite[Theorem~4.1]{Garsia_73}, \cite{Knuth_92}
and \cite[Exercise~5.37a]{Stanley_99},
in two directions:
allowing the $f_n$ to be formal power series rather than just polynomials,
and allowing the coefficients to lie in a commutative ring containing
the rationals rather than just a field of characteristic~0.
Knuth \cite{Knuth_92} proved the converse half by an inductive argument
based on carefully examining the coefficients $f_{nk}$.
This is nice, but it seems to me that the generating-function argument
using the logarithm, taken from \cite{Garsia_73,Stanley_99},
is simpler and more enlightening.

2.  For the converse, it would alternatively suffice to assume that
\reff{eq.fksum} holds for $y = rx$
for {\em any}\/ fixed rational number $r \neq 0,-1$ (not just $r=1$):
we would then have $L(x,t) + L(rx,t) = L((1+r)x,t)$,
which also implies $L(x,t) = x \Psi(t)$
since $1 + r^m \neq (1+r)^m$ for all $m \in {\mathbb N} \setminus \{1\}$
and all $r \in {\mathbb Q} \setminus \{0,-1\}$.

3.  By iterating \reff{eq.fksum}, we see that every convolution family ${\bm{f}}$
satisfies
\begin{equation}
    \sum\limits_{\begin{scarray}
                    k_1,\ldots,k_m \ge 0 \\
                    k_1 + \ldots + k_m = n
                 \end{scarray}}
    \!\!\!\!\!
    f_{k_1}(x_1) \,\cdots\, f_{k_m}(x_m)  \;=\;  f_n(x_1 + \ldots + x_m)
 \label{eq.fksum.iterated}
\end{equation}
for each integer $m \ge 1$.
This ``multinomial'' version of the identity is sometimes useful.

4.  The foregoing theory can equivalently be expressed
in terms of the polynomials $F_n(x) = n! \, f_n(x)$, which satisfy
\begin{equation}
    \sum_{k=0}^n \binom{n}{k} F_k(x) \, F_{n-k}(y)  \;=\;  F_n(x+y)
    \;.
 \label{eq.Fksum.binomial}
\end{equation}
Sequences of polynomials satisfying \reff{eq.Fksum.binomial}
are called {\em sequences of binomial type}\/;
they were introduced by Rota and collaborators
\cite{Mullin_70,Rota_73,Garsia_73,Fillmore_73,Roman_78,Roman_84}
and studied by means of the umbral calculus
\cite{Roman_78,Roman_84,Rota_94,Gessel_03}.\footnote{
   As part of the definition of ``sequence of binomial type'',
   Rota {\em et al.}\/ \cite{Mullin_70,Rota_73}
   and many subsequent authors \cite{Garsia_73,Fillmore_73,Roman_78,Roman_84}
   imposed the additional condition that $\deg F_n = n$ exactly.
   But this condition is irrelevant for our purposes,
   so we refrain from imposing it.
}
A purely combinatorial approach to sequences of binomial type,
employing the theory of species,
has been developed by Labelle \cite{Labelle_81}
(see also \cite[Section~3.1]{Bergeron_98}).
See also \cite{Zeng_96,Scott-Sokal_expidentities}
for some multivariate generalizations.

The identity \reff{eq.Fksum.binomial}
is closely related to the {\em exponential formula}\/
\cite{Wilf_94,Bergeron_98,Stanley_99}
in enumerative combinatorics,
which relates the weights $c_n$ of ``connected'' objects
to the weights $F_n(x)$ of ``all'' objects,
when the weight of an object is defined to be the product of the weights
of its ``connected components'' times a factor $x$ for each
connected component.
See \cite{Wilf_94,Bergeron_98,Stanley_99,Scott-Sokal_expidentities}
for further discussion and many applications.
 $\blacksquare$ \bigskip


\bigskip

\noindent
{\bf Open questions.}
What happens if $R$ does not contain the rationals,
or if $R$ has idempotents other than 0 and 1?


\bigskip

\section*{3. Convolution families, generalized.}

Let us now generalize the identity \reff{eq.fksum}
by allowing three different sequences $f,g,h$ in place of $f,f,f$:
\begin{equation}
   \sum_{k=0}^n f_k(x) \, g_{n-k}(y)  \;=\;  h_n(x+y)
   \;.
 \label{eq.conv.fgh}
\end{equation}
Do any new solutions arise?
It turns out that the answer is yes, as follows:

\begin{proposition}
   \label{prop.convfamily.bis}
Let $R$ be a commutative ring containing the rationals,
and let $A,B,\Psi \in R[[t]]$.  Then
\begin{equation}
   f_n(x)  \:=\:  [t^n] \, A(t) e^{x \Psi(t)}  \:,\quad
   g_n(x)  \:=\:  [t^n] \, B(t) e^{x \Psi(t)}  \:,\quad
   h_n(x)  \:=\:  [t^n] \, A(t) B(t) e^{x \Psi(t)}
 \label{eq.prop.convfamily.bis}
\end{equation}
are sequences in $R[[x]]$ satisfying \reff{eq.conv.fgh}.
Moreover, $\widetilde{f}_n(x) \stackrel{\rm def}{=} f_n(x) / e^{\psi_0 x}$
[where $\psi_0 \stackrel{\rm def}{=} \Psi(0)$]
are polynomials in $x$ with $\deg \widetilde{f}_n \le n$,
and likewise for $g_n$ and $h_n$.
[In~particular, the $f_n,g_n,h_n$ are themselves polynomials for all $n$
 if and only if $\psi_0$ is nilpotent,
 and are polynomials of degree at most $n$ for all $n$
 if and only if $\psi_0 = 0$.]

Conversely, let $R$ be a commutative ring containing the rationals,
and let
${\bm{f}} = (f_n)_{n \ge 0}$, ${\bm{g}} = (g_n)_{n \ge 0}$, ${\bm{h}} = (h_n)_{n \ge 0}$
be sequences in $R[[x]]$ satisfying \reff{eq.conv.fgh}.
Assume further that $f_0(0)$ and $g_0(0)$ are invertible in $R$
[or equivalently that $h_0(0) = f_0(0) \, g_0(0)$ is invertible in $R$].
Then there exist unique formal power series $A,B,\Psi \in R[[t]]$
such that \reff{eq.prop.convfamily.bis} holds;
and $A$ and $B$ are invertible in $R[[t]]$.
\end{proposition}

\par\medskip\noindent{\sc Proof.\ }
By taking the coefficient of $t^n$ on both sides of the identity
$A(t) e^{x \Psi(t)} \, B(t) e^{y \Psi(t)} = {A(t) B(t) e^{(x+y) \Psi(t)}}$,
we see that \reff{eq.conv.fgh} holds.
The statements about $f_n,g_n,h_n$ are proven
as in Proposition~\ref{prop.convfamily}.

For the converse, let $\alpha = f_0(0)$ and $\beta = g_0(0)$;
by hypothesis $\alpha$ and $\beta$ are invertible, and $h_0(0) = \alpha\beta$.
Define the ordinary generating functions
$F(x,t) = \sum_{n=0}^\infty f_n(x) \, t^n$,
$G(x,t) = \sum_{n=0}^\infty g_n(x) \, t^n$
and $H(x,t) = \sum_{n=0}^\infty h_n(x) \, t^n$;
they have constant terms $\alpha$, $\beta$ and $\alpha\beta$, respectively.
Then define $L(x,t) = \log [\alpha^{-1} F(x,t)]$,
$M(x,t) = \log [\beta^{-1} G(x,t)]$ and
$N(x,t) = \log [(\alpha\beta)^{-1} H(x,t)]$;
they have constant term 0.
The identity \reff{eq.conv.fgh}, translated to generating functions,
says that $F(x,t) \, G(y,t) = H(x+y,t)$,
or equivalently that $L(x,t) + M(y,t) = N(x+y,t)$.
Then we must have $[x^k] N(x,t) = 0$ for $k \ge 2$
in order to avoid terms $x^i y^j$ with $i,j \ge 1$ in $N(x+y,t)$.
It then follows that we must have
\begin{equation}
   L(x,t) \:=\: \Gamma(t) \,+\, x \Psi(t)  \:,\quad
   M(x,t) \:=\: \Delta(t) \,+\, x \Psi(t)  \:,\quad
   N(x,t) \:=\: \Gamma(t) \,+\, \Delta(t) \,+\, x \Psi(t)
\end{equation}
for some formal power series $\Gamma,\Delta,\Psi \in R[[t]]$,
where $\Gamma$ and $\Delta$ have zero constant term.
Then \reff{eq.prop.convfamily.bis} holds with
$A(t) = \alpha e^{\Gamma(t)}$ and $B(t) = \beta e^{\Delta(t)}$.
Furthermore, $L,M,N$ are uniquely determined by ${\bm{f}},{\bm{g}},{\bm{h}}$;
hence $\Gamma,\Delta,\Psi$ are also uniquely determined;
hence $A,B,\Psi$ are uniquely determined as well.
\hbox{\hskip 6pt\vrule width6pt height7pt depth1pt \hskip1pt}\bigskip

\bigskip

{\bf Remarks.}
1.  Under the assumption that $f_0(0)$ and $g_0(0)$ are invertible in $R$,
clearly ${\bm{f}} = {\bm{g}} = {\bm{h}}$ if and only if $A(t) = B(t) = 1$;
and in this case we recover the situation of Proposition~\ref{prop.convfamily}.

2.  If the only idempotents in $R$ are 0 and 1,
then it is not difficult to show that the same holds true in $R[[t]]$. 
In this case ${\bm{f}} = {\bm{g}} = {\bm{h}}$ if and only if
$A(t) = B(t) = 1$ or $A(t) = B(t) = 0$;
and we also recover the situation of Proposition~\ref{prop.convfamily}.

3.  Note that here, unlike in Proposition~\ref{prop.convfamily},
it does not suffice to assume \reff{eq.conv.fgh} only for $x=y$.
Indeed, the equality
\begin{equation}
   \sum_{k=0}^n f_k(x) \, g_{n-k}(x)  \;=\;  h_n(2x)
\end{equation}
can be taken as the {\em definition}\/ of ${\bm{h}}$
for {\em completely arbitrary}\/ sequences ${\bm{f}}$ and ${\bm{g}}$.

4.  The foregoing theory can once again equivalently be expressed
in terms of the polynomials $F_n(x) = n! \, f_n(x)$
and likewise for $g_n$ and $h_n$, which satisfy
\begin{equation}
    \sum_{k=0}^n \binom{n}{k} F_k(x) \, G_{n-k}(y)  \;=\;  H_n(x+y)
    \;.
 \label{eq.FGHsum.binomial}
\end{equation}
Sequences of polynomials $F_n(x) = n! \, f_n(x)$
defined by \reff{eq.prop.convfamily.bis}
are called {\em Sheffer sequences}\/ \cite[pp.~2, 18--19]{Roman_84}.\footnote{
   As part of the definition of ``Sheffer sequence'',
   some authors (e.g.\ \cite[p.~2]{Roman_84})
   impose the additional conditions $A(0) \neq 0$,
   $B(0) = 0$, and $B'(0) \neq 0$.
   But these conditions are irrelevant for our purposes,
   so we refrain from imposing them.
}
Many classical sequences of polynomials ---
including the Hermite, Laguerre and Bernoulli polynomials ---
are Sheffer sequences \cite[pp.~2, 28--31, 53--130]{Roman_84}.
 $\blacksquare$ \bigskip

\bigskip

\noindent
{\bf Open question.}
What happens if $f_0(0)$ and/or $g_0(0)$ are not invertible?


\bigskip



\section*{4. Pascal-like matrices.}

We now turn to the matrix interpretation of the Chu--Vandermonde identity.
But before proceeding further,
let us generalize the identity \reff{eq.identity.L} in two ways:
First, we allow three different matrices $A,B,C$ in place of $L,L,L$;
and second, we do not require $A,B,C$ to be lower-triangular.

So let $A = (a_{ij})_{i,j \ge 0}$ be a matrix with entries
in a commutative ring $R$.  We define the {\em row-generating series}\/
$A_i(u) = \sum_{j=0}^\infty a_{ij} u^j \in R[[u]$.
Clearly, there is a one-to-one correspondence between matrices
$A = (a_{ij})_{i,j \ge 0}$ and collections $(A_i(u))_{i \ge 0}$
of row-generating series.

We then have the following result:

\begin{proposition}[Characterization of Pascal-like matrices]
   \label{prop.pascal-like}
Let $R$ be a commutative ring, and let $f,g,h \in R[[u]]$.
Then
\begin{equation}
   A_i(u) \;=\; f(u) \, h(u)^i   \:,\quad
   B_i(u) \;=\; g(u) \, h(u)^i   \:,\quad
   C_i(u) \;=\; f(u) \, g(u) \, h(u)^i
 \label{eq.ABC.fgh}
\end{equation}
are the row-generating series of matrices
$A = (a_{ij})_{i,j \ge 0}$,
$B = (b_{ij})_{i,j \ge 0}$,
$C = (c_{ij})_{i,j \ge 0}$
satisfying
\begin{equation}
   \sum_{j=0}^n a_{ij} \, b_{\ell,n-j}  \;=\;  c_{i+\ell,n}
   \qquad\hbox{for all $i,\ell,n \ge 0$}
   \;.
 \label{eq.identity.ABC}
\end{equation}

Conversely, suppose that
$A = (a_{ij})_{i,j \ge 0}$,
$B = (b_{ij})_{i,j \ge 0}$,
$C = (c_{ij})_{i,j \ge 0}$
are matrices with entries in a commutative ring $R$
that satisfy \reff{eq.identity.ABC}.
Suppose further that $a_{00}$ and $b_{00}$ are invertible in $R$
[or equivalently that $c_{00} = a_{00} b_{00}$ is invertible in $R$].
Then there exist unique series $f,g,h \in R[[u]]$
such that the row-generating series of $A,B,C$ are given by \reff{eq.ABC.fgh};
and $f$ and $g$ are invertible.
\end{proposition}

\par\medskip\noindent{\sc Proof.\ }
Multiplying \reff{eq.identity.ABC} by $u^n$ and summing over $n$,
we see that \reff{eq.identity.ABC} is equivalent to the equality
\begin{equation}
   A_i(u) \, B_\ell(u)  \;=\;  C_{i+\ell}(u)
   \qquad\hbox{for all $i,\ell \ge 0$}
 \label{eq.AiBl}
\end{equation}
for the row-generating series.
It is immediate that the construction \reff{eq.ABC.fgh}
satisfies \reff{eq.AiBl}.

For the converse, let us write out \reff{eq.AiBl} in detail:
\begin{subeqnarray}
   C_0  & = &  A_0 B_0  \\
   C_1  & = &  A_0 B_1  \;=\;  A_1 B_0  \\
   C_2  & = &  A_0 B_2  \;=\;  A_1 B_1  \;=\;  A_2 B_0  \\
        & \vdots &   \nonumber
\end{subeqnarray}
Since $a_{00}$ and $b_{00}$ are invertible in $R$,
it follows that $A_0$ and $B_0$ are invertible in $R[[u]]$.
From $C_n = A_0 B_n = A_n B_0$, we deduce that $A_n/A_0 = B_n/B_0$;
let us call this common value $h_n$.
Then \reff{eq.AiBl} says (after division by $A_0 B_0$) that
$h_i h_\ell = h_{i+\ell}$ for all $i,\ell$.
It follows by induction that $h_n = h_1^n$.
So \reff{eq.ABC.fgh} holds with $f = A_0$, $g = B_0$, $h = h_1$.
Moreover, it is clear from \reff{eq.ABC.fgh} that $f = A_0$ and $g = B_0$;
and since $A_0$ and $B_0$ are invertible, we must also have $h = A_1/A_0$.
So $f,g,h$ are uniquely determined.
\hbox{\hskip 6pt\vrule width6pt height7pt depth1pt \hskip1pt}\bigskip

\bigskip

\noindent
{\bf Open question.}
What happens if $a_{00}$ and/or $b_{00}$ are not invertible?

\bigskip
\bigskip

{\bf Remarks.}
1.  Under the assumption that $a_{00}$ and $b_{00}$ are invertible in $R$,
clearly $A=B=C$ if and only if $f(u) = g(u) = 1$.
It turns out (as I discovered after completing
the proof of Proposition~\ref{prop.pascal-like})
that the $A=B=C$ special case of Proposition~\ref{prop.pascal-like}
had been proven nearly 40 years ago
by Olive \cite[Theorems~3.2 and 3.3]{Olive_79}.

2.  If $f(t)$ and $h(t)$ are formal power series,
let ${\mathcal{R}}(f,h)$ be the infinite matrix
$({\mathcal{R}}(f,h)_{nk})_{n,k \ge 0}$ defined by
\begin{equation}
   {\mathcal{R}}(f,h)_{nk}
   \;=\;
   [t^n] \, f(t) h(t)^k
   \;.
 \label{def.riordan}
\end{equation}
When $h$ has constant term 0, the matrix ${\mathcal{R}}(f,h)$ is lower-triangular
and is called a {\em Riordan array}\/ \cite{Shapiro_91,Sprugnoli_94,Barry_16};
such matrices arise frequently in enumerative combinatorics,
and the theory of Riordan arrays provides a useful unifying framework.
But --- as a handful of authors have noted
\cite{Bala_15} \cite{Hoggatt_75} \cite[p.~288]{Pemantle_13} ---
there are also interesting examples
in which $h$ has a nonzero constant term.
Let us call this more general concept,
in which $h$ is an arbitrary formal power series,
a {\em wide-sense Riordan array}\/.\footnote{
   References \cite{Pemantle_13,Bala_15}
   call this a ``generalized Riordan array'',
   but we prefer to avoid this term because it has already been used,
   in a highly-cited paper \cite{Wang_08},
   for a completely unrelated generalization of Riordan arrays.
}
We can then see that the matrices $A,B,C$ defined in \reff{eq.ABC.fgh}
are simply the transpose of a wide-sense Riordan array.

3. What is the relation between Propositions~\ref{prop.convfamily.bis}
and \ref{prop.pascal-like}?
Comparing \reff{eq.conv.fgh} with \reff{eq.identity.ABC},
we see that $x,y,k$ correspond to $i,\ell,j$, respectively;
and then, comparing \reff{eq.prop.convfamily.bis} with \reff{eq.ABC.fgh},
we see that $A(t), B(t), e^{\Psi(t)}$
correspond to $f(u), g(u), h(u)$, respectively.
Therefore, if $\Psi(0) = 0$, we can define $h = e^\Psi$ satisfying $h(0) = 1$;
and since in this case the $f_n,g_n,h_n$ are {\em polynomials}\/,
it makes sense to evaluate them at integer arguments
to obtain $f_n(i) = a_{in}$ and analogously for $g$ and $h$.
And conversely, if $h(0) = 1$,
we can define $\Psi = \log h$ satisfying $\Psi(0) = 0$,
and a triplet of matrices $A,B,C$ satisfying \reff{eq.ABC.fgh}
can be extended to a triplet ${\bm{f}},{\bm{g}},{\bm{h}}$
of sequences of polynomials satisfying \reff{eq.prop.convfamily.bis};
once again we can evaluate them at integer arguments
to obtain $f_n(i) = a_{in}$ and analogously for $g$ and $h$.
In other words, when $h(0) = 1$, each column of the matrices $A,B,C$
is a {\em polynomial}\/ function of the index $i$.

If, by contrast, $\Psi(0) \stackrel{\rm def}{=} \psi_0 \neq 0$ or $h(0) \neq 1$,
then Propositions~\ref{prop.convfamily.bis} and \ref{prop.pascal-like}
are incommensurable for general commutative rings $R$.
However, when $R = {\mathbb R}$ or ${\mathbb C}$, we can still define $h = e^\Psi$
satisfying $h(0) = e^{\psi_0}$;
then $f_n(x),g_n(x),h_n(x)$ are polynomials multiplied by $e^{\psi_0 x}$
and can again be evaluated at integer arguments.
And conversely, if $R= {\mathbb R}$ (resp.\ ${\mathbb C}$) and $h(0) > 0$ (resp.\ $h(0) \neq 0$),
then we can define $\Psi = \log h$,
and the columns of $A,B,C$ are interpolated by functions
$f_n(x), g_n(x), h_n(x)$ that are polynomials multiplied by $e^{\psi_0 x}$.
 $\blacksquare$ \bigskip

\bigskip

We can now specialize to the case in which $A$ and $B$ are lower-triangular.
In fact, we can be a bit more general.
Let us say that a matrix $M = (m_{ij})_{i,j \ge 0}$
is {\em lower-triangular in row $i$}\/ if $m_{ij} = 0$ for all $j > i$.
We then have:

\begin{corollary}
   \label{cor.pascal-like}
Let
$A = (a_{ij})_{i,j \ge 0}$,
$B = (b_{ij})_{i,j \ge 0}$,
$C = (c_{ij})_{i,j \ge 0}$
be matrices with entries in a commutative ring $R$
that satisfy \reff{eq.identity.ABC};
and suppose further that $a_{00}$ and $b_{00}$ are invertible in $R$.
If $A$ and $B$ are lower-triangular in row 0,
then there exist $\alpha,\beta \in R$ with $\alpha$ and $\beta$ invertible,
and $h \in R[[u]]$, such that
\begin{equation}
   A_i(u) \;=\; \alpha \, h(u)^i   \:,\quad
   B_i(u) \;=\; \beta \, h(u)^i   \:,\quad
   C_i(u) \;=\; \alpha\beta \, h(u)^i
   \;.
\end{equation}
If, in addition, at least one of $A,B,C$ is lower-triangular in row 1,
then there exist $\alpha,\beta,\kappa,\lambda \in R$,
with $\alpha$ and $\beta$ invertible, such that
\begin{equation}
   a_{ij}  \;=\;  \alpha \kappa^{i-j} \lambda^j \binom{i}{j}  \:,\quad
   b_{ij}  \;=\;  \beta \kappa^{i-j} \lambda^j \binom{i}{j}  \:,\quad
   c_{ij}  \;=\;  \alpha\beta \kappa^{i-j} \lambda^j \binom{i}{j}
   \;.
\end{equation}
\end{corollary}

\par\medskip\noindent{\sc Proof.\ }
If $A$ and $B$ are lower-triangular in row 0,
then $f = a_{00} = \alpha$ and $g = b_{00} = \beta$.
If, in addition, at least one of $A,B,C$ is lower-triangular in row 1,
then $h = \kappa + \lambda u$.
\hbox{\hskip 6pt\vrule width6pt height7pt depth1pt \hskip1pt}\bigskip

When $A=B=C$, this yields:

\begin{corollary}[No-go theorem for lower-triangular Pascal-like matrices]
   \label{cor.pascal-like.2}
Let $L = (L_{ij})_{i,j \ge 0}$ be a lower-triangular matrix
with entries in a commutative ring $R$
that satisfies \reff{eq.identity.L}.
If $L_{00}$ is invertible in $R$, then in fact $L_{00} = 1$,
and there exist $\kappa,\lambda \in R$ such that
\begin{equation}
   L_{ij}  \;=\;  \kappa^{i-j} \lambda^j \binom{i}{j}
   \;.
\end{equation}
\end{corollary}

Corollary~\ref{cor.pascal-like.2} thus gives a negative answer
to the question posed in the introduction:
there are no lower-triangular solutions to \reff{eq.identity.L}
other than trivial rescalings of the Pascal matrix.
But --- and this is the interesting twist ---
Proposition~\ref{prop.pascal-like} shows that there {\em are}\/
interesting examples if we give up the insistence that $L$ be lower-triangular:
we can take $f(u) = g(u) = 1$
and choose an {\em arbitrary}\/ formal power series $h(u)$,
not just $h(u) = \kappa + \lambda u$.
These examples turn out to have interesting applications
to the theory of Hankel-total positivity \cite{Sokal_totalpos};
but that story will have to be told elsewhere \cite{Petreolle-Sokal_nontri}.


\section*{Acknowledgments}

I wish to thank Mathias P\'etr\'eolle and Bao-Xuan Zhu
for helpful conversations,
and the referees for helpful suggestions.

This research was supported in part by
U.K.~Engineering and Physical Sciences Research Council grant EP/N025636/1.







2018-04-25T02:07:49.000
1804
1804.08919
en
https://arxiv.org/abs/1804.08919
We consider two different interpretations of the Chu--Vandermonde identity: as an identity for polynomials, and as an identity for infinite matrices. Each interpretation leads to a class of possible generalizations, and in both cases we obtain a complete characterization of the solutions.
Combinatorics (math.CO); Commutative Algebra (math.AC)
How to generalize (and not to generalize) the Chu--Vandermonde identity
Qwen/Qwen-72B
1. YES
2. YES