# Lucas numbers count hi-hat patterns

My friend Molly is a drummer, and posed the following question: in rock music the hihat is usually struck on every eighth-note of a measure, either open or closed, with an open hit typically never followed by another open hit. Given measures containing $m$ eighth notes, how many possible patterns are there?

That is, what is the number $d_m$ of patterns of length $m$ on the alphabet $\{x,o\}$ such that no two o’s appear consecutively? Note that we consider the first and last letters of a give pattern to be consecutive occurrences, since beat patterns usually/often repeat.

Here’s how Molly and I solved this. Let $w$ be a valid pattern of length $m$. We have the following cases: (1) $w = xo\ldots x$, (2) $w = xx\ldots o$, (3) $w=xx\ldots x$, (4) $w = ox\ldots x$, or (5) $w = xo \ldots o$. Note that these cases are mutually exclusive.

In cases (1-3), removing the initial x gives you a valid pattern of length $m-1$. Moreover, from any valid pattern of length $m-1$, you can add an x to the beginning to get a valid pattern of length $m$, so these account for $d_{m-1}$ patterns of length $m$.

In cases (4-5), removing the initial two letters gives a valid pattern of length $m-2$.  Moreover, any valid pattern of length $m-2$ either ends in x, in which cases adding ox gives a pattern of type (4), or in o, in which case adding xo gives a pattern of type (5). Thus, these contribute $d_{m-2}$ many patterns to $d_m$.

This shows that $d_m = d_{m-1} + d_{m-2}$, with $d_1 = 1$ and $d_2 = 3$ (these initial conditions can be verified by hand.)

That looks familiar…..

…..and it is! This is the defining recurrence of the Lucas numbers!