  Zeckendorf's Theorem states that any positive integer can be uniquely
decomposed into a sum of distinct, non-adjacent Fibonacci numbers. There are
many generalizations, including results on existence of decompositions using
only even indexed Fibonacci numbers. We extend these further and prove that
similar results hold when only using indices in a given arithmetic progression.
As part of our proofs, we generate a range of new recurrences for the Fibonacci
numbers that are of interest in their own right.
