  An interesting characterization of the Fibonacci numbers is that, if we write
them as $F_1 = 1$, $F_2 = 2$, $F_3 = 3$, $F_4 = 5, ...$, then every positive
integer can be written uniquely as a sum of non-adjacent Fibonacci numbers.
This is now known as Zeckendorf's theorem [21], and similar decompositions
exist for many other sequences ${G_{n+1} = c_1 G_{n} + ... + c_L G_{n+1-L}}$
arising from recurrence relations. Much more is known. Using continued fraction
approaches, Lekkerkerker [15] proved the average number of summands needed for
integers in $[G_n, G_{n+1})$ is on the order of $C_{{\rm Lek}} n$ for a
non-zero constant; this was improved by others to show the number of summands
has Gaussian fluctuations about this mean.
  Kolo$\breve{{\rm g}}$lu, Kopp, Miller and Wang [17, 18] recently recast the
problem combinatorially, reproving and generalizing these results. We use this
new perspective to investigate the distribution of gaps between summands. We
explore the average behavior over all $m \in [G_n, G_{n+1})$ for special
choices of the $c_i$'s. Specifically, we study the case where each $c_i \in
{0,1}$ and there is a $g$ such that there are always exactly $g-1$ zeros
between two non-zero $c_i$'s; note this includes the Fibonacci, Tribonacci and
many other important special cases. We prove there are no gaps of length less
than $g$, and the probability of a gap of length $j > g$ decays geometrically,
with the decay ratio equal to the largest root of the recurrence relation.
These methods are combinatorial and apply to related problems; we end with a
discussion of similar results for far-difference (i.e., signed) decompositions.
