A Generalized Formula for the A-th Element of a N-Nacci Recursive Sequence Using Complex Residues

Overview

Objectives/Goals The objective of the project was to derive a closed form formula for the A-th element of a N-Nacci recursive sequence using the residue theorem from complex analysis. Methods/Materials In order to derive such a formula, I began with finding a closed form for the generating function for a N-Nacci recursive sequence. After this I showed that the generating function will be holomorphic for a suitable length of Z less than epsilon. I then proceeded to use Cauchy's Differentiation Formula to extract the A-th element of the sequence. Following this I used the Residue Theorem to relate the A-th element to the residues of the closed form generating function not about zero. Finally, I wrote two brief proofs to show that the generating function would only contain simple poles of multiplicity one, as well as a short proof of Binet's Formula. Results It was determined that the A-th element of any linear homogeneous recurrence relation with constant coefficients is equal to the negative sum of the residues of its closed form generating function not about zero. Conclusions/Discussion The results of this project show a deep connection between complex residues and linear homogeneous recurrence relations with constant coefficients. It provides a different method to solving recurrence relations than the standard linear algebraic method.

Awards (1)

• Fourth Place

Competition history

• CSEF 2013 Mathematics & Software · Entry S1498

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2013 project
• CSEF Fourth Place winners