We provide two combinatorial proofs that linear recurrences with constant coefficients have a closed form based on the roots of its characteristic equation. The proofs employ sign-reversing involutions on weighted tilings.
© 2011 Benjamin, Derks & Quinn
Benjamin, Arthur T., Halcyon Derks and Jennifer J. Quinn. "The Combinatorialization of Linear Recurrences." The Electronic Journal of Combinatorics, Vol. 18(2), P12, Zeilberger Issue, June 11, 2011.