  A \Def{composition} of a positive integer $n$ is a $k$-tuple $(\l_1, \l_2,
\dots, \l_k) \in \Z_{> 0}^k$ such that $n = \l_1 + \l_2 + \dots + \l_k$. Our
goal is to enumerate those compositions whose parts $\l_1, \l_2, \dots, \l_k$
avoid a fixed arithmetic sequence. When this sequence is given by the even
integers (i.e., all parts of the compositions must be odd), it is well known
that the number of compositions is given by the Fibonacci sequence. A much more
recent theorem says that when the parts are required to avoid all multiples of
a given integer $k$, the resulting compositions are counted by a sequence given
by a Fibonacci-type recursion of depth $k$. We extend this result to arbitrary
arithmetic sequences. Our main tool is a lemma on generating functions which is
no secret among experts but deserves to be more widely known.
