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 eighth notes, how many possible patterns are there?
That is, what is the number of patterns of length on the alphabet 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 be a valid pattern of length . We have the following cases: (1) , (2) , (3) , (4) , or (5) . Note that these cases are mutually exclusive.
In cases (1-3), removing the initial x gives you a valid pattern of length . Moreover, from any valid pattern of length , you can add an x to the beginning to get a valid pattern of length , so these account for patterns of length .
In cases (4-5), removing the initial two letters gives a valid pattern of length . Moreover, any valid pattern of length 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 many patterns to .
This shows that , with and (these initial conditions can be verified by hand.)
That looks familiar…..
…..and it is! This is the defining recurrence of the Lucas numbers!