## Solving Two-Term Combinatorial Recurrence Relations, Part II

A few years ago I published a paper [2] giving a partial answer to the following question in Graham, Knuth, and Patashnik’s Concrete Mathematics (Problem 6.92):

Develop a general theory of the solutions to the two-parameter recurrence

$\displaystyle \left| n \atop k \right| = (\alpha n + \beta k + \gamma) \left| n-1 \atop k \right| + (\alpha' n + \beta' k + \gamma') \left| n-1 \atop k-1 \right| + [n=k=0].$

A post from a few years ago discusses the results in my paper.  I also asked a question on Math Overflow (my first MO question!) asking for other known results.

Well, a recent paper by Barbero, Salas, and Villaseñor, “Bivariate Generating Functions for a Class of Linear Recurrences: General Structure” [1], gives a complete solution to this recurrence in the form of exponential generating functions.  I’m not going to try to summarize their paper here, as it’s too technical, although I will mention that they do have to break the recurrence into cases to obtain their results.  (Given my earlier work on the problem this does not surprise me.)  If you’re interested, take a look.  They do some very nice work to get their results.

References

1.  Barbero, Salas, and Villaseñor, “Bivariate Generating Functions for a Class of Linear Recurrences: General Structure,” Journal of Combinatorial Theory, Series A, 125 (2014) 146-165.

2.  Spivey, Michael Z.,  “On Solutions to a General Combinatorial Recurrence,” Journal of Integer Sequences, 14 (9): Article 11.9.7, 2011.