A combinatorial approach to a general two-term recurrence

We provide combinatorial proofs of explicit formulas for some sequences satisfying particular cases of the general recurrence |nk|=(α(n−1)+βk+γ)|n−1k|+(α′(n−1)+β′k+γ′)|n−1k−1|+[n=k=0], which have been previously shown using other methods. Many interesting combinatorial sequences are special cases of this recurrence, such as binomial coefficients, both kinds of Stirling numbers, Lah numbers, and two types of Eulerian numbers. Among the cases we consider are α′=0α′=0, α=−βα=−β, and β=β′=0β=β′=0. We also provide combinatorial proofs of some prior identities satisfied by |nk| when α′=0α′=0 and when β=β′=0β=β′=0 as well as deduce some new ones in the former case. In addition, we introduce a polynomial generalization of |nk| when α′=0α′=0 which has among its special cases qq-analogues of both kinds of Stirling numbers. Finally, we supply combinatorial proofs of two formulas relating binomial coefficients and the two kinds of Stirling numbers which were previously obtained by equating three different expressions for the solution of the aforementioned recurrence in the case when α′=β′=0α′=β′=0 and all other weights are unity.