LINEAR RECURRENCE SEQUENCES WITH INDICES IN ARITHMETIC PROGRESSION AND THEIR SUMS

摘要

For an arbitrary homogeneous linear recurrence sequence of order d with constant coecients, we derive recurrence relations for all subsequences with indices in arithmetic progression. The coecients of these recurrences are given explicitly in terms of partial Bell polynomials that depend on at most d 1 terms of the generalized Lucas sequence associated with the given recurrence. We also provide an elegant formula for the partial sums of such sequences and illustrate all of our results with examples of various orders, including common generalizations of the Fibonacci numbers.