For an arithmetic function f₀, we define a new arithmetic function f₁, generalizing the linear recurrence for the numbers of compositions of positive integers. Using f₁ in the same way, we then define f₂, and so on.

We establish some patterns related to the sequence f₁, f₂, ... . Our investigations depend on the following result: if f₀ satisfies a linear recurrence equation of order k, then each function f_m will also satisfy a linear recurrence equation of the same order.

In several results, we derive a recurrence equation for f_m(n) in terms of m and n. For each result, we give a combinatorial meaning for f_m(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.