image

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 c013-math-001 means finding an explicit formula for c013-math-002 using initial conditions. We will employ this powerful method to confirm Binet's formulas for c013-math-003 and c013-math-004.

13.1 LHRWCCs

A kth-order linear homogeneous recurrence with constant coefficients (LHRWCCs) is a recurrence of the form

where c013-math-006 and c013-math-007.

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 live online training, plus books, videos, and digital content from nearly 200 publishers.