Many named combinatorial numbers satisfy the following general twoterm combinatorial recurrence relation:
For example:
 Binomial coefficients:
 Stirling cycle numbers:
 Stirling subset numbers:
 Lah numbers:
 Eulerian numbers:
 Secondorder Eulerian numbers:
It is not known how to solve the recurrence in general. In fact, research problem 6.94 in Concrete Mathematics [1] is to develop a general theory of solutions to the recurrence. (Update: See my May 13, 2014, post on Barbero, Salas, and Villaseñor’s paper, in which they find a complete solution to the recurrence in terms of exponential generating functions.)
Partial results are known, however – some of which I recently published [3]. In this post I’ll summarize the main results from that paper.
Theorem 1 (the case ):
If
then
where
are the Stirling cycle and subset numbers, respectively. (This theorem was first proved by Neuwirth [2].)
Theorem 2 (the case ):
If
then
Theorem 3 (the case ):
If and
then
Theorem 4:
If , then the solution to
is
References

Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, 2nd edition, AddisonWesley, 1994.
 Erich Neuwirth, “Recursively defined combinatorial functions: extending Galton’s board,” Discrete Mathematics 239, pp. 3351, 2001.
 Michael Z. Spivey, “On solutions to a general combinatorial recurrence,” Journal of Integer Sequences 14 (9): Article 11.9.7, 2011.
Pingback: Solving TwoTerm Combinatorial Recurrence Relations, Part II  A Narrow Margin