MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer

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$.

share|cite|improve this answer
+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

share|cite|improve this answer
Could you at least give the full citation for this paper you speak of? – J. M. Nov 6 '11 at 12:20
1 for the paper on Mafia game 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.… – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.