A closed formula for linear recurrences with constant coefficients

2024/08/22 by Glenn Bruda, Bruda, Glenn, Bruce Fang +15
Computer Science · Mathematics · #11B37 #11B39 #Advanced Topics in Algebra #Combinatorics (math.CO) #FOS: Mathematics #Matrix Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.2408.12660

openalex publication_date 2024/08/22 · openalex created_date 2024/09/21 · openalex updated_date 2026/07/28

Abstract

Given a linear recurrence of the form c_n=a₁c_n-1+⋯+a_j c_n-j, it is well-known that c_n=∑_rp_r(n)rⁿ, where the sum is taken over the set of characteristic roots and each p_r(n) is some polynomial. We give a closed formula for the coefficients of each polynomial p_r(n) for any linear recurrence of this form.

Related

• Definite Sums as Solutions of Linear Recurrences With Polynomial Coefficients
• Some Linear Recurrences Motivated by Stern's Diatomic Array
• Composite polynomials in linear recurrence sequences
• Common values of a class of linear recurrence
• Linear combinations of polynomials with three-term recurrence