The sum of Fibonacci numbers, i.e. the sequence 2, 4, 7, 12, 20, 33, 54, 88, … has many combinatorial interpretations.  For instance, the n-th term in this sequence is the number of length-n binary strings that avoid 001.  In this talk, I will describe a related (but to my knowledge, new) interpretation: given a length-3 binary string—called the keyword—we say two length-n binary strings are equivalent if one can be obtained from the other by some sequence of substitutions: each substitution replaces an instance of the keyword with its negation, or vice versa.  It turns out that the number of induced equivalence classes is again the n-th term in the aforementioned sequence.  What makes this result surprising is that it does not depend on the keyword, despite the fact that the sizes of the equivalence classes do.  If the keyword has length m, then we instead use the sum of (m-1)-step Fibonacci numbers.  This is joint work with undergraduates (present and past): Blan Morrison, Patrick Revilla, Mason Rogers, Arianna Serafini, Anav Sood.

Speaker’s website: https://www.ewbates.com/