RECURRENCES AND GENERATING FUNCTIONS
In preceding chapters, we came across several recurrences. We will now develop a method for solving a large and important class of recurrences. Solving a recurrence for 
means finding an explicit formula for 
using initial conditions. We will employ this powerful method to confirm Binet's formulas for 
and 
.
13.1 LHRWCCs
A kth-order linear homogeneous recurrence with constant coefficients (LHRWCCs) is a recurrence of the form
where 
and 
.
We now add a few words of explanation about the definitional terms. The term linear means that every term on the RHS of equation (13.1) contains at most the first power of any predecessor . A recurrence is homogeneous ...
Get Fibonacci and Lucas Numbers with Applications, Volume 1, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
