A closed formula for linear recurrences with constant coefficients

Glenn Bruda; Bruce Fang; Pico Gilman; Raul Marquez; Steven J. Miller; Beni Prapashtica; Daeyoung Son; Saad Waheed; Janine Wang

paper

A closed formula for linear recurrences with constant coefficients

arXiv:2408.12660

Abstract

Given a linear recurrence of the form $c_{n} = a_{1} c_{n - 1} + \dots + a_{j} c_{n - j}$ , it is well-known that $c_{n} = \sum_{r} p_{r} (n) r^{n}$ , 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.

11 pages; emails and acknowledgments updated