# Solving a general two-term combinatorial recurrence relation

What is known about explicit (not necessarily closed-form) solutions to the recurrence $$R^n_k= (\alpha n) R^{n-1}_k + (\alpha' n + \beta' k) R^{n-1} _{k-1},$$ with initial condition $R_0^0 = 1$ and with $R^n_k = 0$ for $n < 0$ or $k < 0$? Special cases of this are closely related to recurrences satisfied by some interesting combinatorial numbers, such as the binomial coefficients and the Stirling numbers.

The more general recurrence $$R^n_k= (\alpha n + \beta k + \gamma) R^{n-1}_k + (\alpha' n + \beta' k + \gamma') R^{n-1} _{k-1},$$

is open Problem 6.94 in Concrete Mathematics (2nd edition, p. 319).

The closest published result I have found thus far is the following formula due to Neuwirth ("Recursively defined combinatorial functions: Extending Galton's board," Discrete Mathematics, 2001) for the case $\alpha' = 0$ of the Concrete Mathematics problem,

$$R^n_k = \prod_{i=1}^k (\beta' i + \gamma') \sum_{i=0}^n \sum_{j=0}^n s^n_i \binom{i}{j} S^j_k \alpha^{n-i} (\gamma - \alpha)^{i-j} \beta^{j-k},$$

which, of course, gives me an answer to my question when $\alpha'=0$. (Here, $s^n_i$ and $S^j_k$ are unsigned Stirling numbers of the first and second kinds, respectively.)

I have tried generating functions without any success thus far. An answer like Neuwirth's that involves sums and binomial coefficients or Stirling numbers would be fine, as would a partial answer or just another idea to try.

A general solution of the Graham-Knuth-Patashnik 6.94 problem

$$R^{n}_k=(\alpha \, n + \beta\, k + \gamma)\, R^{n−1}_k+ (\alpha′\, n+ \beta′\, k +\gamma′)\, R^{n−1}_{k−1} + \delta_{n,0}\delta_{k,0}\,,$$

with $R_{n}^k=0$ if $n<0$ or $k<0$, can be found in the paper Bivariate generating functions for a class of linear recurrences: General structure'', by J.F. Barbero G., J. Salas, and E.J.S. Villaseñor, published in J. Combin. Theory A 125 (2014) 146-165 (see also arXiv:1307.2010). The solution was obtained by using generating functions.

By now it is not a general answer, but I hope it may help. The method is based on the one used in the Appendix A of arXiv:1009.1031.

To calculate $R^N_K$ one can introduce densities $\rho_k(t)$ accumulating the multiplier of $R^{N-t}_k$ after using the recurrence formula $2^{t}-1$ times. Then $R^N_K$ is just $\rho_0(N)$ for the initial condition $\rho_k(0)=\delta_{Kk}$.

The set of equations of their evolution reads:

$$\rho_k(t+1) = (\alpha n + \beta k + \gamma) \rho_k(t)+(\alpha' n + \beta' (k+1) + \gamma')\rho_{k+1}(t)$$

for integer $k$ and bearing in mind that $n = N-t$.

After introducing a generating function $$G(t,z)=\sum_{k=-\infty}^\infty \rho_k(t)z^k,$$ with the initial condition $G(0,z)=z^K$, the set of equations is transformed into $$G(t+1,z) = \left( \gamma + \alpha n +(\gamma'+\alpha'n)\frac{1}{z}+(\beta z+\beta')\frac{\partial }{\partial z} \right)G(t,z).$$ So in general case $R^N_K$ is the constant term of $$\left[ \prod_{n=1}^N \left( \gamma + \alpha n +(\gamma'+\alpha'n)\frac{1}{z}+(\beta z+\beta')\frac{\partial }{\partial z} \right)\right]z^K.$$ The question is if it is possible to simplify it. As in general at different times (i.e. for different $n$) eigenvectors of the differential operators are different, one cannot use the same approach as in the paper.

However, for some special cases eigenvectors are the same for every $n$, that is for

• $\alpha' = 0$,
• $\beta = \beta' = 0$.

If decompose $z^M$ in the eigenfunctions $z^M = \sum_i a_i f_i(z)$, then instead of a product of operators one gets a product of eigenvalues $$R^N_K = \sum_i a_i \times \text{[the constant term of f_i(z)]}\times\prod_{n=1}^N \lambda_i(n).$$ I keep writing the constant term of instead of $|_{z=0}$ as when $\gamma'\neq 0$ or $\alpha'\neq 0$ one needs to tackle negative powers of $z$.

• +1 for the generating function formulation. As you say, the question is whether it is possible to simplify the expression for the constant term of the generating function. – Mike Spivey Dec 1 '11 at 23:24

have a look at Migdal(2010), paper on analysis of Mafia game, there is a vey similar problem there with some solution

• Could you at least give the full citation for this paper you speak of? – J. M. is not a mathematician Nov 6 '11 at 12:20
• arxiv.org/pdf/1009.1031 for the paper on Mafia game jstor.org/stable/3215985 for Gani's paper on random allocation model + have a look at refernces to Woodbury and Rutherford hope it helps – sigma_z_1980 Nov 6 '11 at 22:44
• Unfortunately, the recurrences in those papers don't quite match up with the one I'm asking about. And with partial difference equations like these, slight changes in the parameters can make a huge difference in the solutions. Thank you for the interesting references, though. – Mike Spivey Nov 7 '11 at 22:51
• Could you explain what exactly doesn't match up? Also you may want ot have a look at undergrad textbook by Elaydi, An Introduction to Difference Equations, Chapeter 2.4 deals with nonhomogeneous equations, maybe it helps. I asked a similar question here and on MSE, but still pretty vague about what to do. I know it uses GF and determinant of eigenmatrices somehow though. It's strange since the implication is very intuitive, especially in biological/life sciences. mathoverflow.net/questions/80194/… – sigma_z_1980 Nov 8 '11 at 2:13
• The recurrence relations in those papers don't have the parameters in the same form as in my question. As I said in my earlier comment, slight changes to the parameters in a partial difference equation can make a huge difference in the solution, so to answer my question I would need a reference in which the parameters are exactly of the same form. – Mike Spivey Nov 24 '11 at 21:52