A Combinatorial Solution to Intertwined Recurrences

Authors

Arthur T. Benjamin, Harvey Mudd CollegeFollow
Michael D. Hirschhorn, University of New South Wales

Document Type

Article

Department

Mathematics (HMC)

Publication Date

2-2007

Abstract

We provide combinatorial derivations of solutions to intertwined second order linear recurrences (such as a_n = pb_n-1 + qa_n-2, b_n = ra_n-1 + sb_n-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.

Comments

First published in the Australasian Journal of Combinatorics, vol. 37 (February 2007), by the Combinatorial Mathematics Society of Australasia.

This article is also available at http://ajc.maths.uq.edu.au/?page=get_volumes&volume=37.

Rights Information

© 2007 Combinatorial Mathematics Society of Australasia (Inc.)

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Recommended Citation

Benjamin, A.T., % Hirschhorn, M.D. (2007). A Combinatorial Solution to Intertwined Recurrences. Australasian Journal of Combinatorics, 37: 101-116.