\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \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,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \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} \newtheorem{identity}[theorem]{Identity} \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 On Solutions to a \\ \vskip .15in General Combinatorial Recurrence } \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 \newcommand{\stirling}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} \newcommand{\Stirling}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} \newcommand{\Eulerian}[2]{\genfrac{<}{>}{0pt}{}{#1}{#2}} \newcommand{\Recur}[2]{\genfrac{|}{|}{0pt}{}{#1}{#2}} \newcommand{\RRecur}[2]{\genfrac{\|}{\|}{0pt}{}{#1}{#2}} \begin{abstract} We develop techniques that can be applied to find solutions to the recurrence $\Recur{n}{k} = (\alpha n + \beta k + \gamma) \Recur{n-1}{k} + (\alpha' n + \beta' k + \gamma') \Recur{n-1}{k-1} + [n=k=0]$. Many interesting combinatorial numbers, such as binomial coefficients, both kinds of Stirling and associated Stirling numbers, Lah numbers, Eulerian numbers, and second-order Eulerian numbers, satisfy special cases of this recurrence. Our techniques yield explicit expressions in the instances $\alpha = -\beta$, $\beta = \beta' = 0$, and $\frac{\alpha}{\beta} = \frac{\alpha'}{\beta} +1$, adding to the result of Neuwirth on the case $\alpha' = 0$. Our approach employs finite differences, continuing work of the author on using finite differences to study combinatorial numbers satisfying simple recurrences. We also find expressions for the power sum $\sum_{j=0}^n \Recur{n}{j} j^m$ for some special cases of the recurrence, and we prove some apparently new identities involving Stirling numbers of the second kind, Bell numbers, Rao-Uppuluri-Carpenter numbers, second-order Eulerian numbers, and both kinds of associated Stirling numbers. \end{abstract} \section{Introduction} Graham, Knuth, and Patashnik give the following open problem in {\em Concrete Mathematics} \cite[p.\ 319, Problem 6.94]{GrKnPa94}: \begin{quotation} Develop a general theory of the solutions to the two-parameter recurrence \begin{equation} \label{GrKnPaEq} \Recur{n}{k} = (\alpha n + \beta k + \gamma) \Recur{n-1}{k} + (\alpha' n + \beta' k + \gamma') \Recur{n-1}{k-1} + [n=k=0], \text{ for $n, k \geq 0$}, \end{equation} assuming that $\Recur{n}{k} = 0$ when $n < 0$ or $k < 0$. What special values ($\alpha$, $\beta$, $\gamma$, $\alpha'$, $\beta'$, $\gamma'$) yield ``fundamental solutions" in terms of which the general solution can be expressed? \end{quotation} Many numbers of combinatorial interest satisfy recurrences of the form~\eqref{GrKnPaEq}. These include binomial coefficients (\seqnum{A007318}), both kinds of Stirling numbers (\seqnum{A008275}, \seqnum{A008277}), Lah numbers (\seqnum{A008297}), Eulerian numbers (\seqnum{A008292}), second-order Eulerian numbers (\seqnum{A008517}), and even the two kinds of associated Stirling numbers (\seqnum{A008306}, \seqnum{A008299}). Perhaps the most general result thus far on solutions to~\eqref{GrKnPaEq} is due to Neuwirth~\cite{Neu01}. He proves that if $\alpha' = 0$ then \begin{equation} \label{NeuEq} \Recur{n}{k} = \prod_{i=1}^k (\beta' i + \gamma') \sum_{i=0}^n \sum_{j=0}^n \stirling{n}{i} \binom{i}{j} \Stirling{j}{k} \alpha^{n-i} (\gamma - \alpha)^{i-j} \beta^{j-k}, \end{equation} so that the solution to~\eqref{GrKnPaEq} can be expressed as a double sum involving binomial coefficients, both kinds of Stirling numbers, and generalized factorials. Moreover, for several special cases, such as $\gamma = 2 \alpha$ or $\gamma - \alpha = \beta$, this expression simplifies to a single sum or even a closed form. Neuwirth uses what he calls {\em Galton arrays}, infinite triangular matrices whose entries are the $\Recur{n}{k}$ values for recurrences of type~\eqref{GrKnPaEq}. This matrix form leads to some new insights, particularly with representing solutions to~\eqref{GrKnPaEq} in terms of solutions to simpler recurrences of the same type~\eqref{GrKnPaEq}. This, in fact, is Neuwirth's approach for deriving Equation~\eqref{NeuEq}. Regev and Roichman~\cite{ReRo06} also obtain Neuwirth's result~\eqref{NeuEq} in the presence of the additional restriction $\beta' = 0$, and they show how special cases of the resulting solutions are related to certain statistics on colored permutations. Other expressions for the solution to~\eqref{GrKnPaEq} are obtained in the case $\beta = \gamma' = 1$, $\gamma = \alpha' = \beta' = 0$ by Mijajlovi\'{c} and Markovi\'{c}~\cite{MiMa98} and by Caki\'{c}~\cite{Cak07}. Generating functions can also, of course, be used to solve many recurrences of type~\eqref{GrKnPaEq}. In fact, Graham, Knuth, and Patashnik themselves suggest an investigation of the generating function $\sum_{m,n \geq 0} \Recur{m+n}{m} w^m z^n$~\cite[p.\ 564]{GrKnPa94}. Thus far, though, the work on finding general solutions to the recurrence~\eqref{GrKnPaEq} has not primarily involved generating functions. The main purpose of this paper is to extend the results of Neuwirth on recurrences of type~\eqref{GrKnPaEq}. We prove some basic results that can be used to solve simple instances of~\eqref{GrKnPaEq}. We then find expressions for the solution to~\eqref{GrKnPaEq} for the cases $\alpha = -\beta$, $\beta = \beta' = 0$, and $\frac{\alpha}{\beta} = \frac{\alpha'}{\beta'} + 1$. The formulas we develop can be used in other cases as well, but we get explicit answers in these instances. All of the expressions involve, as with Neuwirth's result~\eqref{NeuEq}, nothing more than binomial coefficients, the two kinds of Stirling numbers, and generalized factorials. For the cases we consider, then, these numbers are the ``fundamental solutions" requested by Graham, Knuth, and Patashnik. We also use our formulas to give short derivations of some known combinatorial identities and to prove some apparently new ones involving Stirling numbers of the second kind (\seqnum{A008277}), Bell numbers (\seqnum{A000110}), Rao-Uppuluri-Carpenter numbers (\seqnum{A000587}), second-order Eulerian numbers (\seqnum{A008517}), and both kinds of associated Stirling numbers (\seqnum{A008306}, \seqnum{A008299}). Our method entails deriving an expression relating the sum $\sum_{j=0}^n \Recur{n}{j} f(j,m)$ to the sum $\sum_{j=0}^n \Recur{n}{j} \Delta_j f(j,m)$, where $\Recur{n}{k}$ satisfies a recurrence of type~\eqref{GrKnPaEq} and $\Delta_j f(j,m) = f(j+1,m) - f(j,m)$, the partial finite difference of $f$ with respect to $j$. This formula is most useful when $f(n,k) = \RRecur{n}{k}$, another solution to the recurrence~\eqref{GrKnPaEq}. In particular, by a judicious choice of the parameters involved, the sum $\sum_{j=0}^n \Recur{n}{j} \RRecur{j}{k}$ can itself be a solution to a recurrence of type~\eqref{GrKnPaEq}. In these cases, then, we can ``factor" a recurrence of type~\eqref{GrKnPaEq} into two simpler recurrences that are easier to solve, as does Neuwirth~\cite{Neu01}. The choice of $\RRecur{n}{k} = \binom{n}{k}$ is particularly helpful because it allows nearly any $\Recur{n}{k}$ satisfying \eqref{GrKnPaEq} to be so factored. Working with finite differences is not as clean as the matrix approach of Neuwirth, but the additional level of detail enables us to find explicit expressions for some classes of recurrences of type~\eqref{GrKnPaEq} that Neuwirth does not. (We note, however, that our paper does not completely avoid matrices or generating functions. There is an implicit matrix inversion in the inverse relation~\eqref{inverse}, which is used in Theorem~\ref{bintransfact} and in several examples in Section~\ref{upperbin}. We also use generating functions in the proofs of Identities~\ref{stirpowersum} and \ref{stiraltpowersum}.) This approach relating $\sum_{j=0}^n \Recur{n}{j} f(j)$ and $\sum_{j=0}^n \Recur{n}{j} \Delta_j f(j)$ was also used extensively in previous work~\cite{Spi07} of the author, usually to find an expression for the power sum $\sum_{j=0}^n \Recur{n}{j} j^m$, where $\Recur{n}{k}$ generally satisfied certain special cases of recurrence~\eqref{GrKnPaEq}. However, the formulas presented there can only handle some cases in which $\beta = \beta' = 0$. A secondary purpose of this paper, then, is to develop methods for finding the power sum in which $\beta$ and $\beta'$ are not both zero. Our result for $\sum_{j=0}^n \Recur{n}{j} \binom{j}{m}$ turns out to be key. As examples, we obtain expressions for the power sums $\sum_{j=0}^n \Eulerian{n}{j} j^m$, $\sum_{j=0}^n \langle \! \langle {n \atop j} \rangle \! \rangle j^m$, $\sum_{j=0}^n \Stirling{n}{j} j^m$, and $\sum_{j=0}^n \Stirling{n}{j} (-1)^j j^m$, where $\Eulerian{n}{k}$ is an Eulerian number (\seqnum{A008292}), $\left < \!\! \left < {n \atop k} \right > \!\! \right >$ is a second-order Eulerian number (\seqnum{A008517}), and $\Stirling{n}{k}$ is a Stirling number of the second kind (\seqnum{A008277}). The first of these four expressions is easily derivable from a known identity involving Eulerian numbers, but the other three appear to be new. In Section~\ref{basicsec} we present some basic results on recurrences of type~\eqref{GrKnPaEq}. In Section~\ref{finitediffsec} we give our formula relating $\sum_{j=0}^n \Recur{n}{j} f(j,m)$ and $\sum_{j=0}^n \Recur{n}{j} \Delta_j f(j,m)$, and we use this formula to derive expressions for the solution to~\eqref{GrKnPaEq} in the cases $\alpha = - \beta$ and $\beta = \beta' = 0$. Section~\ref{upperbin} contains our formula for the important special case $f(j,m) = \binom{j}{m}$. We use this formula to \begin{enumerate} \item give a short derivation of a known identity involving Eulerian numbers (\seqnum{A008292}), \item find apparently new expressions containing second-order Eulerian numbers (\seqnum{A008517}) and both kinds of associated Stirling numbers (\seqnum{A008306}, \seqnum{A008299}), and \item derive an expression for the solution to~\eqref{GrKnPaEq} in the case $\frac{\alpha}{\beta} = \frac{\alpha'}{\beta'} + 1$. \end{enumerate} Finally, in Section~\ref{rpsums} we apply our formula for the case $f(j,m) = \binom{j}{m}$ to find expressions for the power sums for $\Eulerian{n}{k}$, $\left < \!\! \left < {n \atop k} \right > \!\! \right >$, $\Stirling{n}{k}$, and $\Stirling{n}{k} (-1)^k $. In most instances we find it easier to work with slight variations of the recurrence~\eqref{GrKnPaEq} rather than the form in which we first stated it. In particular, the formulas are often cleaner if the coefficients $\alpha, \alpha'$, and $\beta'$ are applied to factors $n-1, n-1$, and $k-1$, respectively, instead of $n$, $n$, and $k$. For notational simplicity we also assume that $\Recur{n}{k} = 0$ when $n < 0$ or $k < 0$ and that recurrence relations hold only for $n, k \geq 0$. In addition, we take $0^0$ to be 1. \section{Basic results} \label{basicsec} In this section we present a handful of results on recurrences of the form \eqref{GrKnPaEq}. These results can be used to solve some simpler recurrences of this type. First, we have the following. \begin{theorem} \label{basic} Suppose $\RRecur{n}{k} = f_1(n,k) \RRecur{n-1}{k} + f_2(n,k) \RRecur{n-1}{k-1} + [n = k = 0]$ and $\Recur{n}{k} = h(n) g_1(n-k) f_1(n,k) \Recur{n-1}{k} + h(n) g_2(k) f_2(n,k) \Recur{n-1}{k-1} + [n = k = 0]$. Then \begin{equation} \label{basicthmeq} \Recur{n}{k} = \left(\prod_{j=1}^n h(j)\right) \left(\prod_{j=1}^{n-k} g_1(j)\right) \left(\prod_{j=1}^k g_2(j) \right)\RRecur{n}{k} . \end{equation} \end{theorem} \begin{proof} Equation~\eqref{basicthmeq} is clearly true in the case $n = k = 0$. Otherwise, \begin{align*} &h(n) g_1(n-k) f_1(n,k) \left(\prod_{j=1}^{n-1} h(j)\right) \left(\prod_{j=1}^{n-1-k} g_1(j)\right) \left(\prod_{j=1}^k g_2(j) \right) \RRecur{n-1}{k} \\ & \indent + h(n) g_2(k) f_2(n,k) \left(\prod_{j=1}^{n-1} h(j)\right) \left(\prod_{j=1}^{n-k} g_1(j)\right) \left(\prod_{j=1}^{k-1} g_2(j) \right) \RRecur{n-1}{k-1}\\ &= \left(\prod_{j=1}^{n} h(j)\right) \left(\prod_{j=1}^{n-k} g_1(j)\right) \left(\prod_{j=1}^k g_2(j) \right)f_1(n,k) \RRecur{n-1}{k} \\ & \indent + \left(\prod_{j=1}^{n} h(j)\right) \left(\prod_{j=1}^{n-k} g_1(j)\right) \left(\prod_{j=1}^{k} g_2(j) \right) f_2(n,k) \RRecur{n-1}{k-1} \\ &= \left(\prod_{j=1}^{n} h(j)\right) \left(\prod_{j=1}^{n-k} g_1(j)\right) \left(\prod_{j=1}^{k} g_2(j) \right) \RRecur{n}{k}. \end{align*} Since the right-hand side of Equation~\eqref{basicthmeq} satisfies the recurrence for $\Recur{n}{k}$, the theorem holds. \end{proof} The following corollary contains the most commonly-used special cases of Theorem~\ref{basic}. \begin{corollary} \label{useful} Let $c$ be a constant. Suppose $\RRecur{n}{k} = f_1(n,k) \RRecur{n-1}{k} + f_2(n,k) \RRecur{n-1}{k-1} + [n = k = 0]$. \begin{enumerate} \item If $\Recur{n}{k} = c f_1(n,k) \Recur{n-1}{k} + f_2(n,k) \Recur{n-1}{k-1} + [n = k = 0]$ then $\Recur{n}{k} = \RRecur{n}{k} c^{n-k}$. \item If $\Recur{n}{k} = f_1(n,k) \Recur{n-1}{k} + c f_2(n,k) \Recur{n-1}{k-1} + [n = k = 0]$ then $\Recur{n}{k} = \RRecur{n}{k} c^k $. \item If $\Recur{n}{k} = (n-k) f_1(n,k) \Recur{n-1}{k} + f_2(n,k) \Recur{n-1}{k-1} + [n = k = 0]$ then $\Recur{n}{k} = \RRecur{n}{k} (n-k)! $. \item If $\Recur{n}{k} = f_1(n,k) \Recur{n-1}{k} + k f_2(n,k) \Recur{n-1}{k-1} + [n = k = 0]$ then $\Recur{n}{k} = \RRecur{n}{k} k!$. \item If $\Recur{n}{k} = n f_1(n,k) \Recur{n-1}{k} + n f_2(n,k) \Recur{n-1}{k-1} + [n = k = 0]$ then $\Recur{n}{k} = \RRecur{n}{k} n!$. \end{enumerate} \end{corollary} The following theorem shows how to swap the coefficient functions of $\Recur{n-1}{k}$ and $\Recur{n-1}{k-1}$. It is easy to prove but quite important, as we use it in all of our major theorems that give solutions to \eqref{GrKnPaEq}. \begin{theorem} \label{swap} Suppose $\RRecur{n}{k} = f_1(n,k) \RRecur{n-1}{k} + f_2(n,k) \RRecur{n-1}{k-1} + [n = k = 0]$ and $\Recur{n}{k} = f_2(n,n-k) \Recur{n-1}{k} + f_1(n,n-k) \Recur{n-1}{k-1} + [n = k = 0]$. Then $\Recur{n}{k} = \RRecur{n}{n-k}$. \end{theorem} \begin{proof} The theorem is clearly true in the case $n=k=0$. Otherwise, we have $f_2(n,n-k) \RRecur{n-1}{n-1-k} + f_1(n,n-k) \RRecur{n-1}{n-k} = \RRecur{n}{n-k}$, completing the proof. \end{proof} %\begin{theorem} %\label{shift} %Suppose $R(n,k)$ solves $\Recur{n}{k} = f_1(n,k) \Recur{n-1}{k} + f_2(n,k) \Recur{n-1}{k-1} + [n = k = 0]$, for $n, k \geq 0$. Then, if $f_1$ and $f_2$ have the form given in column 1, column 3 contains a solution to the recurrence with the new $f_1$ and $f_2$ given in column 2. %\begin{table}[h] % \begin{center} % \begin{tabular}{cc|c||cc|c} % \multicolumn{3}{c||}{Original} & \multicolumn{3}{c}{New} \\ % $f_1(n,k)$ & $f_2(n,k)$ & Solution & $f_1(n,k)$ & $f_2(n,k)$ & Solution \\ \hline % $\alpha n + \beta k + \gamma$ & 1 & $R(n,k)$ & $\alpha n + \beta k + \beta + \gamma$ & 1 & $\beta k R(n,k+1) + R(n,k)$ \\ % $\alpha n + \gamma$ & 1 & $R(n,k)$ & $\alpha n - \alpha + \gamma$ & 1 & $\gamma R(n-1,k) + R(n-1,k-1)$ % \end{tabular} % \end{center} %\end{table} %\begin{table}[h] % \begin{center} % \begin{tabular}{cc|c||cc|c} % \multicolumn{3}{c||}{Original} & \multicolumn{3}{c}{New} \\ % $f_1(n,k)$ & $f_2(n,k)$ & Solution & $f_1(n,k)$ & $f_2(n,k)$ & Solution \\ \hline % 1 & $\alpha' n + \beta' k + \gamma'$ & $R(n,k)$ & 1 & $\alpha' n + \beta' k - \beta' + \gamma'$ & $R(n,k) + \beta'(-n + k - 1) R(n,k-1)$ \\ % 1 & $\alpha' n + \gamma'$ & $R(n,k)$ & 1 & $\alpha' n - \alpha' + \gamma'$ & $R(n-1,k) + \gamma' R(n-1,k-1)$ % \end{tabular} % \end{center} %\end{table} %\begin{enumerate} % \item Suppose $R(n,k)$ solves $\Recur{n}{k} = (\alpha n + \beta k + \gamma) \Recur{n-1}{k} + \Recur{n-1}{k-1} = [n = k = 0]$. Then a solution to $\Recur{n}{k} = (\alpha n + \beta k + \beta + \gamma) \Recur{n-1}{k} + \Recur{n-1}{k-1} = [n = k = 0]$ is $\beta k R(n,k+1) + R(n,k)$. % \item Suppose $R(n,k)$ solves $\Recur{n}{k} = (\alpha n + \gamma) \Recur{n-1}{k} + \Recur{n-1}{k-1} = [n = k = 0]$. Then a solution to $\Recur{n}{k} = (\alpha n - \alpha + \gamma) \Recur{n-1}{k} + \Recur{n-1}{k-1} = [n = k = 0]$ is $\gamma R(n,k+1) + R(n,k)$. % \item Suppose $R(n,k)$ solves $\Recur{n}{k} = \Recur{n-1}{k} + (\alpha' n + \beta' n + \gamma') \Recur{n-1}{k-1} = [n = k = 0]$. Then a solution to $\Recur{n}{k} = (\alpha n + \beta k - \beta + \gamma) \Recur{n-1}{k} + \Recur{n-1}{k-1} = [n = k = 0]$ is $R(n,k+1) + \beta(-n + k - 1) R(n,k)$. % \item Suppose $R(n,k)$ solves $\Recur{n}{k} = \Recur{n-1}{k} + (\alpha n + \gamma) \Recur{n-1}{k-1} = [n = k = 0]$. Then a solution to $\Recur{n}{k} = \Recur{n-1}{k} + (\alpha n - \alpha + \gamma) \Recur{n-1}{k-1} = [n = k = 0]$ is $R(n,k+1) + \gamma R(n,k)$. %\end{enumerate} %\end{theorem} %Our final basic result is on solutions $\RRecur{n}{k}$ to \eqref{GrKnPaEq} in which $\RRecur{n}{k}$, for $n \geq k$, is a function solely of $n$ or solely of $k$. %\begin{theorem} %\label{fn} %The only recurrences of the form %\[\Recur{n}{k} = (\alpha n + \beta k + \gamma) \Recur{n-1}{k} + (\alpha' n + \beta' k + \gamma') \Recur{n-1}{k-1} + [n=k=0] \] %that have \[\Recur{n}{k} = \begin{cases} f(n), & n \geq k; \\ 0, & n < k; \end{cases}\] %are those of the form %\[\Recur{n}{k} = (\alpha n - \alpha k) \Recur{n-1}{k} + \alpha k \Recur{n-1}{k-1} + [n=k=0]. \] %In this case, the solution is $\Recur{n}{k} = \alpha^n n! \, [n \geq k]$. %\end{theorem} %\begin{proof} %In order for $\Recur{n}{k}$, $n \geq k$, to be a function solely of $n$, we must have $\Recur{n}{k} = \Recur{n}{k-1}$ when $k \geq 1$ and $n \geq k$. This means that the recurrence simplifies, for $k \geq 1$ and $n \geq k+1$, to %\[ \Recur{n}{k} = ((\alpha + \alpha')n + (\beta + \beta')k + (\gamma + \gamma')) \Recur{n-1}{k}+ [n=k=0].\] %At the boundaries we must have $\Recur{n}{0} = (\alpha n + \gamma) \Recur{n-1}{0} + [n=0]$ and $\Recur{n}{n} = ((\alpha' + \beta') n + \gamma') \Recur{n-1}{n-1} + [n=0]$. Equating coefficients yields the following: %\begin{align*} %\alpha + \alpha' &= \alpha = \alpha' + \beta', \\ %\beta + \beta' &= 0, \\ %\gamma + \gamma' &= \gamma = \gamma'. %\end{align*} %Solving this system yields the requirements on the coefficients, and then the solution $\Recur{n}{k} = \alpha^n n! [n \geq k]$ is easy to obtain. %\end{proof} %\begin{theorem} %\label{fk} %There are no recurrences of the form %\[\Recur{n}{k} = (\alpha n + \beta k + \gamma) \Recur{n-1}{k} + (\alpha' n + \beta' k + \gamma') \Recur{n-1}{k-1} + [n=k=0] \] %that have \[\Recur{n}{k} = \begin{cases} f(k), & n \geq k; \\ 0, & n < k. \end{cases}\] %\end{theorem} %\begin{proof} %The proof is similar to that of Theorem~\ref{fn}. We must have $\Recur{n}{k} = \Recur{n-1}{k}$ when $n \geq k+1$. Thus the recurrence simplifies, for $1 \leq k \leq n-1$, to %\[ \Recur{n}{k} = \frac{\alpha' n + \beta' k + \gamma'}{-\alpha n + -\beta k - \gamma + 1} \Recur{n}{k-1}.\] %At the boundaries we have $\Recur{n}{0} = (\alpha n + \gamma) \Recur{n}{0}$ and $\Recur{n}{n} = ((\alpha' + \beta')n + \gamma') \Recur{n}{n-1} + [n=0]$. %Thus $\alpha = 0$, $\gamma = 1$, and, for all $k, 1 \leq k \leq n-1$, \[\frac{\alpha' n + \beta' k + \gamma'}{-\beta k} = (\alpha' + \beta')n + \gamma'. \] %But this last equation has no solutions that hold for all $n$ and $k$. %\end{proof} Since $\binom{n}{k}$, $\stirling{n}{k}$, and $\Stirling{n}{k}$, respectively, are solutions to the recurrences \begin{align*} &\Recur{n}{k} = \Recur{n-1}{k} + \Recur{n-1}{k-1} + [n=k=0], \\ &\Recur{n}{k} = (n-1)\Recur{n-1}{k} + \Recur{n-1}{k-1} + [n=k=0], \\ &\Recur{n}{k} = k\Recur{n-1}{k} + \Recur{n-1}{k-1} + [n=k=0], \end{align*} Theorems~\ref{basic} and \ref{swap} allow us to solve a large number of recurrences of the form~\eqref{GrKnPaEq} almost immediately. For example, Exercise 6.17 in {\em Concrete Mathematics}~\cite[p.\ 311]{GrKnPa94} asks to find the solutions to the following recurrences: \begin{align} &\Recur{n}{k} = \Recur{n-1}{k} + n \Recur{n-1}{k-1} + [n=k=0], \label{first}\\ &\Recur{n}{k} = (n-k) \Recur{n-1}{k} + \Recur{n-1}{k-1} + [n=k=0], \label{second}\\ &\Recur{n}{k} = k \Recur{n-1}{k} + k \Recur{n-1}{k-1} + [n=k=0]. \label{third} \end{align} Corollary~\ref{useful} immediately implies that the solution to \eqref{second} is $\Recur{n}{k} = \binom{n}{k}(n-k)!$ (\seqnum{A094587}) and the solution to \eqref{third} is $\Recur{n}{k} = \Stirling{n}{k} k!$ (\seqnum{A131689}). The solution to \eqref{first} is only slightly more difficult. Applying Theorem~\ref{swap} changes the problem to finding the solution to $\RRecur{n}{k} = n\RRecur{n-1}{k} + \RRecur{n-1}{k-1} + [n=k=0]$. This is almost the recurrence for $\stirling{n}{k}$, and, in fact, since $\stirling{n}{0} = [n=0]$, it can be easily shown that $\stirling{n+1}{k+1}$ solves $\RRecur{n}{k} = n\RRecur{n-1}{k} + \RRecur{n-1}{k-1} + [n=k=0]$ (see also Theorem~\ref{NeuThm}). Thus the solution to \eqref{first} is $\Recur{n}{k} = \stirling{n+1}{n+1-k}$ (\seqnum{A094638}). A somewhat more complicated example involves the recursion \begin{equation} \label{BinSq} \Recur{n}{k} = (n+k) \Recur{n-1}{k} + \Recur{n-1}{k-1} + [n=k=0]. \end{equation} By Theorem~\ref{basic}, we can solve the recurrence~\eqref{BinSq} if we can solve \begin{align*} \RRecur{n}{k} &= (n-k)(n+k) \RRecur{n-1}{k} + k^2\RRecur{n-1}{k-1} + [n=k=0] \\ &= (n^2-k^2) \RRecur{n-1}{k} + k^2\RRecur{n-1}{k-1} + [n=k=0]. \end{align*} But, since $n^2 - k^2 + k^2 = n^2$, $\RRecur{n}{0} = n^2 \RRecur{n-1}{0} + [n=0]$, and $\RRecur{n}{n} = n^2 \RRecur{n-1}{n-1} + [n=0]$, it must be the case that $\RRecur{n}{k} = (n!)^2 [n \geq k]$. Thus the solution to~\eqref{BinSq} is $\Recur{n}{k} = \frac{(n!)^2}{(n-k)!(k!)^2}[n \geq k] = \binom{n}{k}^2 (n-k)!$ (\seqnum{A021009}). \section{Factoring with finite differences} \label{finitediffsec} We now develop a few results that greatly expand our ability to solve recurrences of the form~\eqref{GrKnPaEq}. Let $\Delta_j f(j,m)$ denote the finite difference of $f(j,m)$ with respect to $j$; i.e., $\Delta_j f(j,m) = f(j+1,m) - f(j,m)$. We have the following. \begin{theorem} \label{finitediff} Suppose $\Recur{n}{k} = (\alpha (n-1) + \beta k + \gamma) \Recur{n-1}{k} + (\alpha' (n-1) + \beta' (k-1) + \gamma') \Recur{n-1}{k-1} + [n=k=0]$. Then, for $n \geq 1$, \begin{align*} \sum_{j=0}^n \Recur{n}{j} f(j,m) &= \sum_{j=0}^{n-1} \Recur{n-1}{j} \left( (\alpha + \alpha')(n-1) + (\beta + \beta')j + \gamma + \gamma' \right) f(j,m) \\ &\indent + \sum_{j=0}^{n-1} \Recur{n-1}{j} (\alpha' (n-1) + \beta' j + \gamma') \Delta_j f(j,m). \end{align*} \end{theorem} \begin{proof} By definition, \[\sum_{j=0}^{n-1} \Recur{n-1}{j} \Delta_j g(n,j,m) = \sum_{j=0}^{n-1} \Recur{n-1}{j} g(n,j+1,m) - \sum_{j=0}^{n-1} \Recur{n-1}{j} g(n,j,m).\] Let $g(n,j,m) = (\alpha' (n-1) + \beta'(j-1) + \gamma')f(j,m)$. Then $\Delta_j g(n,j,m) = (\alpha' (n-1) + \beta'j + \gamma') \Delta_j f(j,m) + \beta' f(j,m)$ (see, for instance, \cite[p.\ 55]{GrKnPa94}). We then have \bigbreak \begin{align*} &\sum_{j=0}^{n-1} \Recur{n-1}{j} ((\alpha' (n-1) + \beta'j + \gamma') \Delta_j f(j,m) + \beta' f(j,m)) \\ &= \sum_{j=0}^{n-1} \Recur{n-1}{j} (\alpha' (n-1) + \beta'j + \gamma')f(j+1,m) - \sum_{j=0}^{n-1} \Recur{n-1}{j} (\alpha' (n-1) + \beta'(j-1) + \gamma')f(j,m)\\ &= \sum_{j=0}^{n-1} \Recur{n}{j+1} f(j+1,m) - \sum_{j=0}^{n-1} \Recur{n-1}{j+1} (\alpha (n-1) + \beta (j+1) + \gamma)f(j+1,m) \\ & \indent - \sum_{j=0}^{n-1} \Recur{n-1}{j} (\alpha' (n-1) + \beta'(j-1) + \gamma')f(j,m) \end{align*} \begin{align*} &= \sum_{j=0}^n \Recur{n}{j} f(j,m) - \sum_{j=0}^{n-1} \Recur{n-1}{j} (\alpha (n-1) + \beta j + \gamma)f(j,m) \\ & \indent - \sum_{j=0}^{n-1} \Recur{n-1}{j} (\alpha' (n-1) + \beta'(j-1) + \gamma')f(j,m) \\ & \indent - \Recur{n}{0} f(0,m) + \Recur{n-1}{0} (\alpha(n-1) + \gamma)f(0,m) - \Recur{n-1}{n} (\alpha (n-1) + \beta n + \gamma)f(n,m). \end{align*} Since the recursion definition implies $\Recur{n}{0} = \Recur{n-1}{0} (\alpha (n-1) + \gamma)$ and $\Recur{n-1}{n} = 0$, collecting terms yields the result. \end{proof} The most useful values of $f(j,m)$ in Theorem~\ref{finitediff} for the present work are numbers $\RRecur{n}{k}$ (with $j=n$ and $m=k$) themselves satisfying a recurrence of the form~\eqref{GrKnPaEq}. \begin{corollary} \label{sumprod} Suppose $\Recur{n}{k} = (\alpha (n-1) + \beta k + \gamma) \Recur{n-1}{k} + (\alpha' (n-1) + \beta' (k-1) + \gamma') \Recur{n-1}{k-1} + [n=k=0]$ and $\RRecur{n}{k} = (\bar{\alpha} (n-1) + \bar{\beta} k + \bar{\gamma}) \RRecur{n-1}{k} + (\bar{\bar{\alpha}} (n-1) + \bar{\bar{\beta}} (k-1) + \bar{\bar{\gamma}}) \RRecur{n-1}{k-1} + [n=k=0]$. Then \begin{align*} \sum_{j=0}^n \Recur{n}{j} \, \RRecur{j}{k} = &\sum_{j=0}^{n-1} \Recur{n-1}{j} \, \RRecur{j}{k} \bigg(\left(\alpha + \alpha'\left(\bar{\alpha}j + \bar{\beta}k + \bar{\gamma}\right)\right) (n-1) \\ &\indent + \left( \beta + \beta' \left(\bar{\alpha}j + \bar{\beta}k + \bar{\gamma}\right) + \gamma'\bar{\alpha} \right) j + \gamma + \gamma' \left(\bar{\beta}k + \bar{\gamma}\right) \bigg) \\ &+ \sum_{j=0}^{n-1} \Recur{n-1}{j} \, \RRecur{j}{k-1} \bigg( \alpha'\left(\bar{\bar{\alpha}}j + \bar{\bar{\beta}}(k-1) + \bar{\bar{\gamma}}\right) (n-1) \\ &\indent + \left(\beta'\left(\bar{\bar{\alpha}}j + \bar{\bar{\beta}}(k-1) + \bar{\bar{\gamma}}\right) + \gamma'\bar{\bar{\alpha}}\right)j + \gamma'\left(\bar{\bar{\beta}}(k-1) + \bar{\bar{\gamma}}\right)\bigg) \\ &+ [n=k=0]. \end{align*} \end{corollary} \begin{proof} If $n = 0$ then $\sum_{j=0}^n \Recur{0}{j} \, \RRecur{j}{k} = \RRecur{0}{k} = [k=0]$. For $n \geq 1$ and $j \geq 0$, we have \begin{align*} \Delta_j \RRecur{j}{k} &= \RRecur{j+1}{k} - \RRecur{j}{k} \\ &= (\bar{\alpha} j + \bar{\beta} k + \bar{\gamma}) \RRecur{j}{k} + (\bar{\bar{\alpha}} j + \bar{\bar{\beta}} (k-1) + \bar{\bar{\gamma}}) \RRecur{j}{k-1} - \RRecur{j}{k} \\ &= (\bar{\alpha} j + \bar{\beta} k + \bar{\gamma} - 1) \RRecur{j}{k} + (\bar{\bar{\alpha}} j + \bar{\bar{\beta}} (k-1) + \bar{\bar{\gamma}}) \RRecur{j}{k-1}. \end{align*} Applying Theorem~\ref{finitediff} and collecting terms yields the result. \end{proof} Corollary~\ref{sumprod} is important mainly because of special cases of $\alpha, \beta, \gamma, \alpha', \beta'$, and $\gamma'$ in which all of the terms involving $j$ vanish. Then Corollary~\ref{sumprod} reduces to a recurrence of the form $S(n,k) = f_1(n,k) S(n-1,k) + f_2(n,k) S(n-1,k-1) + [n=k=0]$, where $S(n,k) = \sum_{j=0}^n \Recur{n}{j} \RRecur{j}{k}$. If, furthermore, the terms involving $nk$ also vanish, then $f_1$ and $f_2$ are each linear functions of $n$ and $k$, and thus we have a recurrence relation of the form~\eqref{GrKnPaEq}. (Neuwirth~\cite{Neu01} gives examples of scenarios in which this happens.) The value of these latter special cases of Corollary~\ref{sumprod} is that they enable us to ``factor" certain recurrences of the type~\eqref{GrKnPaEq} into simpler recurrences that may be solvable. In particular, when combined with Theorem~\ref{basic}, we can obtain the expression~\eqref{NeuEq} due to Neuwirth~\cite{Neu01} for the case $\alpha' = 0$ of recurrence~\eqref{GrKnPaEq}, although we express it in a slightly different form. \begin{theorem} \label{NeuThm} (Neuwirth) If $\Recur{n}{k} = (\alpha (n-1) + \beta k + \gamma) \Recur{n-1}{k} + (\beta'k + \gamma') \Recur{n-1}{k-1} + [n=k=0]$, then \[\Recur{n}{k} = \prod_{i=1}^k (\beta' i + \gamma') \sum_{i=0}^n \sum_{j=0}^n \stirling{n}{i} \binom{i}{j} \Stirling{j}{k} \alpha^{n-i} \beta^{j-k} \gamma^{i-j} . \] \end{theorem} \begin{proof} By Theorem~\ref{basic}, $\Recur{n}{k} = \prod_{i=1}^k (\beta' i + \gamma') \RRecur{n}{k}$, where $\RRecur{n}{k}$ satisfies \[\RRecur{n}{k} = (\alpha (n-1) + \beta k + \gamma) \RRecur{n-1}{k} + \RRecur{n-1}{k-1} + [n=k=0]. \] By Corollary~\ref{sumprod}, $\RRecur{n}{k} = \sum_{j=0}^n R(n,j) S(j,k)$, where \begin{align*} R(n,k) &= (\alpha(n-1) + \gamma)R(n-1,k) + R(n-1,k-1) + [n=k=0],\\ S(n,k) &= \beta k S(n,k) + S(n-1,k-1) + [n=k=0]. \end{align*} By Corollary~\ref{useful}, $S(n,k) = \Stirling{n}{k} \beta^{n-k}$, and an expression for $R(n,k)$ can be obtained by applying Corollary~\ref{sumprod} again. We have $R(n,k) = \sum_{i=0}^n T(n,i) U(i,k)$, where \begin{align*} T(n,k) &= \alpha(n-1) T(n-1,k) + T(n-1,k-1) + [n=k=0], \\ U(n,k) &= \gamma U(n-1,k) + U(n-1,k-1) = [n=k=0]. \end{align*} By Corollary~\ref{useful}, $T(n,k) = \stirling{n}{k}\alpha^{n-k} $ and $U(n,k) = \binom{n}{k} \gamma^{n-k}$. \end{proof} Regev and Roichman~\cite{ReRo06} refer to solutions $\Recur{n}{k}$ in Theorem~\ref{NeuThm} for the case $\beta' = 0$, $\gamma' = 1$ as {\em binomial-Stirling numbers}. If any of $\alpha$, $\beta$, or $\gamma$ is zero then the following identities (see, for example,~\cite[p.\ 265]{GrKnPa94}) can be used to simplify the solution in Theorem~\ref{NeuThm}: \begin{align*} \sum_{i=0}^n \stirling{n}{i} \binom{i}{j} &= \stirling{n+1}{j+1}, \\ \sum_{j=0}^n \binom{n}{j} \Stirling{j}{k} &= \Stirling{n+1}{k+1}. \end{align*} For example, Theorem~\ref{NeuThm} gives the solution to the recurrence~\eqref{BinSq} to be \[\Recur{n}{k} = \sum_{i=0}^n \sum_{j=0}^n \stirling{n}{i} \binom{i}{j} \Stirling{j}{k}.\] Simplifying this result and comparing it with our original solution to \eqref{BinSq} yields the following identity: \begin{identity} \[\binom{n}{k}^2 (n-k)! = \sum_{j=0}^n \stirling{n+1}{j+1} \Stirling{j}{k} = \sum_{j=0}^n \stirling{n}{j} \Stirling{j+1}{k+1}.\] \end{identity} We can also obtain an expression for the solution to the case $\alpha = -\beta$ in the recurrence~\eqref{GrKnPaEq} by combining Theorem~\ref{swap} with Theorem~\ref{NeuThm}. \begin{theorem} \label{fact1} If $\Recur{n}{k} = (\alpha n - \alpha k + \gamma) \Recur{n-1}{k} + (\alpha'(n-1) + \beta'(k-1) + \gamma') \Recur{n-1}{k-1} + [n=k=0]$ then \[\Recur{n}{k} = \prod_{i=1}^{n-k} (\alpha i + \gamma) \sum_{i=0}^n \sum_{j=0}^n \stirling{n}{i} \binom{i}{j} \Stirling{j}{n-k} (\alpha'+ \beta')^{n-i} (-\beta')^{j+k-n} (\gamma')^{i-j}. \] \end{theorem} \begin{proof} By Theorem~\ref{swap}, $\Recur{n}{k} = \RRecur{n}{n-k}$, where $\RRecur{n}{k}$ satisfies the recurrence \[\RRecur{n}{k} = ((\alpha'+ \beta')(n-1) - \beta'k + \gamma') \RRecur{n-1}{k} + (\alpha k + \gamma) \RRecur{n-1}{k-1} + [n=k=0].\] Applying Theorem~\ref{NeuThm} completes the proof. \end{proof} In addition, we can find an expression for the solution to~\eqref{GrKnPaEq} when $\beta = \beta' = 0$, $\alpha' \neq 0$, by going back to Corollary~\ref{sumprod}. (If $\alpha'=0$ then we use Theorem~\ref{NeuThm} instead.) \begin{theorem} \label{factnok} If $\alpha' \neq 0$ and $\Recur{n}{k} = (\alpha (n-1) + \gamma) \Recur{n-1}{k} + (\alpha'(n-1) + \gamma') \Recur{n-1}{k-1} + [n=k=0]$ then \[\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{theorem} \begin{proof} By Corollary~\ref{sumprod}, $\Recur{n}{k} = \sum_{j=0}^n R(n,j) S(j,k)$, where \begin{align*} R(n,k) &= \left(\gamma - \frac{\alpha \gamma'}{\alpha'}\right)R(n-1,k) + \left(n - 1 + \frac{\gamma'}{\alpha'}\right)R(n-1,k-1) + [n=k=0], \\ S(n,k) &= \alpha S(n,k) + \alpha' S(n-1,k-1) + [n=k=0]. \end{align*} By Corollary~\ref{useful}, $S(n,k) = \binom{n}{k} \alpha^{n-k} (\alpha')^k$. By Theorem~\ref{swap} and Corollary~\ref{useful}, $R(n,k) = T(n,n-k) (\gamma - \frac{\alpha \gamma'}{\alpha'})^{n-k}$, where \[T(n,k) = \left(n - 1 + \frac{\gamma'}{\alpha'}\right) T(n-1,k) + T(n-1,k-1) + [n=k=0].\] By Theorem~\ref{NeuThm}, $T(n,k) = \sum_{i=0}^n \stirling{n}{i} \binom{i}{k} (\frac{\gamma'}{\alpha'})^{i-k}$. \end{proof} \section{An upper binomial transform} \label{upperbin} Using Theorems~\ref{NeuThm}, \ref{fact1}, and \ref{factnok} to factor a recurrence of type~\eqref{GrKnPaEq} into recurrences of simpler types is based on cases of Corollary~\ref{sumprod} in which all nonlinear terms and terms involving $j$ vanish. In this section we prove that for most cases letting $\RRecur{n}{k} = \binom{n}{k}$ in Corollary~\ref{sumprod}, scaling the coefficient of $\Recur{n-1}{k}$ or $\Recur{n-1}{k-1}$ appropriately via Corollary~\ref{useful}, and applying properties specific to $\binom{n}{k}$ will also cause all nonlinear terms and terms involving $j$ to vanish. The cases 1) $\alpha \neq 0$, $\beta = 0$, $\beta' \neq 0$ and 2) $\alpha' \neq 0$, $\beta' = 0$, $\beta \neq 0$ are the only two for which this procedure does not work. Thus, except in these cases, the solution $\Recur{n}{k}$ to any recurrence of type~\eqref{GrKnPaEq} produces a sum $\RRecur{n}{k} = \sum_{j=0}^n \Recur{n}{j} \binom{j}{k}$, where $\RRecur{n}{k}$ satisfies another recurrence of type~\eqref{GrKnPaEq}. Then the inverse relation~\cite[p.\ 45]{Rio68} \begin{equation} \label{inverse} \RRecur{n}{k} = \sum_{j=0}^n \Recur{n}{j} \binom{j}{k} \Longleftrightarrow \Recur{n}{k} = \sum_{j=0}^n \RRecur{n}{j} \binom{j}{k} (-1)^{j+k} \end{equation} implies that if we can find an expression for $\RRecur{n}{k}$ then we have one for $\Recur{n}{k}$ as well. In particular, for the case $\frac{\alpha}{\beta} = \frac{\alpha'}{\beta'}+1$, $\RRecur{n}{k}$ can be factored using Theorem~\ref{fact1}. Since the expression $\sum_{j=0}^n \binom{n}{j} a_j$ is sometimes called the {\em binomial transform}~\cite{SpSt06} the sum $\sum_{j=0}^n \Recur{n}{j} \binom{j}{k}$ can be considered a kind of {\em upper binomial transform}. %Let $f(k) = k^m$. Then $\Delta f(k) = \sum_{j=0}^{m-1} \binom{m}{j} k^j$. Let $S^m_n = \sum_{k=0}^n \Recur{n}{k} k^m$. Theorem~\ref{finitediff} then yields %\begin{align*} %&\sum_{k=0}^{n+1} \Recur{n+1}{k} k^m - \sum_{k=0}^n \Recur{n}{k} \left( (\alpha + \alpha')n + (\beta + \beta')k + \alpha + \alpha' + \beta' + \gamma + \gamma' \right) k^m \\ %&= \sum_{k=0}^n \Recur{n}{k} (\alpha' n + \beta' k + \alpha' + \beta' + \gamma') \sum_{j=0}^{m-1} \binom{m}{j} k^j, %\end{align*} %which implies %\begin{align} %&(\beta + \beta') S^{m+1}_n = S^m_{n+1} - \left((\alpha + \alpha')n + \alpha + \alpha' + \beta'(m + 1) + \gamma + \gamma' \right)S^m_n \nonumber \\ %&- \sum_{j=0}^{m-1} \left((\alpha' n + \alpha' + \beta' + \gamma') \binom{m}{j} + \beta' \binom{m}{j-1} \right) S^j_n. \label{psumrecur} %\end{align} %If $\beta + \beta' \neq 0$, then, we have that $S^1_n$ can be expressed as a linear combination of $S_{n+1}$ and $S_n$, $S^2_n$ can be expressed as a linear combination of $S_{n+2}$, $S_{n+1}$ and $S_n$, and so forth, so that in general $S^m_n$ can be expressed as a linear combination of $S_{n+m}, S_{n+m-1}, \ldots, S_n$. Moreover, while it is difficult to do for general $\alpha, \alpha', \beta, \beta', \gamma, \gamma'$, the constants in the linear combination can be obtained for a specific instance of these parameters by solving the recurrence \eqref{psumrecur}. The sequence $S_n$ turns out to be fundamental, then, in understanding the behavior of the falling power sum $\sum_{k=0}^n \Recur{n}{k} k^m$. \begin{theorem} \label{bintrans} Suppose $\Recur{n}{k} = (\alpha (n-1) + \beta k + \gamma) \Recur{n-1}{k} + (\alpha' (n-1) + \beta' (k-1) + \gamma') \Recur{n-1}{k-1} + [n=k=0]$. Let $\RRecur{n}{k}$ denote the sum $\sum_{j=0}^n \Recur{n}{j} \binom{j}{k}$. Then \begin{align*} \RRecur{n}{k} &= (\beta + \beta') (k+1) \RRecur{n-1}{k+1} + \big((\alpha + \alpha')(n-1) + (\beta + 2\beta') k + \gamma + \gamma' \big) \RRecur{n-1}{k} \\ & \indent + (\alpha' (n-1) + \beta'(k-1) + \gamma') \RRecur{n-1}{k-1} + [n=k=0]. \end{align*} \end{theorem} \begin{proof} By Corollary~\ref{sumprod}, \begin{align*} &\sum_{j=0}^{n} \Recur{n}{j} \binom{j}{k} \\ &= \sum_{j=0}^n \Recur{n-1}{j} \binom{j}{k} \big( (\alpha + \alpha')(n-1) + (\beta + \beta')j + \gamma + \gamma' \big) \\ &\indent + \sum_{j=0}^n \Recur{n-1}{j} \binom{j}{k-1}(\alpha' (n-1) + \beta' j + \gamma') + [n=k=0] \\ &= \sum_{j=0}^n \Recur{n-1}{j} \binom{j}{k}\big( (\alpha + \alpha')(n-1) + (\beta + \beta')(j - k) + (\beta + \beta')k + \gamma + \gamma' \big) \\ &\indent +\sum_{j=0}^n \Recur{n-1}{j} \binom{j}{k-1} \big(\alpha' (n-1) + \beta' (j - k + 1 ) + \beta'(k-1) + \gamma'\big) + [n=k=0] \end{align*} \begin{align*} &= (\beta + \beta')(k+1) \sum_{j=0}^n \Recur{n-1}{j} \binom{j}{k+1} \\ &\indent + \sum_{j=0}^n \Recur{n-1}{j} \binom{j}{k} \big( (\alpha + \alpha')(n-1) + (\beta + 2\beta')k + \gamma + \gamma' \big) \\ &\indent +\sum_{j=0}^n \Recur{n-1}{j} \binom{j}{k-1} (\alpha' (n-1) + \beta'(k-1) + \gamma') + [n=k=0] , \end{align*} where we have used the fact that $(j-k) \binom{j}{k} = (k+1) \binom{j}{k+1}$. (This is easily proved by expressing $\binom{j}{k}$ as $\frac{j!}{k!(j-k)!}$.) \end{proof} Thus if $\beta + \beta'=0$, the choice of $\RRecur{j}{k} = \binom{j}{k}$ in Corollary~\ref{sumprod} produces a recurrence of type~\eqref{GrKnPaEq}. We state this fact formally in the following corollary. \begin{corollary} \label{bintranscor} Suppose $\Recur{n}{k} = (\alpha (n-1) + \beta k + \gamma) \Recur{n-1}{k} + (\alpha' (n-1) + \beta' (k-1) + \gamma') \Recur{n-1}{k-1} + [n=k=0]$, with $\beta + \beta' = 0$. Let $\RRecur{n}{k}$ denote the sum $\sum_{j=0}^n \Recur{n}{j} \binom{j}{k}$. Then \begin{align*} \RRecur{n}{k} = &\big((\alpha + \alpha')(n-1) + \beta' k + \gamma + \gamma' \big)\RRecur{n-1}{k}+ (\alpha' (n-1) + \beta'(k-1) + \gamma') \RRecur{n-1}{k-1} \\ &+ [n+k=0]. \end{align*} \end{corollary} We now give a few examples illustrating Corollary~\ref{bintranscor}. The first is a short derivation of two known expressions relating the Eulerian numbers $\Eulerian{n}{k}$ (\seqnum{A008292}) and the Stirling numbers of the second kind $\Stirling{n}{k}$ (\seqnum{A008277}). \begin{identity} \label{Eulerbin} \[\Stirling{n}{k} k! = \sum_{j=0}^n \Eulerian{n}{j} \binom{j}{n-k} \] \end{identity} \begin{identity} \label{Eulerian} \[\Eulerian{n}{k} = \sum_{j=0}^n \Stirling{n}{j} \binom{n-j}{k} (-1)^{n-j+k} j!\] \end{identity} \begin{proof} The Eulerian numbers satisfy the recurrence~\cite[p.\ 268]{GrKnPa94} \[\Eulerian{n}{k} = (k+1)\Eulerian{n-1}{k} + (n-k)\Eulerian{n-1}{k-1} + [n = k = 0].\] By Corollary~\ref{bintranscor}, $\RRecur{n}{k} = \sum_{j=0}^n \Eulerian{n}{j} \binom{j}{k}$ satisfies $\RRecur{n}{k} = (n-k) \RRecur{n-1}{k} + (n-k)\RRecur{n-1}{k-1} + [n=k=0]$. But this recurrence is easy to solve: Corollary~\ref{useful} tells us that $\RRecur{n}{k} = (n-k)! R(n,k)$, where $R(n,k)$ satisfies \[R(n,k) = R(n-1,k) + (n-k)R(n-1,k-1) + [n=k=0].\] By Theorem~\ref{swap}, $R(n,k) = \Stirling{n}{n-k}$. This proves $\Stirling{n}{n-k} (n-k)! = \sum_{j=0}^n \Eulerian{n}{j} \binom{j}{k}$. Reindexing produces Identity~\ref{Eulerbin}. Applying the inverse relation~\eqref{inverse} to Identity~\ref{Eulerbin}, we have %\[ \Eulerian{n}{k} = \sum_{j=0}^n (-1)^{j+k} (n-j)! \Stirling{n}{n-j} \binom{j}{k}. \] $ \Eulerian{n}{k} = \sum_{j=0}^n \Stirling{n}{n-j} \binom{j}{k} (-1)^{j+k} (n-j)!. $ Reindexing yields Identity~\ref{Eulerian}. \end{proof} Identities~\ref{Eulerbin} and \ref{Eulerian} are stated in Graham, Knuth, and Patashnik~\cite[p.\ 269]{GrKnPa94}, and Identity~\ref{Eulerian} is proved in Charalambides~\cite[p.\ 519]{Cha02} via Eulerian polynomials. Another example yields what are apparently new identities relating the second-order Eulerian numbers $\left < \!\! \left < {n \atop k} \right > \!\! \right >$ (\seqnum{A008517}) and the associated Stirling numbers of the first kind $\left [ \!\! \left [ {n \atop k} \right ] \!\! \right ]$ (\seqnum{A008306}). The second-order Eulerian numbers satisfy the recurrence~\cite[p.\ 270]{GrKnPa94} \[\left < \!\! \left < {n \atop k} \right > \!\! \right > = (k+1) \left < \!\! \left < {n \atop k} \right > \!\! \right > + (2n-k-1)\left < \!\! \left < {n \atop k} \right > \!\! \right > + [n=k=0],\] and the associated Stirling numbers of the first kind $\left [ \!\! \left [ {n \atop k} \right ] \!\! \right ]$ satisfy (see, for example, Comtet~\cite[p.\ 256]{Com74} or Fekete~\cite{Fek94}) \[\left [ \!\! \left [ {n \atop k} \right ] \!\! \right ] = (n-1) \left [ \!\! \left [ {n-1\atop k} \right ] \!\! \right ] + (n-1) \left [ \!\! \left [ {n-2 \atop k-1} \right ] \!\! \right ] + [n=k=0].\] We have the following. \begin{identity} \label{Euler2bin} \[\left [ \!\! \left [ {n+k \atop k} \right ] \!\! \right ] = \sum_{j=0}^n \left < \!\! \left < {n \atop j} \right > \!\! \right > \binom{j}{n-k} \] \end{identity} \begin{identity} \label{Euler2} \[ \left < \!\! \left < {n \atop k} \right > \!\! \right > =\sum_{j=0}^n \left [ \!\! \left [ {n+j \atop j} \right ] \!\! \right ] \binom{n-j}{k} (-1)^{n-j+k}\] \end{identity} \begin{proof} The recurrence satisfied by the associated Stirling numbers of the first kind can be converted to the form of the recurrence~\eqref{GrKnPaEq} via the transformation $S_1(n,k) = \left [ \!\! \left [ {n + k \atop k} \right ] \!\! \right ]$, which changes diagonals of $\left [ \!\! \left [ {n \atop k} \right ] \!\! \right ]$ into rows of $S_1(n,k)$. The numbers $S_1(n,k)$ then satisfy \begin{equation} \label{S1recur} S_1(n,k) = (n+k-1) S(n-1,k) + (n+k-1) S(n-1,k-1) + [n=k=0]. \end{equation} Applying Corollary~\ref{bintranscor}, we have that the sum $T(n,k) = \sum_{j=0}^n \langle \! \langle {n \atop j} \rangle \! \rangle \binom{j}{k}$ satisfies the recurrence \[T(n,k)= (2n-k-1) T(n-1,k) + (2n-k-1) T(n-1,k-1) + [n = k = 0].\] By Theorem~\ref{swap}, $T(n,n-k)$ satisfies the recurrence for $S_1(n,k)$. This proves Identity~\ref{Euler2bin}. Replacing $k$ with $n-k$ in Identity~\ref{Euler2bin} and applying the inverse relation~\eqref{inverse} yields $\left < \!\! \left < {n \atop k} \right > \!\! \right > = \sum_{j=0}^n [ \!\! [ {2n-j \atop n-j} ] \!\! ] \binom{j}{k} (-1)^{j+k} $. Reindexing produces Identity~\ref{Euler2}. \end{proof} In many cases the restriction that $\beta + \beta'$ be zero does not really prevent one from using Corollary~\ref{bintranscor}. This is because, thanks to Corollary~\ref{useful}, any recurrence of the form~\eqref{GrKnPaEq} with $\beta \neq 0$ and $\beta' \neq 0$ can have the coefficient of $\Recur{n-1}{k}$ or $\Recur{n-1}{k-1}$ scaled so that Corollary~\ref{bintranscor} can be applied. In addition, if $\alpha = \beta = 0$, then Corollary~\ref{useful} allows for the factor $\beta'(n-k)$ to be introduced to the coefficient of $\Recur{n-1}{k}$ so that Corollary~\ref{bintranscor} can be applied. Similarly, if $\alpha' = \beta' = 0$, then Corollary~\ref{useful} shows that introducing the factor $-\beta k$ to the coefficient of $\Recur{n-1}{k-1}$ allows Corollary~\ref{bintranscor} to be used. We illustrate this idea by deriving an apparently new relationship between the associated Stirling numbers of the first (\seqnum{A008306}) and second (\seqnum{A008299}) kinds. The associated Stirling numbers of the second kind are denoted $\left \{ \!\! \left \{ {n \atop k} \right \} \!\! \right \}$ and satisfy the recurrence (see, for example, Comtet~\cite[p.\ 221--222]{Com74} or Fekete~\cite{Fek94}) \[\left \{ \!\! \left \{ {n \atop k} \right \} \!\! \right \} = k \left \{ \!\! \left \{ {n-1\atop k} \right \} \!\! \right \} + (n-1) \left \{ \!\! \left \{ {n-2 \atop k-1} \right \} \!\! \right \} + [n=k=0].\] \begin{identity} \label{assStir1} \[ \left [ \!\! \left [ {n+k \atop k} \right ] \!\! \right ] = \sum_{j=0}^n \left \{ \!\! \left \{ {n + j \atop j} \right \} \!\! \right \} \binom{j-1}{k-1} (-1)^{n+j} + [n=k=0]\] \end{identity} \begin{identity} \label{assStir2} \[ \left \{ \!\! \left \{ {n + k \atop k} \right \} \!\! \right \} = \sum_{j=0}^n \left [ \!\! \left [ {n+j \atop j} \right ] \!\! \right ] \binom{j-1}{k-1} (-1)^{n+j} + [n=k=0] \] \end{identity} \begin{proof} As with the associated Stirling numbers of the first kind, the recurrence for the associated Stirling numbers of the second kind can be converted to the form~\eqref{GrKnPaEq} via the transformation $S_2(n,k) = \left \{ \!\! \left \{ {n + k \atop k} \right \} \!\! \right \}$, where, as before, diagonals are changed to rows. Then the numbers $S_2(n,k)$ satisfy \begin{equation} \label{S2recur} S_2(n,k) = k S_2(n-1,k) + (n+k-1) S_2(n-1,k-1) + [n=k=0]. \end{equation} Moreover, we can see from the recurrence that $S_2(n,0) = [n=0]$ and $S_2(1,1) = 1$. Thus $S'_2(n,k) = S_2(n+1,k+1)$ is also of the form~\eqref{GrKnPaEq} and, in fact, satisfies \[S'_2(n,k) = (k+1)S'_2(n,k) + (n+k+1)S'_2(n,k) + [n=k=0].\] It is also the case that $S_1(n,0) = [n=0]$ and $S_1(1,1) = 1$; thus $S'_1(n,k) = S_1(n+1,k+1)$ is of the form~\eqref{GrKnPaEq} as well, and \[S'_1(n,k) = (n+k+1)S'_1(n,k) + (n+k+1)S'_1(n,k) + [n=k=0].\] %By Corollary~\ref{useful}, the numbers $(-1)^k S'_2(n,k)$ satisfy $\Recur{n}{k} = (k+1) \Recur{n-1}{k} + (-n-k-1) \Recur{n-1}{k-1} + [n=k=0]$, and, then, by Corollary~\ref{bintranscor} By Corollaries~\ref{useful} and \ref{bintranscor} the sum $T(n,k) = \sum_{j=0}^n S'_2(n,j) \binom{j}{k} (-1)^j $ satisfies \[T(n,k) = (-n-k-1) T(n-1,k) + (-n-k-1) T(n-1,k-1) + [n=k=0].\] Applying Corollary~\ref{useful} again, we see that $(-1)^n \sum_{j=0}^n S'_2(n,j) \binom{j}{k} (-1)^j $ satifies %$\Recur{n}{k} = (n+k+1) \Recur{n-1}{k} + (n+k+1) \Recur{n-1}{k-1} + [n=k=0]$, the recurrence for $S'_1(n,k)$. Putting all of this together, we have, for $k \geq 0$, the identity $\left [ \!\! \left [ {n+k+2 \atop k+1} \right ] \!\! \right ] = \sum_{j=0}^n \{ \!\! \{ {n + j+2 \atop j+1} \} \!\! \} \binom{j}{k} (-1)^{n+j}$. Reindexing and including the boundary condition $\left [ \!\! \left [ {n \atop 0} \right ] \!\! \right ] = [n=k=0]$ produces Identity~\ref{assStir1}. By Equation~\eqref{inverse}, we also have, for $k \geq 0$, $\left \{ \!\! \left \{ {n + k+2 \atop k+1} \right \} \!\! \right \} = \sum_{j=0}^n [ \!\! [ {n+j+2 \atop j+1} ] \!\! ] \binom{j}{k} (-1)^{n+j}$. Reindexing and including the boundary condition $\left \{ \!\! \left\{ {n \atop 0} \right \} \!\! \right \} = [n=k=0]$ yields Identity~\ref{assStir2}. \end{proof} We also have the following more general result, which uses Corollary~\ref{bintranscor} to transform recurrences of type~\eqref{GrKnPaEq} in which $\frac{\alpha}{\beta} = \frac{\alpha'}{\beta'} + 1$ into a form in which Theorem~\ref{fact1} can be applied. \begin{theorem} \label{bintransfact} If $\frac{\alpha}{\beta} = \frac{\alpha'}{\beta'} + 1$, then the solution to $\Recur{n}{k} = (\alpha(n-1) + \beta k + \gamma) \Recur{n-1}{k} + (\alpha'(n-1) + \beta'(k-1) + \gamma') \Recur{n-1}{k-1} + [n=k=0]$ is \begin{align*} \Recur{n}{k} &= \sum_{l=0}^n \left(\prod_{i=1}^{n-l} \left(-i + 1 - \frac{\gamma}{\beta} + \frac{\gamma'}{\beta'} \right) \right) \binom{l}{k} \\ &\indent \times \left( \sum_{i=0}^n \sum_{j=0}^n \stirling{n}{i} \binom{i}{j} \Stirling{j}{n-l} (-1)^j \alpha^{n-i} \beta^{i-k} \left(\beta'\right)^{j+k-i} \left(\gamma'\right)^{i-j} \right) . \end{align*} \end{theorem} \begin{proof} By Corollary~\ref{useful}, $\Recur{n}{k} = R(n,k) (-1)^{n-k} (\frac{\beta}{\beta'})^{n-k} $, where $R(n,k)$ satisfies the recurrence \begin{align*} R(n,k) &= \left(-\frac{\alpha \beta'}{\beta}(n-1) - \beta'k - \frac{\gamma \beta'}{\beta}\right) R(n-1,k) \\ &\indent + (\alpha'(n-1) + \beta'(k-1) + \gamma') R(n-1,k-1) + [n=k=0]. \end{align*} Letting $S(n,k) = \sum_{j=0}^n R(n,j) \binom{j}{k}$ and applying Corollary~\ref{bintranscor}, we have \begin{align*} S(n,k) &= \left(\left(\alpha' - \frac{\alpha \beta'}{\beta}\right)(n-1) + \beta'k + \left(\gamma' - \frac{\gamma \beta'}{\beta}\right)\right)S(n-1,k) \\ &\indent + (\alpha'(n-1) + \beta'(k-1) +\gamma') S(n-1,k-1) + [n=k=0]. \end{align*} Since, by assumption, $\alpha' = \frac{\alpha \beta'}{\beta} - \beta'$, this is the recurrence \begin{align*} S(n,k) &= \left(-\beta'(n-1) + \beta'k + \left(\gamma' - \frac{\gamma \beta'}{\beta}\right)\right)S(n-1,k) \\ &\indent + (\alpha'(n-1) + \beta'(k-1) +\gamma') S(n-1,k-1) + [n=k=0]. \end{align*} By Theorem~\ref{fact1}, \[S(n,k) = \prod_{i=1}^{n-k} \left(-\beta'i + \beta' + \gamma' - \frac{\gamma \beta'}{\beta}\right) \sum_{i=0}^n \sum_{j=0}^n \stirling{n}{i} \binom{i}{j} \Stirling{j}{n-k} (\alpha'+\beta')^{n-i} (-\beta')^{j+k-n} (\gamma')^{i-j}. \] Applying Equation~\eqref{inverse}, we have \begin{align*} \Recur{n}{k} = &(-1)^{n-k} \left(\frac{\beta}{\beta'}\right)^{n-k} \sum_{l=0}^n (-1)^{l+k} \left( \prod_{i=1}^{n-l} \left(-\beta'i + \beta' + \gamma' - \frac{\gamma \beta'}{\beta}\right) \right) \binom{l}{k}\\ &\indent \times \left(\sum_{i=0}^n \sum_{j=0}^n \stirling{n}{i} \binom{i}{j} \Stirling{j}{n-l} (\alpha'+\beta')^{n-i} (-\beta')^{j+l-n} (\gamma')^{i-j}\right). \end{align*} Since, by assumption, $\alpha' + \beta' = \frac{\alpha \beta'}{\beta}$, simpifying this expression completes the proof. \end{proof} %\begin{theorem} %If $\frac{a}{b} = \frac{\alpha'}{b'} + 1$, then the solution to $\Recur{n}{k} = (a(n-1) + bk + c) \Recur{n-1}{k} + (a'(n-1) + b'k + c') \Recur{n-1}{k-1} + [n=k=0]$ is %\begin{align*} %\Recur{n}{k} &= a^n \left(\frac{b'}{b}\right)^k \sum_{l=0}^n \prod_{i=1}^{n-l} \left(-i + 2 + \frac{c'}{b'} - \frac{c}{b}\right) \\ % &\indent \times \left( \sum_{i=0}^n \sum_{j=0}^n \left(\frac{b}{a} + \frac{c' b}{ab'}\right)^i \left(\frac{-b'}{b'+c'}\right)^j \stirling{n}{i} \binom{i}{j} \Stirling{j}{n-l} \right) \binom{l}{k}. %\end{align*} %\end{theorem} %\begin{proof} %By Corollary~\ref{useful}, the solution to $\Recur{n}{k}$ is $(-1)^{n-k} \left(\frac{b}{b'}\right)^{n-k} R(n,k)$, where $R(n,k)$ satisfies the recurrence $R(n,k) = (-\frac{ab'}{b}(n-1) - b'k - \frac{cb'}{b}) R(n-1,k) + (a'(n-1) + b'k + c') R(n-1,k-1) + [n=k=0]$. Applying Corollary~\ref{bintranscor}, we have that $\sum_{j=0}^n R(n,j) \binom{j}{k}$ satisfies the recurrence $S(n,k) = ((a' - \frac{ab'}{b})(n-1) + b'k + (b' + c' - \frac{cb'}{b}))S(n-1,k) + (a'(n-1) + b'k +c') S(n-1,k-1) + [n=k=0]$. Since, by assumption, $a' = \frac{ab'}{b} - b'$, this is the recurrence $S(n,k) = (-b'(n-1) + b'k + (b' + c' - \frac{cb'}{b}))S(n-1,k) + (a'(n-1) + b'k +c') S(n-1,k-1) + [n=k=0]$. By Theorem~\ref{fact1}, %\[S(n,k) = \prod_{i=1}^{n-k} \left(-b'i + 2b' + c' - \frac{cb'}{b}\right) \sum_{i=0}^n \sum_{j=0}^n (a'+b')^{n-i} (b'+c')^{i-j} (-b')^{j+k-n} \stirling{n}{i} \binom{i}{j} \Stirling{j}{n-k}. \] %Applying Equation~\eqref{inverse}, we have %\begin{align*} %\Recur{n}{k} = &(-1)^{n-k} \left(\frac{b}{b'}\right)^{n-k} \sum_{l=0}^n (-1)^{l+k} \Bigg( \prod_{i=1}^{n-l} \left(-b'i + 2b' + c' - \frac{cb'}{b}\right) \\ % &\indent \times \sum_{i=0}^n \sum_{j=0}^n (a'+b')^{n-i} (b'+c')^{i-j} (-b')^{j+l-n} \stirling{n}{i} \binom{i}{j} \Stirling{j}{n-l} \Bigg) \binom{l}{k}. %\end{align*} %Since, by assumption, $a' + b' = \frac{ab'}{b}$, simpifying this expression completes the proof. %\end{proof} \section{Row sums and power sums} \label{rpsums} For many combinatorial numbers $\Recur{n}{k}$ satisfying recurrence~\eqref{GrKnPaEq} the row sum $\sum_{j=0}^n \Recur{n}{j}$, or, more generally, the power sum $\sum_{j=0}^n \Recur{n}{j} j^m$, is of interest. In this section we discuss some consequences of our results pertaining to these quantities. Denote the power sum $\sum_{j=0}^n \Recur{n}{j} j^m$ by $S^m_n$. For notational simplicity we also refer to the row sum $S^0_n$ by $S_n$. First, we have the following result on row sums (also proved by Neuwirth~\cite{Neu01}). \begin{corollary} (Neuwirth) \label{rowsums} Suppose $\Recur{n}{k}$ satisfies $\Recur{n}{k} = (\alpha (n-1) + \beta k + \gamma) \Recur{n-1}{k} + (\alpha' (n-1) + \beta' (k-1) + \gamma') \Recur{n-1}{k-1} + [n=k=0]$ and that $\beta + \beta' = 0$. Then \[ \sum_{k=0}^n \Recur{n}{k} = \prod_{i=0}^{n-1} \left((\alpha + \alpha')i + \gamma + \gamma' \right).\] \end{corollary} \begin{proof} Taking $k=0$ in Corollary~\ref{bintranscor} means that the row sum $S_n$ satisfies the recurrence \[S_n = \big((\alpha + \alpha')(n-1) + \gamma + \gamma' \big)S_{n-1} + [n=0].\] \end{proof} The (known) row sums for several well-known combinatorial numbers are special cases of Corollary~\ref{rowsums}. Some of these are given in Table~\ref{rowsumtable}. \begin{table}[h] \begin{center} \begin{tabular}{cccc} & & Recurrence Values & \\ Name & Notation & $(\alpha, \beta, \gamma; \alpha', \beta', \gamma')$ & Row Sum \\ \hline Binomial coefficients & $\binom{n}{k}$ & $(0, 0, 1; 0, 0, 1)$ & $2^n$ \\ Alternating binomial coefficients & $ \binom{n}{k} (-1)^k$ & $(0,0,1;0,0,-1)$ & $[n=0]$ \\ Signed Stirling numbers, first kind & $s(n,k)$ & $(-1,0,0;0,0,1)$ & $[n=0] + [n=1]$ \\ Unsigned Stirling numbers, first kind & $\stirling{n}{k}$ & $(1,0,0;0,0,1)$ & $n!$ \\ Eulerian numbers & $\Eulerian{n}{k}$ & $(0,1,1;1,-1,0)$ & $n!$ \\ Second-order Eulerian numbers & $\left < \!\! \left < {n \atop k} \right > \!\! \right >$ & $(0,1,1;2,-1,0)$ & $(2n-1)!!$ \\ \end{tabular} \caption{Row sums for some combinatorial numbers} \label{rowsumtable} \end{center} \end{table} Corollary~\ref{rowsums}, applied to the recurrences \eqref{S1recur} and \eqref{S2recur}, immediately yields the following identities on alternating diagonal sums of the two kinds of associated Stirling numbers (\seqnum{A008306}, \seqnum{A008299}). \begin{identity} \label{aStir1diag} \[\sum_{k=0}^n \left [ \!\! \left [ {n+k \atop k} \right ] \!\! \right ] (-1)^k = (-1)^n\] \end{identity} \begin{identity} \[\sum_{k=0}^n \left \{ \!\! \left \{ {n + k \atop k} \right \} \!\! \right \} (-1)^k = (-1)^n n!\] \end{identity} (Identity~\ref{aStir1diag} at least is known, as it appears in Comtet~\cite[p.\ 256]{Com74}.) In addition, Theorem~\ref{bintrans} and Corollary~\ref{rowsums} answer a question in the author's paper~\cite{Spi07}. In this work we derive formulas that can be used to find the row sums for numbers satisfying recurrences of the form~\eqref{GrKnPaEq} that have $\beta = \beta' = 0$. In particular, numbers of this type have ``nice" row sums. However, some combinatorial numbers that do not have $\beta = \beta' = 0$ (such as the Eulerian (\seqnum{A008292}) and second-order Eulerian numbers (\seqnum{A008517})) also have ``nice" expressions for their rows sums, while others (such as the Stirling numbers of the second kind (\seqnum{A008277})) do not. Theorem~\ref{bintrans} and Corollary~\ref{rowsums} explain this difference: The requirement for a ``nice" row sum (in the sense here) is that $\beta + \beta'$ be zero. If $\beta + \beta' = 0$, then we obtain the fairly simple expression in Corollary~\ref{rowsums}, but if $\beta + \beta' \neq 0$ then, from Theorem~\ref{bintrans}, we have the more complicated expression \[S_n = (\beta + \beta') S^1_{n-1} + \big((\alpha + \alpha')(n-1) + \gamma + \gamma' \big)S_{n-1} + [n=0]\] that also contains the sum $S^1_{n-1} = \sum_{j=0}^{n-1} \Recur{n-1}{j} j$. %For example, the row sums for the Stirling numbers of the second kind $\Stirling{n}{k}$ satisfy %\[ \sum_{k=0}^n \Stirling{n}{k} = \sum_{k=0}^{n-1} \Stirling{n-1}{k} k + \sum_{k=0}^{n-1} \Stirling{n-1}{k} + [n=0].\] In the more general case of the power sum $\sum_{k=0}^n \Recur{n}{j} j^m$ we can also use Theorem~\ref{bintrans} or Corollary~\ref{bintranscor}. This is because $\binom{j}{m} m! = j^{\underline{m}}$, and we can convert falling powers $j^{\underline{m}}$ to ordinary powers $j^m$ via the relation~\cite[p.\ 264]{GrKnPa94} \begin{equation} \label{falltoord} j^m = \sum_{i=0}^m \Stirling{m}{i} j^{\underline{i}}. \end{equation} As examples, we find expressions for the sums $\sum_{j=0}^n \Eulerian{n}{j} j^m$, $\sum_{j=0}^m \langle \! \langle {n \atop j} \rangle \! \rangle j^m$, $\sum_{j=0}^n \Stirling{n}{j} j^m$, and $\sum_{j=0}^n \Stirling{n}{j} (-1)^j j^m$. Doing so completes the author's study begun in Spivey~\cite{Spi07} of using finite differences to find explicit expressions for the power sum $\sum_{j=0}^n \Recur{n}{j} j^m$ for some common combinatorial numbers $\Recur{n}{k}$ . \begin{identity} \[\sum_{j=0}^n \Eulerian{n}{j} j^m = \sum_{i=0}^m \Stirling{m}{i} \Stirling{n}{n-i} i! (n-i)!\] %= \sum_{j=0}^n \Eulerian{n}{j} \sum_{i=0}^m \Stirling{m}{i} j^{\underline{i}} \end{identity} \begin{proof} Identity~\ref{Eulerbin} implies \[\sum_{j=0}^n \Eulerian{n}{j} j^{\underline{i}} = \sum_{j=0}^n \Eulerian{n}{j} \binom{j}{i} i! = \Stirling{n}{n-i} i! (n-i)! .\] Applying Equation~\eqref{falltoord} then yields the result. \end{proof} \begin{identity} \[\sum_{j=0}^n \left < \!\! \left < {n \atop j} \right > \!\! \right > j^m = \sum_{i=0}^m \Stirling{m}{i} \left [ \!\! \left [ {2n-i \atop n-i} \right ] \!\! \right ] i! \] \end{identity} \begin{proof} Identity~\ref{Euler2bin} implies \[\sum_{j=0}^n \left < \!\! \left < {n \atop j} \right > \!\! \right > j^{\underline{i}} = \sum_{j=0}^n \left < \!\! \left < {n \atop j} \right > \!\! \right > \binom{j}{i} i! = \left [ \!\! \left [ {2n-i \atop n-i} \right ] \!\! \right ] i! .\] Applying Equation~\eqref{falltoord} produces the identity. \end{proof} The power sum for the Stirling numbers of the second kind (\seqnum{A008277}), $\sum_{j=0}^n \Stirling{n}{j} j^m$, is more complicated because Theorem~\ref{bintrans} must be used instead of Corollary~\ref{bintranscor}. In particular, if $\RRecur{n}{m}$ denotes $\sum_{j=0}^n \Stirling{n}{j} \binom{j}{m}$, then Theorem~\ref{bintrans} implies, for $m \geq 0$, \[\RRecur{n}{m} = (m+1) \RRecur{n-1}{m+1} + (m + 1)\RRecur{n-1}{m}+ \RRecur{n-1}{m-1},\] Reindexing and rearranging terms, we have, for $m \geq 1$, \begin{equation} \label{Stirlingrecur} \RRecur{n}{m} = \frac{1}{m}\RRecur{n+1}{m-1} - \RRecur{n}{m-1} - \frac{1}{m} \RRecur{n}{m-2}. \end{equation} Taking $m = 1$, we see that $\sum_{j=0}^n \Stirling{n}{j} \binom{j}{1}$ can be expressed as a linear combination of the Bell numbers (\seqnum{A000110}) $\varpi(n)$ and $\varpi(n+1)$, where $\varpi(n) = \sum_{j=0}^n \Stirling{n}{j}$~\cite[p.\ 210]{Com74}, and the coefficients do not depend on $n$. Taking $m=2$ in the recurrence~\eqref{Stirlingrecur} shows that $\sum_{j=0}^n \Stirling{n}{j} \binom{j}{2}$ can be written as a linear combination of $\varpi(n), \varpi(n+1)$, and $\varpi(n+2)$, where, once again, the coefficients do not depend on $n$. In general, we can see that $\sum_{j=0}^n \Stirling{n}{j} \binom{j}{m}$ can be expressed as a linear combination of $\varpi(n), \varpi(n+1), \ldots, \varpi(n+m)$, where the coefficients do not depend on $n$. Since $\binom{j}{m} m! = j^{\underline{m}}$, and in view of Equation~\eqref{falltoord}, the power sum $\sum_{j=0}^n \Stirling{n}{j} j^m$ can be expressed in the form $\sum_{i=0}^m c_{mi} \varpi(n+i)$, where the $c_{mi}$ coefficients do not depend on $n$. Determining the $c_{mi}$ for small values of $m$ leads to the conjecture $c_{mi} = \binom{m}{i} R(m-i)$, where $R(n) = \sum_{j=0}^n \Stirling{n}{j} (-1)^j$, the $n$th alternating row sum of the Stirling numbers of the second kind, also known as the the $n$th Rao-Uppuluri-Carpenter number (\seqnum{A000587})~\cite{RUC69}. This turns out to be the case, and, once conjectured, easily established using generating functions. More generally, we have the following identities. \begin{identity} \label{stirpowersum} \[\sum_{j=0}^n \Stirling{n}{j} j^m = \sum_{i=0}^m \binom{m}{i} R(m-i) \varpi(n+i) \] \end{identity} \begin{identity} \label{stiraltpowersum} \[\sum_{j=0}^n \Stirling{n}{j} (-1)^j j^m = \sum_{i=0}^m \binom{m}{i} \varpi(m-i) R(n+i) \] \end{identity} \begin{proof} The Bell numbers have exponential generating function (egf) $e^{e^x-1}$, and the Rao-Uppuluri-Carpenter numbers have egf $e^{1-e^x}$~\cite[p.\ 351]{GrKnPa94}. It is known that if $f(x)$ is the egf of the sequence $\{a_i\}_0^{\infty}$, then $D^n(f(x))$ is the egf of the sequence $\{a_{n+i}\}_0^{\infty}$~\cite[p.\ 40]{Wil94}, where $D^n$ denotes differentiation $n$ times with respect to $x$. Thus the egf of $\{\varpi(n+i)\}_{i=0}^{\infty}$ is $D^n (e^{e^x-1})$, and the egf of $\{R(n+i)\}_{i=0}^{\infty}$ is $D^n (e^{1-e^x})$. We now prove, by induction, that $D^n(e^{e^x-1}) = e^{e^x-1} \sum_{j=0}^n \Stirling{n}{j} e^{jx}$. We know the claim is true for $n=0$. Since $D (e^{e^x-1}) = e^x (e^{e^x-1})$, the claim is also true for $n=1$. Assuming, for $n \geq 2$, the claim is true in the case $n-1$, we have\bigbreak \begin{align*} D^n \left(e^{e^x-1}\right) &= D \left(e^{e^x-1} \sum_{j=0}^{n-1} \Stirling{n-1}{j} e^{jx} \right) \\ &= e^{e^x-1} \left(\sum_{j=0}^{n-1} \Stirling{n-1}{j} j e^{jx} + \sum_{j=0}^{n-1} \Stirling{n-1}{j} e^{(j+1)x} \right) \\ &= e^{e^x-1} \left(\sum_{j=0}^{n-1} \Stirling{n-1}{j} j e^{jx} + \sum_{j=1}^{n} \Stirling{n-1}{j-1} e^{j x} \right) \\ &= e^{e^x-1} \left(\sum_{j=0}^{n-1} \Stirling{n}{j} e^{jx} + \Stirling{n-1}{n-1} e^{jx} \right) \\ &= e^{e^x-1} \left(\sum_{j=0}^n \Stirling{n}{j} e^{jx} \right). \end{align*} (In the second-to-last step, we used the recurrence $\Stirling{n}{k} = k \Stirling{n-1}{k} + \Stirling{n-1}{k-1}$ and the fact that $\Stirling{n}{0} = 0$ for $n \geq 1$. In the last step, we used the fact that $\Stirling{n}{n} = \Stirling{n-1}{n-1}$.) A similar argument shows that $D^n (e^{1-e^x}) = e^{1-e^x} \sum_{j=0}^n \Stirling{n}{j} (-1)^j e^{jx}$. Since it is the case that if $f(x)$ is the egf for $\{a_n\}_0^{\infty}$ and $g(x)$ is the egf of $\{b_n\}_0^{\infty}$, then $f(x)g(x)$ is the egf of the sequence $\sum_{i=0}^n \binom{n}{i} a_i b_{n-i}$~\cite[p.\ 42]{Wil94}, we have that the egf of $\sum_{i=0}^m \binom{m}{i} R(m-i) \varpi(n+i) $ is $\sum_{j=0}^n \Stirling{n}{j} e^{jx}$. Because $e^{jx} = \sum_{m=0}^{\infty} \frac{j^m x^m}{m!}$ this egf can be expressed as \begin{equation} \label{Stirgen} \sum_{m=0}^{\infty} \sum_{j=0}^n \Stirling{n}{j} j^m \frac{x^m}{m!}. \end{equation} Since the coefficient of $\frac{x^m}{m!}$ in this expression is $\sum_{j=0}^n \Stirling{n}{j} j^m$, Expression~\eqref{Stirgen} must also be the egf of $\sum_{j=0}^n \Stirling{n}{j} j^m$. Thus $\sum_{j=0}^n \Stirling{n}{j} j^m = \sum_{i=0}^m \binom{m}{i} R(m-i) \varpi(n+i) $. A similar argument shows that $\sum_{j=0}^n \Stirling{n}{j} (-1)^j j^m = \sum_{i=0}^m \binom{m}{i} \varpi(m-i) R(n+i) $. \end{proof} %However, if $\beta + \beta' \neq 0$, then, we have that $S^1_n$ can be expressed as a linear combination of $S_{n+1}$ and $S_n$, $S^2_n$ can be expressed as a linear combination of $S_{n+2}$, $S_{n+1}$ and $S_n$, and so forth, so that in general $S^m_n$ can be expressed as a linear combination of $S_{n+m}, S_{n+m-1}, \ldots, S_n$. Moreover, while it is difficult to do for general $\alpha, \alpha', \beta, \beta', \gamma, \gamma'$, the constants in the linear combination can be obtained for a specific instance of these parameters by solving the recurrence \eqref{psumrecur}. The sequence $S_n$ turns out to be fundamental, then, in understanding the behavior of the power sum $\sum_{k=0}^n \Recur{n}{k} k^{\underline m}$. Remark: Here, the investigation of Equation~\eqref{Stirlingrecur} led to expressions for the power sum and alternating power sum for the Stirling numbers of the second kind (\seqnum{A008277}). Viewing Equation~\eqref{Stirlingrecur} from another perspective led to a new recurrence for the Bell numbers (\seqnum{A000110})~\cite{Spi08}. \begin{thebibliography}{10} \bibitem{Cak07} N. P. Caki\'{c}, \newblock On the numbers related to the Stirling numbers of the second kind, \newblock {\em Facta Univ. Ser. Math. Inform.} {\bf 22} (2007), 105--108. \bibitem{Cha02} C. A. Charalambides, \newblock {\em Enumerative Combinatorics}, \newblock CRC Press, 2002. \bibitem{Com74} L. Comtet, \newblock {\em Advanced Combinatorics}, \newblock D. Reidel, Dordrecht, Holland, 1974. \bibitem{Fek94} A. E. Fekete, \newblock Apropos two notes on notation, \newblock {\em Amer. Math. Monthly} {\bf 101} (1994), 771--778. \bibitem{GrKnPa94} R. L. Graham, D. E. Knuth, and O. Patashnik, \newblock {\em Concrete Mathematics}, 2nd ed., \newblock Addison-Wesley, 1994. \bibitem{MiMa98} \^{Z}. Mijajlovi\'{c} and Z.~Markovi\'{c}, \newblock Some recurrence formulas related to the differential operator $\theta d$, \newblock {\em Facta Univ. Ser. Math. Inform.} {\bf 13} (1998) 7--17. \bibitem{Neu01} E. Neuwirth, \newblock Recursively defined combinatorial functions: extending Galton's board, \newblock {\em Discrete Math.} {\bf 239} (2001), 33--51. \bibitem{RUC69} V. R. Rao-Uppuluri and J. A. Carpenter, \newblock Numbers generated by the function $e^{1-e^x}$, \newblock {\em Fibonacci Quart.} {\bf 7} (1969), 437--448. \bibitem{ReRo06} A. Regev and Y. Roichman, \newblock Statistics on wreath products and generalized binomial-Stirling numbers, \newblock {\em Israel J. Math.} {\bf 151} (2006), 189--221. \bibitem{Rio68} J. Riordan, \newblock {\em Combinatorial Identities}, \newblock John Wiley \& Sons, 1968. \bibitem{Spi07} M. Z. Spivey, \newblock Combinatorial sums and finite differences, \newblock {\em Discrete Math.} {\bf 307} (2007), 3130--3146. \bibitem{Spi08} M. Z. Spivey, \newblock A generalized recurrence for Bell numbers, \newblock {\em J. Integer Sequences} {\bf 11} (2008), \newblock \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Spivey/spivey25.html}{Article 08.2.5}. \bibitem{SpSt06} M. Z. Spivey and L. L. Steil, \newblock The $k$-binomial transforms and the Hankel transform, \newblock {\em J. Integer Sequences} {\bf 9} (2006), \newblock \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Spivey/spivey7.html}{Article 06.1.1}. \bibitem{Wil94} H. S. Wilf, \newblock {\em Generatingfunctionology}, 2nd ed., \newblock Academic Press, 1994. \end{thebibliography} \noindent(Concerned with sequences A000110, A000587, A007318, A008275, A008277, A008292, A008297, A008299, A008306, A008517, A021009, A094587, A094638, A131689.) \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11B37; Secondary 05A10, 05A19, 11B65, 11B73, 11B83, 65Q30. \noindent \emph{Keywords: } Recurrence relation, finite difference, associated Stirling number, Bell number, Eulerian number, Rao-Uppuluri-Carpenter number. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000110}, \seqnum{A000587}, \seqnum{A007318}, \seqnum{A008275}, \seqnum{A008277}, \seqnum{A008292}, \seqnum{A008297}, \seqnum{A008299}, \seqnum{A008306}, \seqnum{A008517}, \seqnum{A021009}, \seqnum{A094587}, \seqnum{A094638}, and \seqnum{A131689}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received October 18 2010; revised version received October 19 2011. Published in {\it Journal of Integer Sequences}, November 21 2011. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} .