\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amscd} \usepackage{graphicx} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}} \newcommand{\stirling}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} \newcommand{\Astirling}[2]{\left[ \! \stirling{#1}{#2} \! \right]} \newcommand{\Stirling}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} \newcommand{\AStirling}[2]{\left\{ \! \Stirling{#1}{#2} \! \right\}} \newcommand{\Eulerian}[2]{\genfrac{<}{>}{0pt}{}{#1}{#2}} \newcommand{\EEulerian}[2]{\left< \! \Eulerian{#1}{#2} \! \right>} \newcommand{\Recur}[2]{\genfrac{|}{|}{0pt}{}{#1}{#2}} \newcommand{\RRecur}[2]{\genfrac{\|}{\|}{0pt}{}{#1}{#2}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Recurrent Combinatorial Sums and \\ \vskip .1in Binomial-Type Theorems } \vskip 1cm \large Michael Z. Spivey\\ Department of Mathematics and Computer Science \\ University of Puget Sound \\ Tacoma, WA 98416-1043\\ USA\\ \href{mailto:mspivey@pugetsound.edu}{\tt mspivey@pugetsound.edu}\\ \end{center} \vskip .2 in \begin{abstract} We prove that several known combinatorial sum identities, including identities featuring the binomial coefficients, both kinds of Stirling numbers, the Lah numbers, both kinds of associated Stirling numbers, and first- and second-order Eulerian numbers, are all special cases of a single identity satisfying a simple one-term recurrence. Moreover, subject to a certain set of restrictions, these special cases are the only identities featuring the aforementioned numbers that also satisfy this one-term recurrence. We then derive formulas for the coefficients involved when converting between multifactorial powers (a generalization of rising and of falling factorial powers) and ordinary powers, as well as some conditions under which numbers satisfying a general two-term combinatorial recurrence can be considered inverses of each other. Next, we derive conditions under which numbers that satisfy a general two-term recurrence also satisfy a binomial-type theorem, and we show that the binomial coefficients and the Stirling numbers of the first kind are the only numbers mentioned earlier that exhibit these conditions. Finally, we give a combinatorial proof of a binomial-type theorem satisfied by the Stirling numbers of the first kind. \end{abstract} \section{Introduction} The following four identities, featuring, respectively, the binomial coefficients $\binom{n}{k}$, the Stirling numbers of the first kind $\stirling{n}{k}$, the Stirling numbers of the second kind $\Stirling{n}{k}$, and the Lah numbers $L(n,k)$, are strikingly similar: \begin{align} (x+1)^n &= \sum_{k=0}^n \binom{n}{k} x^k, \label{binthm} \\ x^{\overline{n}} &= \sum_{k=0}^n \stirling{n}{k} x^k, \label{s1sum}\\ x^n &= \sum_{k=0}^n \Stirling{n}{k} x^{\underline{k}}, \label{s2sum} \\ x^{\overline{n}} &= \sum_{k=0}^n L(n,k) x^{\underline{k}} \label{Lahsum}. \end{align} (The expressions $x^{\underline{n}}$ and $x^{\overline{n}}$ represent, respectively, the {\em falling factorial}, \[x^{\underline{n}} = x(x-1)(x-2) \cdots (x-n+1),\] and the {\em rising factorial}, \[x^{\overline{n}} = x(x+1)(x+2) \cdots (x+n-1).)\] Generalizing, we see that all four identities are special cases of the following equation: \begin{equation} S(n) = \sum_{k=0}^n \Recur{n}{k} g(k), \label{geneq} \end{equation} where \begin{itemize} \item $S(n)$ satisfies a recurrence of the form $S(n+1) = h(n) S(n)$, \item $g(k)$ satisfies a recurrence of the form $g(k+1) = f(k)g(k)$, \item $S(0) = g(0)$, and \item $\Recur{n}{k}$ is a well-known set of numbers that satisfies a two-term recurrence of the following form: \begin{equation} \label{GrKnPaEq} \Recur{n+1}{k} = (\alpha n + \beta k + \gamma) \Recur{n}{k} + (\alpha' n + \beta' (k-1) + \gamma') \Recur{n}{k-1}, \end{equation} valid for $n, k \geq 0$, with $\Recur{0}{k} = [k=0]$ and $\Recur{n}{k} = 0$ when $n < 0$ or $k < 0$. \end{itemize} The array $\Recur{n}{k}$ was first considered by Graham et al.~\cite[Problem 3.94]{GrKnPa94} and has been studied from various standpoints \cite{BaSaVi14, MaSh13, Neu01, Spi11}. For example, Equation~\eqref{binthm}, the binomial theorem, has $S(n) = (x+1)^n$, $h(n) = x+1$, $g(k) = x^k$, $f(k) = x$, $\Recur{n}{k} = \binom{n}{k}$, $\alpha = \beta = \alpha' = \beta' = 0$, and $\gamma = \gamma' = 1$. A summary of these values for Equations~\eqref{binthm}, \eqref{s1sum}, \eqref{s2sum}, and \eqref{Lahsum} is given in Table~\ref{geneqtable}. \begin{table}[ht] \begin{center} \begin{tabular}{lcccccc} Equation & $S(n)$ & $h(n)$ & $g(k)$ & $f(k)$ & $\Recur{n}{k}$ & $(\alpha, \beta, \gamma; \alpha', \beta', \gamma')$ \\ \hline Eq.~\eqref{binthm} & $(x+1)^n$ & $x+1$ & $x^k$ & $x$ & $\binom{n}{k}$ & $(0, 0, 1; 0, 0, 1)$ \\ Eq.~\eqref{s1sum} & $x^{\overline{n}}$ & $x+n$ & $x^k$ & $x$ & $\stirling{n}{k}$ & $(1, 0, 0; 0, 0, 1)$ \\ Eq.~\eqref{s2sum} & $x^n$ & $x$ & $x^{\underline{k}}$ & $x-k$ & $\Stirling{n}{k}$ & $(0, 1, 0; 0, 0, 1)$ \\ Eq.~\eqref{Lahsum} & $x^{\overline{n}}$ & $x+n$ & $x^{\underline{k}}$ & $x-k$ & $L(n,k)$ & $(1, 1, 0; 0, 0, 1)$ \\ \end{tabular} \caption{Equations~\eqref{binthm} through \eqref{Lahsum} as special cases of Equation~\eqref{geneq}.} \label{geneqtable} \end{center} \end{table} All of these similarities motivate the following question: \begin{quote} What general conditions produce an identity of the form of Equation~\eqref{geneq}, \begin{equation*} S(n) = \sum_{k=0}^n \Recur{n}{k} g(k)? \end{equation*} \end{quote} Given a particular set of doubly-indexed numbers $\Recur{n}{k}$ satisfying Equation~\eqref{GrKnPaEq}, our Theorem~\ref{mainthm} (presented in Section~\ref{secmainthm}) gives an answer to this question: It gives conditions on $h(n)$, $f(k)$, and the $\alpha, \beta, \gamma, \alpha', \beta'$, and $\gamma'$ values that guarantee the existence of an identity of the form of Equation~\eqref{geneq}. Moreover, for any particular set of numbers $\Recur{n}{k}$, there is (up to scaling and/or shifting with a choice of parameter) often only one function $h(n)$ and one function $f(k)$ that simultaneously satisfy these conditions. When this is the case, we call the resulting identity the {\em natural recurrent identity} for the $\Recur{n}{k}$ numbers. In Section~\ref{secExamples} we give several examples of the use of Theorem~\ref{mainthm}, including showing that the natural recurrent identities for the binomial coefficients, the two kinds of Stirling numbers, and the Lah numbers are precisely the identities given in Equations~\eqref{binthm} through \eqref{Lahsum}. We also find the natural recurrent identities for the associated Stirling numbers as well as the first- and second-order Eulerian numbers. One of the observations in Section~\ref{secExamples} is that the natural recurrent identities for the binomial coefficients, the two kinds of Stirling numbers, and the Lah numbers all feature a parameter $x$, while those for the associated Stirling numbers and the two orders of Eulerian numbers do not. In Section~\ref{secpower} we derive conditions on the $\alpha, \beta, \gamma, \alpha', \beta'$, and $\gamma'$ values appearing in Equation~\eqref{GrKnPaEq} such that the natural recurrent identity for $\Recur{n}{k}$ does feature such a parameter $x$. Then we consider the cases that arise when converting from multifactorial powers (a generalization of rising and falling factorial powers) to ordinary powers and from ordinary powers to multifactorial powers, deriving formulas for the coefficients used when making these conversions. Converting from one kind of power to another using numbers $\Recur{n}{k}$ and then back using numbers $\RRecur{n}{k}$ leads naturally to a discussion of situations in which $\Recur{n}{k}$ and $\RRecur{n}{k}$ are inverse sets of numbers. We present a theorem giving conditions under which this is the case, including explicit formulas for the inverse pairs $\Recur{n}{k}$ and $\RRecur{n}{k}$. Section~\ref{secbinomial} starts with a more general form of the binomial theorem, $$(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k},$$ and finds conditions on $\alpha, \beta, \gamma, \alpha', \beta'$, and $\gamma'$ under which a binomial-type theorem of the form $S(n,x,y) = \sum_{k=0}^n \Recur{n}{k} x^k y^{n-k}$ exists. We also present formulas for the numbers $\Recur{n}{k}$ under which such identities exist. Finally, in Section~\ref{seccombo} we give a combinatorial proof for the identity $\prod_{i=0}^{n-1} (x+yi) = \sum_{k=0}^n \stirling{n}{k} x^k y^{n-k}$, the binomial-type theorem satisfied by the Stirling numbers of the first kind that appears as a consequence of our results in Section~\ref{secbinomial}. \section{The main theorem: conditions on a recurrent identity} \label{secmainthm} Our main result addressing identities of the form of Equation~\eqref{geneq} is the following. \begin{theorem} \label{mainthm} Suppose $\Recur{n}{k}$ satisfies a two-term recurrence relation of the form of Equation~\eqref{GrKnPaEq}, \[\Recur{n+1}{k} = (\alpha n + \beta k + \gamma) \Recur{n}{k} + (\alpha' n + \beta' (k-1) + \gamma') \Recur{n}{k-1},\] valid for $n, k \geq 0$, with $\Recur{0}{k} = [k=0]$ and $\Recur{n}{k} = 0$ when $n < 0$ or $k < 0$. Suppose \begin{align*} S(n+1) &= S(0) \prod_{i=0}^n h(i), \\ g(k+1) &= g(0) \prod_{i=0}^k f(i), \text{ and}\\ S(0) &= g(0). \end{align*} If, for all $n$ and $k$, $h(n)$ and $f(k)$ satisfy the relationship \begin{equation} h(n) = \alpha n + \beta k + \gamma + (\alpha' n + \beta' k + \gamma')f(k), \label{thmcond} \end{equation} then the identity (Eq.~\ref{geneq}) \[ S(n) = \sum_{k=0}^n \Recur{n}{k} g(k)\] holds. \end{theorem} \begin{proof} In the case $n = 0$, Equation~\eqref{geneq} simplifies to the claim $S(0) = \Recur{0}{0} g(0)$. Since Equation~\eqref{GrKnPaEq} includes the initial condition $\Recur{0}{0} = 1$, Equation~\eqref{geneq} holds in this case. Now assume Equation~\eqref{geneq} holds for all nonnegative integers up through some fixed value of $n$. Next, substituting $n+1$ for $n$ in Equation~\eqref{geneq} and then expanding via the recurrence in Equation~\eqref{GrKnPaEq}, we have \begin{align*} \sum_{k=0}^{n+1} \Recur{n+1}{k} g(k) &= \sum_{k=0}^{n+1} (\alpha n + \beta k + \gamma) \Recur{n}{k} g(k) + \sum_{k=0}^{n+1} (\alpha' n + \beta' (k-1) + \gamma') \Recur{n}{k-1} g(k) \\ &= \sum_{k=0}^{n+1} (\alpha n + \beta k + \gamma) \Recur{n}{k} g(k) + \sum_{k=-1}^n (\alpha' n + \beta' k + \gamma') \Recur{n}{k} g(k+1) \\ &= \sum_{k=0}^n \big( (\alpha n + \beta k + \gamma) g(k) + (\alpha' n + \beta' k + \gamma') g(k+1) \big) \Recur{n}{k}, \end{align*} where we use the fact that the boundary conditions on Equation~\eqref{GrKnPaEq} imply that $\Recur{n}{-1} = \Recur{n}{n+1} = 0$. Continuing, we have \begin{align*} &\sum_{k=0}^n \big( (\alpha n + \beta k + \gamma) g(k) + (\alpha' n + \beta' k + \gamma') g(k+1) \big) \Recur{n}{k} \\ &= \sum_{k=0}^n \big( (\alpha n + \beta k + \gamma) g(k) + (\alpha' n + \beta' k + \gamma') f(k)g(k) \big) \Recur{n}{k} \\ &= \sum_{k=0}^n \Big( \big(\alpha n + \beta k + \gamma + (\alpha' n + \beta' k + \gamma') f(k)\big)g(k) \Big) \Recur{n}{k}. \end{align*} Now, if $h(n)$ and $f(k)$ satisfy Equation~\eqref{thmcond}, this becomes \begin{align*} &\sum_{k=0}^n \Big( \big(\alpha n + \beta k + \gamma + (\alpha' n + \beta' k + \gamma') f(k)\big)g(k) \Big) \Recur{n}{k} = \sum_{k=0}^n h(n) g(k) \Recur{n}{k} \\ & = h(n) \sum_{k=0}^n \Recur{n}{k} g(k) = h(n) S(n) = S(n+1). \end{align*} \end{proof} The requirement that Equation~\eqref{thmcond} must hold for all values of $n$ and $k$ turns out to be quite restrictive in practice. In fact, as illustrated by every example in the next section, for a given $\Recur{n}{k}$ satisfying Equation~\eqref{GrKnPaEq} there is often only one function (up to scaling and shifting) for $h(n)$ and one function for $f(k)$ that simultaneously satisfy Equation~\eqref{thmcond}. If this is the case, we will refer to the identity of the form $S(n) = \sum_{k=0}^n \Recur{n}{k} g(k)$ produced by this $h(n)$ and $f(k)$ as the {\em natural recurrent identity} for the collection of numbers $\Recur{n}{k}$. \section{Examples} \label{secExamples} In this section we illustrate the use of Theorem~\ref{mainthm} by determining the natural recurrent identity for several known doubly-indexed numbers satisfying Equation~\eqref{GrKnPaEq}: the binomial coefficients, both kinds of Stirling numbers, the Lah numbers, both kinds of associated Stirling numbers, and first- and second-order Eulerian numbers. In each of these cases the identity derived is known. The import is thus not that we obtain new identities for these numbers, but rather that all of these known identities are just consequences of Theorem~\ref{mainthm}. \subsection{Binomial coefficients} The binomial coefficients $\binom{n}{k}$ satisfy the recurrence \[ \binom{n+1}{k} = \binom{n}{k} + \binom{n-1}{k-1}.\] In the notation of Equation~\eqref{GrKnPaEq}, the binomial coefficients have $\alpha = \beta = \alpha' = \beta' = 0$, $\gamma = \gamma' = 1$. Theorem~\ref{mainthm} then says that we can produce an identity of the form \[ S(n) = \sum_{k=0}^n \binom{n}{k} g(k)\] by choosing $f(k)$ and $h(n)$ to satisfy \[ h(n) = f(k) + 1.\] Since $k$ appears only on the right side of this equation and $n$ only appears on the left, using this relationship requires $f$ and $h$ to be constant functions of $k$ and $n$. The only such functions have, for $f$, the form $f(k) = x$, where $x$ does not depend on $k$ or $n$ but may otherwise be a parameter. This forces $h(n) = x+1$, yielding the identity \[ (x+1)^n = \sum_{k=0}^n \binom{n}{k} x^k,\] otherwise known as the binomial theorem. Thus the binomial theorem is the natural recurrent identity for the binomial coefficients. (We could have chosen a shifted version of $f$ such as $f(k) = x+c$ or a scaled version of $f$ such as $f(k) = cx$, for some constant $c$, but these just yield slightly different forms of the binomial theorem. As this will be true for other examples that allow for a parameter $x$, we will not mention these possibilities specifically when we discuss those cases.) \subsection{Stirling numbers of the first kind} The Stirling numbers of the first kind satisfy the recurrence \[ \stirling{n+1}{k} = n \stirling{n}{k} + \stirling{n}{k-1}.\] In the notation of Equation~\eqref{GrKnPaEq}, the Stirling numbers of the first kind have $\beta = \gamma = \alpha' = \beta' = 0$, $\alpha = \gamma' = 1$. Equation~\eqref{thmcond} in Theorem~\ref{mainthm} says that we need functions $f(k)$ and $h(n)$ satisfying \[ h(n) = f(k) + n.\] This means $f(k)$ cannot depend on $k$ and must thus be some parameter $x$. Thus $h(n) = x + n$. The identity of the form of Equation~\eqref{geneq} that this gives us is \begin{align*} \sum_{k=0}^n \stirling{n}{k} x^k = x(x+1)(x+2) \cdots (x+n-1) = x^{\overline{n}}, \end{align*} which is Equation~\eqref{s1sum}. Thus the natural recurrent identity for the Stirling numbers of the first kind is the equation that allows us to represent rising factorial powers in terms of ordinary powers. The signed Stirling numbers of the first kind $s(n,k)$ satisfy the recurrence \[ s(n+1,k) = - n s(n,k) + s(n,k-1)\] and the relationship $s(n,k) = (-1)^{n-k} \stirling{n}{k}$. Applying the condition in Equation~\eqref{thmcond}, we need $f(k)$ and $h(n)$ satisfying \[ h(n) = f(k) - n.\] Using an argument similar to that for the (unsigned) Stirling numbers of the first kind, we see that this condition is satisfied only by $f(k) = x$ and $h(n) = x-n$. By Theorem~\ref{mainthm}, we thus have the identity \begin{align*} &\sum_{k=0}^n s(n,k) x^k = x(x-1)(x-2) \cdots (x-n+1) = x^{\underline{n}} \\ \implies & \sum_{k=0}^n \stirling{n}{k} (-1)^{n-k} x^k = x^{\underline{n}}. \end{align*} Thus the natural recurrent identity for the signed Stirling numbers of the first kind is the equation that allows us to represent falling factorial powers as ordinary powers. \subsection{Stirling numbers of the second kind} The Stirling numbers of the second kind satisfy the recurrence \[ \Stirling{n+1}{k} = k \Stirling{n}{k} + \Stirling{n}{k-1}.\] In the notation of Equation~\eqref{GrKnPaEq}, this yields $\alpha = \alpha' = \beta' = \gamma = 0$, $\beta = \gamma' = 1$. In terms of Theorem~\ref{mainthm}, we have the condition \[ h(n) = f(k) + k.\] With this restriction, $h(n)$ cannot depend on $n$. Thus $h(n) = x$ and $f(k) = x - k$. Applying Theorem~\ref{mainthm} produces the identity \[ x^n = \sum_{k=0}^n \Stirling{n}{k} x(x-1)(x-2) \cdots (x-k+1) = \sum_{k=0}^n \Stirling{n}{k} x^{\underline{k}},\] which is Equation~\eqref{s2sum}. So the natural recurrent identity for the Stirling numbers of the second kind is the formula for converting ordinary powers to falling factorial powers. \subsection{Lah numbers} The Lah numbers satisfy the recurrence \[ L(n+1,k) = (n+k)L(n,k) + L(n,k-1).\] In terms of Equation~\eqref{GrKnPaEq}, we have $\alpha = \beta = \gamma' = 1$, $\gamma = \alpha' = \beta' = 0$. Using the condition in Equation~\eqref{thmcond}, we are looking for $f(k)$ and $h(n)$ satisfying \[ h(n) = f(k) + n + k.\] The left side of this equation depends only on $n$. In order for this to be the case for the right side, we must have a function $f$ of the form $f(k) = x-k$. This forces $h(n) = x+n$. We have seen both of these functions in previous examples, and so Theorem~\ref{mainthm} tells us that \begin{equation*} x^{\overline{n}} = \sum_{k=0}^n L(n,k) x^{\underline{k}}. \end{equation*} This is Equation~\eqref{Lahsum}. Thus the natural recurrent identity for the Lah numbers is the formula for converting from rising factorial powers to falling factorial powers. The Lah numbers can also be used to convert from falling factorial powers to rising factorial powers. This is really just a minor variation of Equation~\eqref{Lahsum}, as substituting $-x$ for $x$ in Equation~\eqref{Lahsum} and performing a few basic manipulations readily shows. \subsection{Associated Stirling numbers} The associated Stirling numbers of the first and second kinds, $\Astirling{n}{k}$ and $\AStirling{n}{k}$, respectively, satisfy the recurrences \begin{align*} \Astirling{n+1+k}{k} &= (n+k)\Astirling{n+k}{k} + (n+k) \Astirling{n+k-1}{k-1}, \text{ and} \\[.1in] \AStirling{n+1+k}{k} &= k\AStirling{n+k}{k} + (n+k) \AStirling{n+k-1}{k-1}, \end{align*} with initial conditions agreeing with those in Equation~\eqref{GrKnPaEq}. As such, the $\Astirling{n+k}{k}$ numbers have $\alpha = \beta = \alpha' = \beta' = \gamma' = 1$ and $\gamma = 0$. The $\AStirling{n+k}{k}$ numbers have $\beta = \alpha' = \beta' = \gamma' = 1$ and $\alpha = \gamma = 0$. These are the first recurrences we have seen such that $\alpha'$ or $\beta'$ is nonzero, which means these are the first examples we shall see in which the $f(k)$ term in Equation~\eqref{thmcond} is multiplied by something other than a constant. For the $\Astirling{n+k}{k}$ numbers, Equation~\eqref{thmcond} yields the condition \[ h(n) = n + k + nf(k) + kf(k) + f(k).\] Finding $f$ and $h$ so that $f$ is a function only of $k$ and $h$ is a function only of $n$ will require more work than we have seen thus far. The fact that we have $n f(k)$ on the right but no additional product terms involving $n$ and $k$ in the equation means that $f(k)$ must be constant (i.e., does not depend on $k$). A constant $f(k)$ implies that the two terms on the right depending on $k$, $k$ and $kf(k)$, must sum to a constant. But a constant value for $k(1+f(k))$ in which $f(k)$ does not depend on $k$ leaves us with only one option: $f(k) = -1$. The equation now reduces to \[ h(n) = n - n -1 = -1,\] which yields our first example that does not feature a parameter $x$. The natural recurrent identity for the associated Stirling numbers of the first kind is thus \begin{equation} \label{As1} (-1)^n = \sum_{k=0}^n \Astirling{n+k}{k} (-1)^k, \end{equation} which appears in both Comtet~\cite[p.\ 256]{Com74} and Spivey~\cite{Spi11}. A similar situation occurs with the associated Stirling numbers of the second kind $\AStirling{n}{k}$. Equation~\eqref{thmcond} yields \[ h(n) = k + nf(k) + kf(k) + f(k).\] The same logic as before implies $f(k) = -1$ and $h(n) = -(n+1)$. In the form of Equation~\eqref{geneq}, this yields \[S(n) = \prod_{i=0}^{n-1} \big((-1)(i+1)\big) = (-1)^n n!,\] and so by Theorem~\ref{mainthm} we have the identity \begin{equation} \label{AS2} (-1)^n n! = \sum_{k=0}^n \AStirling{n+k}{k} (-1)^k \end{equation} as the natural recurrent identity for the associated Stirling numbers of the second kind. (Equation~\eqref{AS2} appears in Spivey~\cite{Spi11}.) \subsection{Eulerian numbers} Our last set of examples illustrating Theorem~\ref{mainthm} concerns the Eulerian numbers. Each collection of first-order and second-order Eulerian numbers, $\Eulerian{n}{k}$ and $\EEulerian{n}{k}$, respectively, satisfies a recurrence and initial conditions agreeing with those in Equation~\eqref{GrKnPaEq}. These are \begin{align*} \Eulerian{n+1}{k} &= (k+1) \Eulerian{n}{k} + (n-k+1)\Eulerian{n}{k-1}, \text{ and} \\[.1in] \EEulerian{n+1}{k} &= (k+1) \EEulerian{n}{k} + (2n-k+1)\EEulerian{n}{k-1}. \end{align*} In the notation of Equation~\eqref{GrKnPaEq}, the first-order Eulerian numbers have $\alpha = \gamma' = 0$, $\beta = \gamma = \alpha' = 1$, $\beta' = -1$. Thus Equation~\eqref{thmcond} yields the condition \[ h(n) = k + 1 + nf(k) - kf(k).\] As with the associated Stirling numbers, the presence of the factor $nf(k)$ on the right with no product terms involving $n$ and $k$ elsewhere in the equation means that $f(k)$ must be constant. If $f(k)$ is constant, then the left side's lack of dependence on $k$ means that the $k$ and $-kf(k)$ terms must add to zero. This forces $f(k) = 1$. We now have \[ h(n) = 1 + n.\] Theorem~\ref{mainthm} then gives us the natural recurrent identity for the Eulerian numbers to be \[ n! = \sum_{k=0}^n \Eulerian{n}{k},\] which is their (known) row sum. For the second-order Eulerian numbers, we have $\alpha = \gamma' = 0$, $\beta = \gamma = 1$, $\alpha' = 2$, $\beta' = -1$. Thus we have \[ h(n) = k + 1 + 2n f(k) - k f(k).\] As before, $f(k)$ must be constant because of the presence of $2n f(k)$ on the right side. The remaining $k$ terms on the right must sum to zero, which implies $f(k) = 1$. This leaves \[ h(n) = 2n+1.\] Then the natural recurrent identity for the Eulerian numbers of the second kind is, by Theorem~\ref{mainthm}, their (known) row sum \[ \sum_{k=0}^n \EEulerian{n}{k} = \prod_{i=0}^{n-1} (2i+1) = 1(3)(5) \cdots (2n-1) = (2n-1)!!.\] \section{Power functions and multifactorials} \label{secpower} In the examples in the previous section, the binomial coefficients, both kinds of Stirling numbers, and the Lah numbers all include a parameter $x$ as part of their natural recurrent identities produced by Theorem~\ref{mainthm}. However, the natural recurrent identities for the two kinds of associated Stirling numbers and the two orders of Eulerian numbers do not feature such a parameter $x$. The reason for this difference depends on the parameters $\alpha, \beta, \gamma, \alpha', \beta'$, and $\gamma'$ in the two-term recurrences of the form of Equation~\eqref{GrKnPaEq} satisfied by the various sets of numbers, as we see in Corollary~\ref{xcor}. \begin{corollary} \label{xcor} Suppose $\Recur{n}{k}$ satisfies a two-term recurrence relation of the form of Equation~\eqref{GrKnPaEq}, \[\Recur{n+1}{k} = (\alpha n + \beta k + \gamma) \Recur{n}{k} + (\alpha' n + \beta' (k-1) + \gamma') \Recur{n}{k-1},\] valid for $n, k \geq 0$, with $\Recur{0}{k} = [k=0]$ and $\Recur{n}{k} = 0$ when $n < 0$ or $k < 0$. Suppose $\Recur{n}{k}$ satisfies a natural recurrent identity of the form \[ S(n) = \sum_{k=0}^n \Recur{n}{k} g(k),\] where \begin{align*} S(n+1) &= S(0) \prod_{i=0}^n h(i), \\ g(k+1) &= g(0) \prod_{i=0}^k f(i), \\ S(0) &= g(0), \\ h(n) &= \alpha n + \beta k + \gamma + (\alpha' n + \beta' k + \gamma')f(k) \:\:\:(i.e., Eq.\text{ }\eqref{thmcond}), \end{align*} and $h$ and $f$ both contain a parameter $x$. \bigskip \noindent{\it Case 1}. If $\alpha' \neq 0$, then $\beta = \beta' = 0$, and the natural recurrent identity for $\Recur{n}{k}$ is \begin{equation} \label{x1eq} \prod_{i=0}^{n-1} \big((\alpha + \alpha' x)i + \gamma + \gamma' x \big) = \sum_{k=0}^n \Recur{n}{k} x^k. \end{equation} \noindent{\it Case 2}. If $\alpha' = 0$, then $\gamma' \neq - \beta' i$ for any $0 \leq i \leq n-1$, and the natural recurrent identity for $\Recur{n}{k}$ is \begin{equation} \label{x2eq} \prod_{i=0}^{n-1} \left(\alpha i + \gamma + \gamma' x \right) = \sum_{k=0}^n \Recur{n}{k} \prod_{i=0}^{k-1} \left(\frac{-\beta i+\gamma' x}{\beta' i + \gamma'}\right). \end{equation} \end{corollary} \begin{proof} First, slightly rewrite the relationship between $h(n)$ and $f(k)$ (Equation~\eqref{thmcond}) as \[ h(n) = \alpha n + \beta k + \gamma + \alpha' n f(k) + \beta' k f(k) + \gamma'f(k).\] \noindent{\it Case 1:} $\alpha' \neq 0$. Since the term $\alpha' n f(k)$ appears only on the right side of this equation, we see that $f(k)$ cannot depend on $k$, as there is no other term in the equation that features the product of $n$ and a nonconstant function of $k$. Since $f$ must depend on the parameter $x$, we have $f(k) = x$. (Again, any shifting or scaling of this would simply result in the same identity in a slightly different form.) The relationship between $h(n)$ and $f(k)$ now reduces to \[ h(n) = \alpha n + \beta k + \gamma + \alpha' n x + \beta' k x + \gamma' x.\] Since there are no other terms involving $k$, $\beta k + \beta' k x = (\beta + \beta' x)k$ must be constant. But since $x$ is a parameter and $k$ is a variable, the only way this is possible is to have $\beta = \beta'=0$. Thus $h(n) = (\alpha + \alpha' x)n + \gamma + \gamma' x$. By Theorem~\ref{mainthm}, then, the natural recurrent identity for $\Recur{n}{k}$ is \[ \prod_{i=0}^{n-1} \big((\alpha + \alpha' x)i + \gamma + \gamma' x\big) = \sum_{k=0}^n \Recur{n}{k} x^k.\] \bigskip \noindent{\it Case 2:} $\alpha' = 0$. Here, we have \[ h(n) = \alpha n + \beta k + \gamma + \beta' k f(k) + \gamma'f(k).\] The terms involving $k$ must sum to a constant parameter. Normally we would choose $x$ as this parameter, but selecting this constant parameter to be $\gamma' x$ instead will give us a result that parallels Case 1 more obviously. (Remember that shifting or scaling by a constant results in the same identity in a slightly different form.) This means that $\gamma'$ cannot equal $- \beta' i$ for any $0 \leq i \leq n-1$ (in particular, $\beta'$ and $\gamma'$ cannot both be zero), and so we have \[ f(k) = \frac{-\beta k + \gamma' x}{\beta' k + \gamma'}.\] Thus $h(n) = \alpha n + \gamma + \gamma' x$, and the natural recurrent identity for $\Recur{n}{k}$ is, by Theorem~\ref{mainthm}, \[ \prod_{i=0}^{n-1} \left(\gamma + \gamma' x + \alpha i \right) = \sum_{k=0}^n \Recur{n}{k} \prod_{i=0}^{k-1} \left(\frac{-\beta i + \gamma' x}{\beta' i + \gamma'}\right).\] \end{proof} With Corollary~\ref{xcor}, we can now see why the associated Stirling numbers and the first- and second-order Eulerian numbers do not feature a parameter $x$ in their natural recurrent identities: All four sets of numbers have $\alpha' \neq 0$ (and so would fall in Case 1), yet all four also have nonzero values for $\beta$ and $\beta'$. \subsection{Converting from multifactorial powers to ordinary powers} Corollary~\ref{xcor} also allows us to find a pair of formulas for the coefficients obtained when converting from multifactorial powers to ordinary powers. Define a {\em multifactorial power} to be one of the form \begin{align*} &M(\alpha,\alpha',\gamma,\gamma';x,n) = \prod_{k=0}^{n-1} \Big((\alpha + \alpha'x)k + \gamma + \gamma'x\Big) \\ &= \big(\gamma + \gamma'x \big)\big(\alpha + \alpha' x + \gamma +\gamma'x \big) \cdots \big((\alpha + \alpha'x)(n-1) + \gamma + \gamma'x\big). \end{align*} We have, for example, $x^{\overline{n}} = M(1,0,0,1;x,n)$ and $x^{\underline{n}} = M(-1,0,0,1;x,n)$. Another example is the {\em double factorial falling power} (see, for example, Gould and Quaintance~\cite{GoQu12}), defined by $((x))^{\underline{n}} = x(x-2)(x-4) \cdots (x-2n+2)$. We have $((x))^{\underline{n}} = M(-2,0,0,1;x,n)$. The formulas for the coefficients needed when converting from multifactorial powers to ordinary powers are given by Corollary~\ref{multicor}. \begin{corollary} \label{multicor} The coefficients $\Recur{n}{k}$ in the formula \[ \prod_{k=0}^{n-1} \Big((\alpha + \alpha'x)k + \gamma + \gamma'x \Big) = \sum_{k=0}^n \Recur{n}{k} x^k,\] for converting from the multifactorial power $M(\alpha,\alpha',\gamma,\gamma';x,n)$ to ordinary powers in $x$, are given by the following $($where $0^0$ is taken to be $1)$. \bigskip \noindent{\it Case 1:} If $\alpha' \neq 0$, then \begin{equation} \label{case1formula} \Recur{n}{k} = \sum_{i=0}^n \sum_{j=0}^n \stirling{n}{i} \binom{i}{n-j} \binom{j}{k} \alpha^{j-k} (\gamma \alpha'- \alpha \gamma')^{n-j} (\alpha')^{k-i} (\gamma')^{i+j-n}. \end{equation} \noindent{\it Case 2:} If $\alpha' = 0$, then \begin{equation} \label{case2formula} \Recur{n}{k} = (\gamma')^k \sum_{i=0}^n \stirling{n}{i} \binom{i}{k} \alpha^{n-i} \gamma^{i-k}. \end{equation} \end{corollary} \begin{proof} For both cases, Corollary~\ref{xcor} tells us that the formula for the conversion from multifactorial powers to ordinary powers is the natural recurrent identity for some collection of doubly-indexed numbers $\Recur{n}{k}$. Moreover, Corollary~\ref{xcor} gives a two-term recurrence satisfied by $\Recur{n}{k}$. For Case 1, $\alpha' \neq 0$ and Corollary~\ref{xcor} imply $\beta = \beta' = 0$, and so the recurrence is \[\Recur{n+1}{k} = (\alpha n + \gamma) \Recur{n}{k} + (\alpha' n + \gamma') \Recur{n}{k-1},\] valid for $n, k \geq 0$, with $\Recur{0}{k} = [k=0]$ and $\Recur{n}{k} = 0$ when $n < 0$ or $k < 0$. Theorem 9 in Spivey~\cite{Spi11} tells us that the solution is given by Equation~\eqref{case1formula}. For Case 2, $\alpha' = 0$ and Corollary~\ref{xcor} imply that, in order for the right side of Equation~\eqref{x2eq} to be of the form \[ \sum_{k=0}^n \Recur{n}{k} x^k,\] we must have $\beta = \beta' = 0$ as well. Thus the recurrence satisfied by $\Recur{n}{k}$ is \[\Recur{n+1}{k} = (\alpha n + \gamma) \Recur{n}{k} +\gamma' \Recur{n}{k-1},\] valid for $n, k \geq 0$, with $\Recur{0}{k} = [k=0]$ and $\Recur{n}{k} = 0$ when $n < 0$ or $k < 0$. Theorem 18 in Neuwirth~\cite{Neu01} gives the solution to be the expression in Equation~\eqref{case2formula}. (Neuwirth uses quite different notation than we do here, though. For a reformulation of Neuwirth's result using our notation, see Theorem 6 in Spivey~\cite{Spi11}.) \end{proof} As an example of the use of Corollary~\ref{multicor}, let's find the formula for converting from double factorial falling powers to ordinary powers. The parameters for the double factorial falling powers are $\alpha' = \gamma = 0, \gamma' = 1$, and $\alpha = -2$. This is Case 2 of Corollary~\ref{multicor}, and so we have \[ ((x))^{\underline{n}} = \sum_{k=0}^n \Recur{n}{k} x^k,\] where \begin{align*} \Recur{n}{k} = (\gamma')^k \sum_{i=0}^n \stirling{n}{i} \binom{i}{k} \alpha^{n-i} \gamma^{i-k}. \end{align*} However, we can simplify this expression. Since $\gamma = 0$, the factor $\gamma^{i-k}$ is nonzero only when $i=k$. Thus we get \begin{align*} \Recur{n}{k} = \stirling{n}{k} (-2)^{n-k}, \end{align*} This means that our formula is \[ ((x))^{\underline{n}} = \sum_{k=0}^n \stirling{n}{k} (-2)^{n-k} x^k,\] which appears in Gould and Quaintance~\cite{GoQu12}. \subsection{Converting from ordinary powers to multifactorial powers} Corollary~\ref{xcor} also allows us to find the coefficients when converting from ordinary powers to a restricted set of multifactorial powers, as we see in Corollary~\ref{ordcor}. \begin{corollary} \label{ordcor} The coefficients $\Recur{n}{k}$ in the formula \[ x^n = \sum_{k=0}^n \Recur{n}{k} \prod_{i=0}^{k-1} \left(a + bx + ci\right),\] for converting from ordinary powers to multifactorial powers, are given by \[ \Recur{n}{k} = b^{-n}(-1)^{n-k} \sum_{i=0}^n \binom{n}{i} \Stirling{i}{k} a^{n-i} c^{i-k}.\] \end{corollary} \begin{proof} Of the two cases in Corollary~\ref{xcor}, only Case 2 allows a multifactorial expression on the right side. Thus we shall assume $\alpha' = 0$ and $\gamma' \neq 0$. Replace $x$ with $(x-\gamma)/\gamma'$ in Equation~\eqref{x2eq} (remember that shifting and scaling do not fundamentally change the identity) to obtain \begin{equation} \label{alteq} \prod_{i=0}^{n-1} \left(x + \alpha i \right) = \sum_{k=0}^n \Recur{n}{k} \prod_{i=0}^{k-1} \left(\frac{x -\beta i - \gamma}{\beta' i + \gamma'}\right). \end{equation} For the left side to equal $x^n$ and the product on the right to feature a multifactorial power, we must have $\alpha = \beta' = 0$. Thus our equation simplifies to \begin{equation} \label{ordtomulteq} x^n = \sum_{k=0}^n \Recur{n}{k} \prod_{i=0}^{k-1} \left(\frac{x -\beta i - \gamma}{\gamma'}\right). \end{equation} With $\alpha = \alpha' = \beta' = 0$, Theorem 18 of Neuwirth~\cite{Neu01} gives $\Recur{n}{k}$ to be \[ \Recur{n}{k} = (\gamma')^k \sum_{i=0}^n \binom{n}{i} \Stirling{i}{k} \beta^{i-k} \gamma^{n-i}.\] However, the right side of Equation~\eqref{ordtomulteq} does not express multifactorial powers in standard form. To correct this, let $\gamma' = 1/b$, $\gamma = -a/b$, and $\beta = -c/b$. Then Equation~\eqref{ordtomulteq} becomes \[x^n = \sum_{k=0}^n \Recur{n}{k} \prod_{i=0}^{k-1} (a + bx + ci),\] and we have \begin{align*} \Recur{n}{k} &= b^{-k} \sum_{i=0}^n \binom{n}{i} \Stirling{i}{k} \left(\frac{-c}{b}\right)^{i-k} \left(\frac{-a}{b}\right)^{n-i} \\ &= b^{-n} (-1)^{n-k} \sum_{i=0}^n \binom{n}{i} \Stirling{i}{k} a^{n-i} c^{i-k}. \end{align*} \end{proof} As an example, let's use Corollary~\ref{ordcor} to find the formula for converting ordinary powers to double factorial falling powers. The latter have, in the notation of Corollary~\ref{ordcor}, $a = 0$, $b = 1$, and $c = -2$. Applying Corollary~\ref{ordcor}, then, the coefficients $\Recur{n}{k}$ in the formula \[ x^n = \sum_{k=0}^n \Recur{n}{k} \prod_{i=0}^{k-1} (x-2i)\] are given by \[ \Recur{n}{k} = (-1)^{n-k} \sum_{i=0}^n \binom{n}{i} \Stirling{i}{k} 0^{n-i} (-2)^{i-k} = \Stirling{n}{k} 2^{n-k},\] which appears in Gould and Quaintance~\cite{GoQu12}. \subsection{Inverse relations} Define two sets of doubly-indexed numbers $\Recur{n}{k}$ and $\RRecur{n}{k}$ to be {\em inverses} of each other if they satisfy the following relationship for sequences $(a_k)$ and $(b_k)$: \begin{equation*} \label{inveq} a_n = \sum_{k=0}^n \Recur{n}{k} b_k \iff b_n = \sum_{k=0}^n \RRecur{n}{k} a_k. \end{equation*} Some examples of inverse pairs include (1) $\Recur{n}{k} = \RRecur{n}{k} = \binom{n}{k}(-1)^k$, (2) $\Recur{n}{k} = \stirling{n}{k}(-1)^k$ and $\RRecur{n}{k} = \Stirling{n}{k}(-1)^k$, and (3) $\Recur{n}{k} = \RRecur{n}{k} = L(n,k)(-1)^k$. (Spivey~\cite[Thms 1, 26, 29]{SpiAPBI19} gives these explicitly; Riordan~\cite[pages 43, 48, 90]{Rio68} gives slight variations.) Corollaries~\ref{xcor}, \ref{multicor}, and \ref{ordcor} allow us to find a large collection of pairs of inverse numbers. \begin{corollary} \label{invcor} Suppose that $\Recur{n}{k}$ satisfies \[\Recur{n+1}{k} = (\alpha n + \gamma) \Recur{n}{k} + \gamma' \Recur{n}{k-1},\] valid for $n, k \geq 0$, with $\Recur{0}{k} = [k=0]$ and $\Recur{n}{k} = 0$ when $n < 0$ or $k < 0$. Suppose also that $\RRecur{n}{k}$ satisfies \[\RRecur{n+1}{k} = \left( \frac{-\alpha}{\gamma'} k - \frac{\gamma}{\gamma'}\right) \RRecur{n}{k} + \frac{1}{\gamma'} \RRecur{n}{k-1},\] valid for $n, k \geq 0$, with $\RRecur{0}{k} = [k=0]$ and $\RRecur{n}{k} = 0$ when $n < 0$ or $k < 0$. Then $\Recur{n}{k}$ and $\RRecur{n}{k}$ satisfy \begin{align*} \Recur{n}{k} &= (\gamma')^k \sum_{j=0}^n \stirling{n}{j} \binom{j}{k} \alpha^{n-j} \gamma^{j-k}, \text{ and} \\ \RRecur{n}{k} &= (\gamma')^{-n} (-1)^{n-k} \sum_{j=0}^n \binom{n}{j} \Stirling{j}{k} \alpha^{j-k} \gamma^{n-j}. \end{align*} In addition, $\Recur{n}{k}$ and $\RRecur{n}{k}$ are inverses; i.e., for sequences $(a_k)$ and $(b_k)$, \[a_n = \sum_{k=0}^n \Recur{n}{k} b_k \iff b_n = \sum_{k=0}^n \RRecur{n}{k} a_k.\] \end{corollary} \begin{proof} By Corollary~\ref{xcor}, the $\Recur{n}{k}$ numbers are the coefficients when converting from multifactorial powers of the form $\prod_{k=0}^{n-1} (\alpha k + \gamma + \gamma' x )$ to ordinary powers via \[ \prod_{k=0}^{n-1} (\alpha k + \gamma + \gamma' x) = \sum_{k=0}^n \Recur{n}{k} x^k.\] Similarly, the $\RRecur{n}{k}$ numbers are, via Equation~\eqref{ordtomulteq}, the coefficients when converting from ordinary powers to multifactorial powers of the form $\prod_{k=0}^{n-1} (\alpha k + \gamma + \gamma' x)$ via \[ x^n = \sum_{k=0}^n \RRecur{n}{k} \prod_{i=0}^{k-1} (\alpha i + \gamma + \gamma' x).\] The formulas for $\Recur{n}{k}$ and $\RRecur{n}{k}$ follow from Corollaries~\ref{multicor} and \ref{ordcor}. Next, we prove that $\Recur{n}{k}$ and $\RRecur{n}{k}$ are inverses. \bigskip \noindent ($\Longrightarrow$): We have \begin{align*} x^n &= \sum_{k=0}^n \RRecur{n}{k} \prod_{j=0}^{k-1} (\alpha j + \gamma + \gamma'x) = \sum_{k=0}^n \RRecur{n}{k} \sum_{j=0}^k \Recur{k}{j} x^j = \sum_{j=0}^n x^j \sum_{k=j}^n \RRecur{n}{k} \, \Recur{k}{j}. \end{align*} Now, since both sides of this equation are polynomials in $x$, their coefficients must be equal. Thus \[ \sum_{k=j}^n \RRecur{n}{k} \, \Recur{k}{j} = [j=n].\] Therefore, since $a_n = \sum_{k=0}^n \Recur{n}{k} b_k$, \begin{align*} \sum_{k=0}^n \RRecur{n}{k} a_k &= \sum_{k=0}^n \RRecur{n}{k} \sum_{j=0}^k \Recur{k}{j} b_j = \sum_{j=0}^n b_j \sum_{k=j}^n \RRecur{n}{k} \Recur{k}{j} = \sum_{j=0}^n b_j [j=n] = b_n. \end{align*} \noindent $(\Longleftarrow)$: This direction is similar. The argument requires starting with $\prod_{k=0}^{n-1} (\gamma + \gamma' x + \alpha k)$ instead of $x^n$ on the left side to derive the identity \[ \sum_{k=j}^n \Recur{n}{k} \, \RRecur{k}{j} = [j=n],\] which can then be used to prove that $a_n = \sum_{k=0}^n \Recur{n}{k} b_k$. \end{proof} For example, substituting $\alpha = 0$, $\gamma = 1$, and $\gamma' = -1$ into Corollary~\ref{invcor} produces $\Recur{n}{k} = \RRecur{n}{k} = \binom{n}{k} (-1)^k$. Similarly, substituting $\alpha = 1$, $\gamma = 0$, and $\gamma' = -1$ into Corollary~\ref{invcor} produces $\Recur{n}{k} = \stirling{n}{k} (-1)^k$ and $\RRecur{n}{k} = \Stirling{n}{k} (-1)^k$. (The fact that $\binom{n}{k}(-1)^k$, $\stirling{n}{k}(-1)^k$, and $\Stirling{n}{k}(-1)^k$ satisfy the recurrence relations obtained by the claimed substitutions follows from Corollary 2 in Spivey~\cite{Spi11}.) However, the self-inverse property of the $L(n,k)(-1)^k$ collection of numbers does not follow from Corollary~\ref{invcor}, as the Lah numbers convert from multifactorial powers to multifactorial powers rather than multifactorial to ordinary powers or vice versa. (The binomial coefficients convert from ordinary powers to a shifted set of ordinary powers, but those are still covered by Corollaries~\ref{multicor} and \ref{ordcor}.) However, we can prove that the $L(n,k)(-1)^k$ numbers are self-inverse by returning to Corollary~\ref{xcor}. We'll give an outline of the argument, as it is quite similar to the proof of Corollary~\ref{invcor}. First, the $L(n,k)(-1)^k$ numbers satisfy (via the known recurrence for $L(n,k)$ and Corollary 2 in Spivey~\cite{Spi11}) a recurrence of the form of Equation~\eqref{GrKnPaEq}, with $\alpha = \beta = 1$ and $\gamma' = -1$. Substituting into Case 2 of Corollary~\ref{xcor}, we see that the $L(n,k)(-1)^k$ numbers are the coefficients when converting from powers of the form $x^{\underline{n}}(-1)^n$ to rising factorial powers. Similarly, by substituting into Equation~\eqref{alteq} in the proof of Corollary~\ref{ordcor}, we see that the $L(n,k)(-1)^k$ numbers are also the coefficients when converting from rising factorial powers to powers of the form $x^{\underline{n}}(-1)^n$. Now that we know the $L(n,k)(-1)^k$ numbers convert from one kind of powers to another kind of powers and back, an argument very similar to that in the proof of Corollary~\ref{invcor} proves that they must be self-inverse. Finally, this argument indicates how one might use Corollary~\ref{xcor} to find inverse pairs of numbers that are used to convert between different multifactorial powers. \section{Binomial-type theorems} \label{secbinomial} The general version of the binomial theorem for positive integers $n$ is \[ (x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}.\] Given our discussion so far, the existence of the binomial theorem raises a natural question: What other doubly-indexed sets of numbers satisfying recurrences of the form of Equation~\eqref{GrKnPaEq} also satisfy a binomial-type theorem? In this section we address this question. \begin{theorem} \label{generalrowsum} Suppose $\Recur{n}{k}$ satisfies a two-term recurrence relation of the form of Equation~\eqref{GrKnPaEq}, \[\Recur{n+1}{k} = (\alpha n + \beta k + \gamma) \Recur{n}{k} + (\alpha' n + \beta' (k-1) + \gamma') \Recur{n}{k-1},\] valid for $n, k \geq 0$, with $\Recur{0}{k} = [k=0]$ and $\Recur{n}{k} = 0$ when $n < 0$ or $k < 0$. Then, if $x$ and $y$ are such that $\beta y + \beta' x = 0$, then \[ \prod_{k=0}^{n-1} \big((\alpha y + \alpha' x)k + \gamma y + \gamma' x \big) = \sum_{k=0}^n \Recur{n}{k}x^k y^{n-k}.\] \end{theorem} \begin{proof} Let $B(n) = \sum_{k=0}^n \Recur{n}{k} x^k y^{n-k}$. Substituting $n+1$ for $n$ in this equation and then expanding via the recurrence, we have \begin{align*} B(n+1) &= \sum_{k=0}^{n+1} \Recur{n+1}{k} x^k y^{n+1-k} \\ &= \sum_{k=0}^{n+1} (\alpha n + \beta k + \gamma) \Recur{n}{k} x^k y^{n+1-k} + \sum_{k=0}^{n+1} (\alpha' n + \beta' (k-1) + \gamma') \Recur{n}{k-1} x^k y^{n+1-k} \\ &= \sum_{k=0}^{n+1} (\alpha n + \beta k + \gamma) \Recur{n}{k} x^k y^{n+1-k} + \sum_{k=-1}^n (\alpha' n + \beta' k + \gamma') \Recur{n}{k} x^{k+1} y^{n-k} \\ &= \sum_{k=0}^n \big( (\alpha n + \beta k + \gamma) y + (\alpha' n + \beta' k + \gamma')x \big) \Recur{n}{k} x^k y^{n-k} \\ &= \sum_{k=0}^n \big( (\alpha y + \alpha ' x) n + (\beta y + \beta' x) k + \gamma y + \gamma' x \big) \Recur{n}{k} x^k y^{n-k}, \end{align*} where we use the fact that the boundary conditions imply $\Recur{n}{-1} = \Recur{n}{n+1} = 0$. If $\beta y + \beta' x = 0$, then we have \begin{align*} B(n+1) &= \big( (\alpha y + \alpha ' x) n + \gamma y + \gamma' x \big)\sum_{k=0}^n \Recur{n}{k} x^k y^{n-k} \\ &= \big( (\alpha y + \alpha ' x) n + \gamma y + \gamma' x \big) B(n). \end{align*} Thus, since $B(0) = \sum_{k=0}^0 \Recur{0}{k} x^0 y^{0-k} = 1$, we have \[ B(n) = \prod_{k=0}^{n-1} \big( (\alpha y + \alpha ' x) k + \gamma y + \gamma' x \big),\] proving the theorem. \end{proof} Theorem~\ref{generalrowsum} gives binomial-type theorems in terms of generic parameters $x$ and $y$ only in the case where $\beta = \beta' = 0$. The binomial coefficients and the Stirling numbers of the first kind fall in this case. The former, of course, yields the usual binomial theorem, while the latter gives the following. \begin{corollary} \label{S1binthm} \[ \prod_{i=0}^{n-1} ( x + y i) = \sum_{k=0}^n \stirling{n}{k}x^k y^{n-k}. \] \end{corollary} \noindent (For a combinatorial proof of Corollary~\ref{S1binthm}, see Section~\ref{seccombo}.) Moreover, Theorem 18 in Neuwirth~\cite{Neu01} and Theorem 9 in Spivey~\cite{Spi11} give us exact formulas for numbers satisfying Equation~\eqref{GrKnPaEq} when $\beta = \beta' = 0$, just as in Corollary~\ref{multicor}. If $\alpha' \neq 0$, then Theorem 9 in Spivey~\cite{Spi11} tells us \[\Recur{n}{k} = \sum_{i=0}^n \sum_{j=0}^n \stirling{n}{i} \binom{i}{n-j} \binom{j}{k} \alpha^{j-k} (\gamma \alpha'- \alpha \gamma')^{n-j} (\alpha')^{k-i} (\gamma')^{i+j-n}.\] And if $\alpha' = 0$, Theorem 18 in Neuwirth tells us \[\Recur{n}{k} = (\gamma')^k \sum_{i=0}^n \stirling{n}{i} \binom{i}{k} \alpha^{n-i} \gamma^{i-k}.\] These are the only possibilities for $\beta = \beta' = 0$ in Equation~\eqref{GrKnPaEq}. Thus, in a sense, the binomial coefficients and the Stirling numbers of the first kind are the fundamental building blocks for numbers $\Recur{n}{k}$ satisfying a two-term recurrence of the form of Equation~\eqref{GrKnPaEq} as well as a binomial-type theorem of the form of Theorem~\ref{generalrowsum}. Let's now look at the remaining cases. In the case where $\beta \neq 0$ or $\beta' \neq 0$, Theorem~\ref{generalrowsum} only allows for a class of identities involving specific values of $x$ and $y$; namely, those satisfying $\beta y + \beta' x = 0$. The associated Stirling numbers and the Eulerian numbers fall into this category, and the identities produced are those we have already seen in Section~\ref{secExamples}. If $\beta = 0$ but $\beta' \neq 0$, or $\beta \neq 0$ but $\beta' = 0$, then the conditions in Theorem~\ref{generalrowsum} force $x = 0$ or $y=0$, respectively. In neither case do we have an interesting identity. The Stirling numbers of the second kind and the Lah numbers fall into this case. Given this, it is unsurprising that we do not see a binomial-type theorem for these sets of numbers. \section{A combinatorial proof for a binomial-type theorem for Stirling numbers of the first kind} \label{seccombo} In this final section, we present a combinatorial proof of Corollary~\ref{S1binthm}, a binomial-type theorem for the Stirling numbers of the first kind. \begin{corollary} \[\prod_{i=0}^{n-1} (x+yi) = \sum_{k=0}^n \stirling{n}{k} x^k y^{n-k}.\] \end{corollary} The Stirling numbers of the first kind $\stirling{n}{k}$ count the number of ways a permutation on $n$ elements can be formed using $k$ disjoint cycles~\cite[p.\ 259] {GrKnPa94}. The following proof is a generalization of one for the case $y = 1$ that appears in Spivey~\cite{Spi14}. \begin{proof} First, suppose $x$ and $y$ are positive integers. Then both sides count the number of colored permutations on $n$ elements satisfying the following rules: \begin{enumerate} \item The smallest element in each cycle is colored one of $x$ colors. \item Every other element is colored one of $y$ colors. \end{enumerate} For the right side, condition on the total number of cycles. There are $\stirling{n}{k}$ ways to construct a permutation on $n$ elements with $k$ disjoint cycles. There are $x^k$ ways to assign colors to the smallest element in each of the $k$ cycles. Then there are $n-k$ elements that are not the smallest in their cycles, leaving $y^{n-k}$ ways to color them. For the left side, construct a permutation by placing the elements $1, 2, \ldots, n$ in order into cycles, selecting colors as we go. If elements $1, 2, \ldots, i$ have already been put in a cycle and colored, then element $i+1$ can be placed after any of the previous elements, in $i$ ways, and colored, in $y$ ways, for a total of $yi$ choices. Alternatively, element $i+1$ can be used to start a new cycle and colored in $x$ ways. This gives a total of $x+yi$ possibilities for element $i+1$. Thus we have $x(x+y)(x+2y) \cdots (x + y(n-1))$ ways to construct a permutation satisfying our two conditions. This proves the identity for all positive integer values of $x$ and $y$. However, Corollary~\ref{S1binthm} entails a multivariate polynomial. Since we have proved the identity for infinitely many $x$ and $y$, it must hold for all real $x$ and $y$. \end{proof} \begin{thebibliography}{99} \bibitem{BaSaVi14} J. Fernando Barbero, Jes\'{u}s Salas, and Eduardo J. S. Villase{\~{n}}or. \newblock Bivariate generating functions for a class of linear recurrences: general structure. \newblock {\em J. Combin. Theory Ser. A} {\bf 125} (2014), 146--165. \bibitem{Com74} Louis Comtet. \newblock {\em Advanced Combinatorics}. \newblock D. Reidel, 1974. \bibitem{GoQu12} Henry Gould and Joceyln Quaintance. \newblock Double fun with double factorials. \newblock {\em Math.\ Mag.} {\bf 85} (2012), 177--192. \bibitem{GrKnPa94} Ronald~L. Graham, Donald~E. Knuth, and Oren Patashnik. \newblock {\em Concrete Mathematics}. \newblock Addison-Wesley, second ed., 1994. \bibitem{MaSh13} Toufik Mansour and Mark Shattuck. \newblock A combinatorial approach to a general two-term recurrence. \newblock {\em Discrete Appl. Math.} {\bf 161} (2013), 2084--2094. \bibitem{Neu01} Erich Neuwirth. \newblock Recursively defined combinatorial functions: extending {Galton's} board. \newblock {\em Discrete Math.} {\bf 239} (2001), 33--51. \bibitem{Rio68} John Riordan. \newblock {\em Combinatorial Identities}. \newblock John Wiley \& Sons, 1968. \bibitem{Spi11} Michael~Z. Spivey. \newblock On solutions to a general combinatorial recurrence. \newblock {\em J.\ Integer Sequences} {\bf 14} (2011), \newblock \href{https://cs.uwaterloo.ca/journals/JIS/VOL14/Spivey/spivey31.html}{Article 11.9.7}. \bibitem{Spi14} Michael~Z. Spivey. \newblock A combinatorial proof for the alternating convolution of the central binomial coefficients. \newblock {\em Amer. Math. Monthly} {\bf 121} (2014), 537--540. \bibitem{SpiAPBI19} Michael~Z. Spivey. \newblock {\em The Art of Proving Binomial Identities}. \newblock CRC Press, 2019. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11B37; Secondary 05A10, 11B65, 11B73, 65Q30. \noindent \emph{Keywords: } binomial coefficient, Stirling number, Eulerian number, Lah number, recurrence relation, binomial theorem, combinatorial sum. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000142}, \seqnum{A001147}, \seqnum{A007318}, \seqnum{A008275}, \seqnum{A008277}, \seqnum{A008292}, \seqnum{A008297}, \seqnum{A008299}, \seqnum{A008306}, \seqnum{A008517}, \seqnum{A048994}, \seqnum{A105278}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received May 9 2019; revised version received December 13 2019; January 9 2020. Published in {\it Journal of Integer Sequences}, June 3 2020. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}