On Linear Recurrence Equations Arising from Compositions of Positive Integers

摘要

For an arithmetic function f0, we define a new arithmetic function f1, generalizing the linear recurrence for the numbers of compositions of positive integers. Using f1 in the same way, we then define f2, and so on. We establish some patterns related to the sequence f1, f2, ... . Our investigations depend on the following result: if f0 satisfies a linear recurrence equation of order k, then each function fm will also satisfy a linear recurrence equation of the same order. In several results, we derive a recurrence equation for fm(n) in terms of m and n. For each result, we give a combinatorial meaning for fm(n) in terms of the number of restricted words over a finite alphabet. We also find new combinatorial interpretations of the Fibonacci polynomials, as well as the Chebyshev polynomials of the second kind.