A Different Approach to Recurrence Relations: A Combinatorial Proof of the Closed Forms for Linear Recursions
Derks, Halcyon C.
MetadataShow full item record
Given a third order linear homogeneous recurrence relation, it is possible to find a closed form by using the roots of the characteristic polynomial. This research has yielded a proof for the closed form solution when the characteristic polynomial has distinguishable roots using the method of Description, Involution, Exception, furthering the research of Benjamin and Quinn (2008), on the second order case. Using tilings to describe the recursive equation and the closed form solution, it is possible to define weights for the tiles and an involution that reduces all of the tilings of an n-board to those composed of only square tiles. Furthermore, this description and involution can be extended to prove the closed form solution for any k th order recurrence equation for which the characteristic polynomial has distinguishable roots. Also, previously undiscovered, was a method that could prove the closed form solution when the characteristic polynomial had repeated roots. This research outlines an extension of the description and involution for a second order repeated roots recursion.