We provide combinatorial derivations of solutions to intertwined second order linear recurrences (such as an = pbn-1 + qan-2, bn = ran-1 + sbn-2) by counting tilings of length n strips with squares and dominoes of various colors and shades. A similar approach can be applied to intertwined third order recurrences with coefficients equal to one. Here we find that all solutions can be expressed in terms of tribonacci numbers. The method can also be easily extended to solve and combinatorially comprehend kth order Fibonacci recurrences.
© 2007 Combinatorial Mathematics Society of Australasia (Inc.)
Benjamin, A.T., % Hirschhorn, M.D. (2007). A Combinatorial Solution to Intertwined Recurrences. Australasian Journal of Combinatorics, 37: 101-116.