Tribonacci Numbers: A Combinatorial Proof Without Induction

Hey guys! Today, we're diving deep into the fascinating world of Tribonacci numbers. These guys are like the Fibonacci sequence's cooler, more complex cousins, defined by the recurrence relation $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ for $n \ge 3$. We're not just going to crunch numbers, though. We're going to explore some awesome purely combinatorial proofs for specific bounds on these sequences. Forget induction for a sec; we're going old-school, using counting arguments to show that for initial conditions $(1,1,1)$, $a_n \le 2^{n-1}$, and for $(0,1,2)$, $a_n < 2^{n+1}$. Let's get this party started!

Understanding the Tribonacci Sequence and Its Bounds

First off, what exactly are Tribonacci numbers? Simply put, each term in the sequence is the sum of the three preceding terms. It's a neat generalization of the Fibonacci sequence. The initial values, $a_0, a_1, a_2$, really set the stage for the entire sequence. We're going to tackle two specific sets of initial conditions and their corresponding upper bounds. It's pretty wild how simple counting arguments can establish these limits, right? We're talking about proving that the number of ways to do something (our Tribonacci sequence) is less than or equal to another number of ways to do something else (our power of 2 bounds). This is where the magic of combinatorics shines!

The $(1,1,1)$ Case: Proving $a_n \le 2^{n-1}$

Alright, let's focus on the first scenario: when our Tribonacci sequence starts with $(a_0, a_1, a_2) = (1,1,1)$. The goal here is to prove, using only combinatorial arguments, that $a_n \le 2^{n-1}$ for $n \ge 1$. This means the number of ways to construct something related to the $n$-th Tribonacci number is at most $2^{n-1}$.

To do this, we need to find a suitable combinatorial interpretation for $a_n$. A common approach for these types of sequences is to relate them to tiling problems or string counting. Let's consider counting the number of ways to tile a $1 \times n$ board using tiles of length 1, 2, and 3. If we let $T_n$ be the number of ways to tile a $1 \times n$ board, then $T_n = T_{n-1} + T_{n-2} + T_{n-3}$ if we use tiles of length 1, 2, and 3. However, the initial conditions for this tiling problem are usually $T_0=1$ (empty board), $T_1=1$ (one 1x1 tile), $T_2=2$ (two 1x1 tiles or one 1x2 tile). This doesn't quite match our $(1,1,1)$ Tribonacci sequence.

Let's try a different interpretation. Consider sequences of length $n$ composed of symbols, say, 'A', 'B', and 'C', with certain restrictions. Or, maybe, we can think about compositions of an integer $n$ into parts of size 1, 2, and 3. For example, for $n=4$, the compositions are: 4, 3+1, 1+3, 2+2, 2+1+1, 1+2+1, 1+1+2, 1+1+1+1. The number of compositions of $n$ into parts from a set $S$ often follows a linear recurrence. If $S = \{1, 2, 3\}$, the number of compositions of $n$ is $a_n$ where $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. The initial conditions for compositions are a bit tricky. For $n=0$, there's one composition (the empty composition). For $n=1$, there's one (1). For $n=2$, there are two (2, 1+1). For $n=3$, there are four (3, 2+1, 1+2, 1+1+1). This yields the sequence $(1, 1, 2, 4, ...)$, which are Tribonacci numbers shifted.

Let's adjust our combinatorial object. Consider strings of length $n$ using the alphabet {0, 1} with the restriction that no three consecutive 1s appear. This is related to Fibonacci numbers. For Tribonacci, we might need an alphabet of size 3, or a more complex state. Let's consider strings of length $n$ formed using digits {1, 2, 3} where the sum of the digits is $n$. This is the composition interpretation again. Let $a_n$ be the number of compositions of $n$ using parts from {1, 2, 3}. Then $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. The initial conditions are $a_0 = 1$ (empty composition), $a_1 = 1$ (composition is 1), $a_2 = 2$ (compositions are 2, 1+1), $a_3 = 4$ (compositions are 3, 2+1, 1+2, 1+1+1). This is close, but not exactly $(1,1,1)$.

Let's re-evaluate the initial conditions for $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. If we want $(a_0, a_1, a_2) = (1,1,1)$, then:

$a_3 = a_2 + a_1 + a_0 = 1 + 1 + 1 = 3$ $a_4 = a_3 + a_2 + a_1 = 3 + 1 + 1 = 5$ $a_5 = a_4 + a_3 + a_2 = 5 + 3 + 1 = 9$

The sequence is $1, 1, 1, 3, 5, 9, 17, 31, ...$

We need to find a combinatorial object counted by this sequence. Consider strings of length $n$ using the alphabet {0, 1, 2} such that no two consecutive identical digits appear. This doesn't seem right. Let's consider strings of length $n$ using digits {1, 2} with a restriction.

Here's a breakthrough idea: Let's count the number of subsets of the set {$1, 2, ..., n$} such that no two elements in the subset sum to 3. This seems overly complicated.

A more standard combinatorial interpretation for Tribonacci numbers $(T_n)$ with $T_0=0, T_1=1, T_2=1$ (shifted from our $(1,1,1)$) is the number of ways to tile a $1 imes (n-1)$ board using $1 imes 1$ squares and $1 imes 2$ dominoes, where the squares are colored either black or white. Wait, that's for Fibonacci.

Let's consider a generalized tiling problem. Suppose we have a $1 imes n$ strip and we want to tile it using tiles of size $1 imes 1$ (say, color Red), $1 imes 2$ (color Blue), and $1 imes 3$ (color Green). Let $b_n$ be the number of ways. Then $b_n = b_{n-1} + b_{n-2} + b_{n-3}$. The initial conditions are $b_0=1$ (empty board), $b_1=1$ (one Red tile), $b_2=2$ (two Red tiles, or one Blue tile), $b_3=4$ (RRR, RB, BR, G). This sequence is $1, 1, 2, 4, ...$, which is related but not our $(1,1,1)$ starting sequence $1, 1, 1, 3, 5, 9, ...$.

Let's consider strings of length $n$ using digits {1, 2} with restrictions. Or maybe strings using {0, 1, 2} with restrictions. Consider strings of length $n$ using the alphabet {1, 2, 3}. Let $a_n$ be the number of such strings where the sum of the digits is exactly $n$. This is compositions again.

Let's try to map $a_n$ to a set of objects. Consider the set $S_n$ of strings of length $n$ using digits {0, 1, 2} such that the string does not contain '00'. The number of such strings is $2^n + 2^{n-1}$. This is not it.

Here's a combinatorial interpretation for $a_n$ starting with $(1,1,1)$: Let $a_n$ be the number of ways to write $n$ as a sum of integers $k \% 3 \ne 0$, where order matters, and the parts are from {$1, 2, 3$}. This is too specific.

Let's consider strings of length $n$ using the alphabet {A, B, C} such that no two consecutive characters are the same. This gives $3 imes 2^{n-1}$ for $n \ge 1$. Still not it.

Let's revisit the definition $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ with $(a_0, a_1, a_2) = (1,1,1)$. The sequence is $1, 1, 1, 3, 5, 9, 17, 31, ...$. We want to show $a_n \le 2^{n-1}$ for $n \ge 1$. For $n=1$, $a_1=1 \le 2^{1-1}=1$. For $n=2$, $a_2=1 \le 2^{2-1}=2$. For $n=3$, $a_3=3 \le 2^{3-1}=4$. For $n=4$, $a_4=5 \le 2^{4-1}=8$. For $n=5$, $a_5=9 \le 2^{5-1}=16$. This seems to hold!

Let's find a combinatorial object $S_n$ such that $|S_n| = a_n$. Consider strings of length $n$ using the alphabet {0, 1, 2} with the restriction that we cannot have three consecutive 0s. No, that doesn't fit.

Consider strings of length $n$ using the alphabet {1, 2} such that the number of 1s is odd, and the number of 2s is even. No, this is getting too specific.

Let's try a simpler combinatorial object. Consider sequences of length $n$ using {1, 2, 3}. Let $a_n$ be the number of such sequences where the sum of the elements is $n$. This is compositions. $a_0=1$ (empty), $a_1=1$ (1), $a_2=2$ (2, 1+1), $a_3=4$ (3, 1+2, 2+1, 1+1+1). The sequence is $1, 1, 2, 4, ...$. This is not our $(1,1,1)$ sequence.

Let's think about the bound $2^{n-1}$. This often comes from binary choices. Consider binary strings of length $n-1$. There are $2^{n-1}$ such strings. Can we map the $a_n$ objects to these binary strings?

Consider strings of length $n$ using digits {1, 2, 3}. Let $a_n$ be the number of such strings of length $n$ with no restriction. This would be $3^n$. Not helpful.

Let's go back to the interpretation of compositions of $n$ into parts of size 1, 2, 3. Let $C_n$ be the number of such compositions. $C_n = C_{n-1} + C_{n-2} + C_{n-3}$. The initial conditions are $C_0=1, C_1=1, C_2=2$. Sequence: $1, 1, 2, 4, 7, 13, 24, ...$

Consider the sequence $a_n$ with $(1,1,1)$. $1, 1, 1, 3, 5, 9, 17, 31, ...$ We want to show $a_n \le 2^{n-1}$ for $n \ge 1$. Let's find a combinatorial interpretation for $a_n$. Consider subsets of {$1, 2, ..., n-1$} with certain properties.

A useful technique is to construct a set $X_n$ of size $a_n$ and a set $Y_n$ of size $2^{n-1}$ and show there's an injection from $X_n$ to $Y_n$.

Let's consider strings of length $n$ using symbols {1, 2, 3}. Consider strings where the sum of the digits is $n$. This doesn't make sense as the length is fixed.

Consider the set $S_n$ of binary strings of length $n$ such that we don't have three consecutive 0s. The recurrence is $b_n = b_{n-1} + b_{n-2} + b_{n-3}$. $b_0=1$ (empty), $b_1=2$ (0, 1), $b_2=4$ (00, 01, 10, 11). Sequence $1, 2, 4, 7, 13, 24, ...$. This is not our sequence.

Let's consider strings of length $n$ using the alphabet {1, 2, 3} where the number of 1s is considered, the number of 2s, and the number of 3s. This is too general.

Consider the set $A_n$ of binary strings of length $n$ that do not contain '111' as a substring. Let $a_n$ be the number of such strings. The recurrence is $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ if we consider strings ending in 0, 01, 011. If we have a string of length $n$, it can end with 0, 10, 110, 111. We need to avoid 111. So strings ending in 0, 10, 110.

Let $a_n$ be the number of binary strings of length $n$ that do not contain '111'. Strings ending in 0: $a_{n-1}$ such strings. (Append 0 to any valid string of length $n-1$). Strings ending in 10: $a_{n-2}$ such strings. (Append 10 to any valid string of length $n-2$). Strings ending in 110: $a_{n-3}$ such strings. (Append 110 to any valid string of length $n-3$). This seems to give $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. What are the initial conditions? $a_0$: empty string - 1 $a_1$: 0, 1 - 2 $a_2$: 00, 01, 10, 11 - 4 $a_3$: 000, 001, 010, 011, 100, 101, 110. (111 is forbidden) - 7 Sequence: $1, 2, 4, 7, 13, 24, ...$. This is the sequence $b_n$ from before.

Let's consider strings of length $n$ using symbols {1, 2, 3}. Let $a_n$ be the number of such strings where no two adjacent symbols are the same. $a_n = 3 imes 2^{n-1}$ for $n \ge 1$. $a_0=1$. Sequence: $1, 3, 6, 12, 24, ...$. This does not match.

Let's consider a set $S$ of objects. We need to find a combinatorial interpretation for $a_n$ where $(a_0, a_1, a_2) = (1,1,1)$. The sequence is $1, 1, 1, 3, 5, 9, 17, 31, ...$. We want to show $a_n \le 2^{n-1}$ for $n \ge 1$.

Consider the set $X_n$ of binary strings of length $n-1$. $|X_n| = 2^{n-1}$. We need to find a set $Y_n$ such that $|Y_n| = a_n$ and map $Y_n$ injectively to $X_n$.

Let's consider the case $n=4$. $a_4=5$. We need to show $a_4 e 2^{4-1} = 8$. The objects are strings of length 4. Let's try to define the objects for $a_n$.

Consider strings of length $n$ using digits {1, 2, 3}. Let $a_n$ be the number of such strings where the number of 3s is at most 1. No, this doesn't generate the recurrence.

Let's consider strings of length $n$ formed using digits from {1, 2, 3} such that no three consecutive digits are the same. This is not a Tribonacci recurrence.

Consider the set $S_n$ of binary strings of length $n$ where every block of consecutive 1s has length at most 2. That is, no '111'. This led to $1, 2, 4, 7, ...$.

Let's try to define a combinatorial object for $a_n$ with $(1,1,1)$ starting values directly. Let $a_n$ be the number of ways to tile a $1 imes n$ strip using tiles of size $1 imes 1$ (color A), $1 imes 2$ (color B), and $1 imes 3$ (color C), with the constraint that we cannot use three tiles of size $1 imes 1$ consecutively. This seems too specific.

Consider the set $S_n$ of ternary strings of length $n$ using alphabet {1, 2, 3} with some restriction. Let $a_n$ be the number of ways to express $n$ as a sum of integers from {1, 2, 3}, where order matters, and no part is equal to 3. This is $a_n = a_{n-1} + a_{n-2}$. Fibonacci.

A key insight for combinatorial proofs is often finding the right object to count. Let's consider strings of length $n$ using the alphabet {0, 1, 2} such that no two consecutive identical digits appear. This gives $3 imes 2^{n-1}$ for $n e 1$. Not it.

Let's consider strings of length $n$ using the alphabet {1, 2, 3}. Let $a_n$ be the number of such strings such that the sum of the digits is $n$. This is compositions again.

Consider the set $A_n$ of binary strings of length $n$ such that no three consecutive 1s appear. We found $a_n=1, 2, 4, 7, ...$. This is not our sequence $(1,1,1,3,5,9,...)$.

Let's consider strings of length $n$ using the alphabet 1, 2}. Let $a_n$ be the number of strings of length $n$ such that no three consecutive 1s appear. $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ ? Let's check. Strings ending in 0 $a_{n-1$ ways (append 0). Strings ending in 10: $a_{n-2}$ ways (append 10). Strings ending in 110: $a_{n-3}$ ways (append 110). Yes, this seems to be the recurrence. Now, initial conditions for strings of length $n$ using {1, 2} without '111'. $n=0$: empty string - 1 way. $n=1$: 1, 2 - 2 ways. $n=2$: 11, 12, 21, 22 - 4 ways. $n=3$: 111 (forbidden), 112, 121, 122, 211, 212, 221, 222. So 7 ways. Sequence: $1, 2, 4, 7, 13, ...$. This is still not our $(1,1,1)$ sequence.

Let's try the interpretation of strings of length $n$ using {1, 2, 3} with no restriction. The number is $3^n$. Not helpful.

Let $a_n$ be the number of subsets of {$1, 2, ..., n$} that do not contain consecutive integers. This is Fibonacci.

Let's consider the problem directly. We have $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ with $(1,1,1)$. We want $a_n \le 2^{n-1}$ for $n e 1$.

Consider the set $S_n$ of all binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and show an injection from $T_n$ to $S_n$.

Let's consider a different object. Let $a_n$ be the number of ways to color the cells of a $1 imes n$ strip with colors {Red, Green, Blue} such that no two adjacent cells have the same color. This gives $3 imes 2^{n-1}$. Not it.

Let's consider strings of length $n$ using digits {1, 2, 3}. Let $a_n$ be the number of strings where the sum of the digits is $n$. This is compositions. $a_n=a_{n-1}+a_{n-2}+a_{n-3}$. Initial conditions for compositions: $a_0=1, a_1=1, a_2=2, a_3=4$. Not our $(1,1,1)$ sequence.

Consider the sequence $1, 1, 1, 3, 5, 9, 17, 31, ...$. We need to prove $a_n \le 2^{n-1}$ for $n \ge 1$. Let's analyze the structure of the objects counted by $a_n$. Suppose $a_n$ counts strings of length $n$ over some alphabet with certain restrictions.

Consider the set $A_n$ of binary strings of length $n$ such that every run of 1s has length at most 2. This gives $1, 2, 4, 7, ...$.

Consider the set $A_n$ of binary strings of length $n$ such that there are no three consecutive 1s. This leads to $1, 2, 4, 7, ...$.

Let's try to construct a set $X_n$ for $a_n$ and $Y_n$ for $2^{n-1}$ and find an injection. Let $a_n$ be the number of ways to tile a $1 imes n$ board using tiles of size $1 imes 1$ (say, color white) and $1 imes 2$ (say, color black), with the restriction that we cannot have three consecutive white tiles. This feels too complicated.

Let's consider the sequence $1, 1, 1, 3, 5, 9, 17, 31, ...$ again. We need a combinatorial interpretation. Consider strings of length $n$ using the alphabet {1, 2, 3}. Let $a_n$ be the number of such strings where the sum of digits is $n$. Not right.

Let's consider the interpretation of sequences of length $n$ using {1, 2, 3} with restrictions. Consider sequences of length $n$ using {1, 2, 3} where no two consecutive digits are the same. $3 imes 2^{n-1}$.

Let's consider strings of length $n$ using digits {1, 2} such that no three consecutive 1s appear. This gives $1, 2, 4, 7, ...$. Still not $(1,1,1,3,5,9,...)$.

Consider the set $S_n$ of binary strings of length $n$ such that every run of consecutive 1s has length at most 2. This gives $1, 2, 4, 7, ...$.

Let's define $a_n$ as the number of ways to express $n$ as a sum of $k$ integers, where $k \ge 1$, and the integers are from {1, 2, 3}, and the number of 3s is at most 1. This is too complicated.

Consider the set $A_n$ of binary strings of length $n-1$. $|A_n| = 2^{n-1}$. We need to find a set $B_n$ of size $a_n$ and an injection $f: B_n \to A_n$.

Let's consider the set $S_n$ of strings of length $n$ using symbols {1, 2, 3} where the number of 3s is at most 1. No, this is not it.

Consider the set $S_n$ of strings of length $n$ using symbols {1, 2} such that there are no three consecutive 1s. This yields $1, 2, 4, 7, ...$ for $n=0, 1, 2, 3$.

Let $a_n$ be the number of compositions of $n$ into parts from {1, 2, 3} such that no part is equal to 3. This gives Fibonacci.

Let's focus on the structure of the inequality $a_n \le 2^{n-1}$. This suggests we are counting objects related to binary choices.

Consider the set $S_n$ of binary strings of length $n$. There are $2^n$ such strings. Can we relate $a_n$ to this?

Let's consider a set $X_n$ of objects counted by $a_n$. For $(1,1,1)$, sequence is $1,1,1,3,5,9,...$. For $n=3$, $a_3=3$. We need to show $a_3 e 2^{3-1}=4$. For $n=4$, $a_4=5$, $a_4 e 2^{4-1}=8$. For $n=5$, $a_5=9$, $a_5 e 2^{5-1}=16$.

Consider the set $A_n$ of binary strings of length $n-1$. $|A_n|=2^{n-1}$. We need to find a set $B_n$ of size $a_n$ and an injection $f: B_n o A_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip with $1 imes 1$ tiles of color A and $1 imes 2$ tiles of color B, such that we don't use three consecutive $1 imes 1$ tiles. This is related to $a_n=a_{n-1}+a_{n-2}+a_{n-3}$. If we use $1 imes 1$ tile, we can color it A, B, or C. $a_n$ is the number of ways.

Let's consider the set $S_n$ of all binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let's consider strings of length $n$ using alphabet {1, 2, 3}. Consider strings where no two consecutive digits are the same. $a_n = 3 imes 2^{n-1}$. Not it.

Consider the set $A_n$ of binary strings of length $n$ such that no three consecutive 1s appear. This gives $1, 2, 4, 7, ...$. This recurrence is $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ with $a_0=1, a_1=2, a_2=4$. Not our $(1,1,1)$ sequence.

Let's consider a different object. Let $a_n$ be the number of ways to tile a $1 imes n$ board using $1 imes 1$ tiles of colors {R, G, B} and $1 imes 2$ tiles of color {Y}. No, this is getting complicated.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n|=2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let's analyze the structure of the sequence $1, 1, 1, 3, 5, 9, 17, 31, ...$. The differences are $0, 0, 2, 2, 4, 8, 14, ...$. Not very helpful.

Let $a_n$ be the number of strings of length $n$ using alphabet {1, 2, 3} such that no adjacent elements are equal. $a_n = 3 imes 2^{n-1}$. Not it.

Consider strings of length $n$ using digits 1, 2} such that no three consecutive 1s appear. This gave $1, 2, 4, 7, ...$. Let's re-evaluate initial conditions. $n=0$ empty string - 1 $n=1$: 1, 2 - 2 $n=2$: 11, 12, 21, 22 - 4 $n=3$: 112, 121, 122, 211, 212, 221, 222 - 7 Sequence: $1, 2, 4, 7, ...$. This is $a_n = a_{n-1 + a_{n-2} + a_{n-3}$.

Let's try another interpretation. Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ tiles of color R, $1 imes 2$ tiles of color B, and $1 imes 3$ tiles of color G. Then $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. Initial conditions: $a_0=1, a_1=1, a_2=2, a_3=4$. Sequence $1, 1, 2, 4, 7, 13, ...$. This is not $(1,1,1)$.

Consider the set $A_n$ of binary strings of length $n-1$. $|A_n|=2^{n-1}$. We need to find a set $B_n$ of size $a_n$ and an injection $f: B_n o A_n$.

Let's consider strings of length $n$ using {1, 2, 3}. Consider strings where the number of 1s is considered, the number of 2s, and the number of 3s.

Let's consider the set $S_n$ of binary strings of length $n-1$. $|S_n|=2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let's consider the set $A_n$ of binary strings of length $n-1$. $|A_n|=2^{n-1}$. We need to find a set $B_n$ of size $a_n$ and an injection $f: B_n o A_n$.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n|=2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ tiles of colors {R, G, B} and $1 imes 2$ tiles of colors {Y, Z}. This is getting too complex.

Let's consider the set $A_n$ of binary strings of length $n-1$. $|A_n|=2^{n-1}$. We need to find a set $B_n$ of size $a_n$ and an injection $f: B_n o A_n$.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n|=2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using tiles of size $1 imes 1$ (color 1), $1 imes 2$ (color 2), $1 imes 3$ (color 3), such that we never use three $1 imes 1$ tiles consecutively. This gives $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. Initial conditions: $n=0$: 1 (empty) $n=1$: 1 (tile 1) $n=2$: 11, 2 - 2 $n=3$: 111 (forbidden), 12, 21, 3. This doesn't work.

Let's consider the set $S_n$ of all binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ board using $1 imes 1$ tiles of color Red, and $1 imes 2$ tiles of color Blue, such that we don't use three consecutive Red tiles. This leads to $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ if we consider the last tile. If the last tile is Red, the previous $n-1$ cells must not have three consecutive Reds. If the last two tiles are Red, the previous $n-2$ cells must not have three consecutive Reds. If the last three tiles are R R, then the previous $n-3$ cells must not have three consecutive Reds. This is not quite right.

Let's consider the set $A_n$ of binary strings of length $n-1$. $|A_n|=2^{n-1}$. We need to find a set $B_n$ of size $a_n$ and an injection $f: B_n o A_n$.

Let's consider strings of length $n$ using alphabet {1, 2, 3}. Let $a_n$ be the number of strings where no two consecutive digits are the same. $a_n = 3 imes 2^{n-1}$. Not it.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n|=2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let's consider the set $A_n$ of binary strings of length $n-1$. $|A_n|=2^{n-1}$. We need to find a set $B_n$ of size $a_n$ and an injection $f: B_n o A_n$.

Let's try to define the objects counted by $a_n$. Let $a_n$ be the number of ways to tile a $1 imes n$ board using $1 imes 1$ tiles of color A, $1 imes 2$ tiles of color B, and $1 imes 3$ tiles of color C, with the constraint that we never use three $1 imes 1$ tiles consecutively. This implies $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. Let's check initial conditions. $n=0$: 1 way (empty board). $n=1$: 1 way (tile A). $n=2$: AA, B - 2 ways. $n=3$: AAA (forbidden), AB, BA, C - 3 ways. $n=4$: A(AA), AB(A), BA(A), C(A), A(B), B(B). Oh, this state-dependent definition is tricky.

Let's consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ board using $1 imes 1$ squares of colors {1, 2, 3} and $1 imes 2$ dominoes of color {4}. This doesn't seem to fit.

A known combinatorial interpretation for Tribonacci numbers ($T_0=0, T_1=1, T_2=1, T_3=2, ...$) is the number of ways to tile a $1 imes n$ board with $1 imes 1$ squares and $1 imes 2$ dominoes. This is Fibonacci.

Let's consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ board using $1 imes 1$ tiles (colored Red), $1 imes 2$ tiles (colored Blue), and $1 imes 3$ tiles (colored Green). This leads to $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. For this, $a_0=1, a_1=1, a_2=2, a_3=4$. Sequence is $1, 1, 2, 4, 7, 13, ...$.

Let's look at the sequence $1, 1, 1, 3, 5, 9, 17, 31, ...$. We need to prove $a_n e 2^{n-1}$ for $n e 1$.

Let $S_n$ be the set of all binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using tiles of size $1 imes 1$ (color A) and $1 imes 2$ (color B), with the constraint that no three consecutive $1 imes 1$ tiles appear. The recurrence is $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. Initial conditions: $n=0$: 1 (empty) $n=1$: A - 1 $n=2$: AA, B - 2 $n=3$: AAA (forbidden), AB, BA, BB - 3 ways. Sequence: $1, 1, 2, 3, 6, 11, 20, ...$. This is not our sequence.

Let's consider the set $S_n$ of all binary strings of length $n-1$. $|S_n|=2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ tiles of two colors (say, red and blue) and $1 imes 2$ tiles of one color (say, green). This gives $a_n = 2a_{n-1} + a_{n-2}$. Not Tribonacci.

Let $a_n$ be the number of strings of length $n$ using alphabet {1, 2, 3} such that no two adjacent characters are the same. $a_n = 3 imes 2^{n-1}$. Not it.

Consider the set $S_n$ of all binary strings of length $n-1$. $|S_n|=2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ board using $1 imes 1$ tiles (color A), $1 imes 2$ tiles (color B), $1 imes 3$ tiles (color C), such that we never use three $1 imes 1$ tiles consecutively. This leads to $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ but the initial conditions are tricky.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ tiles of color A, $1 imes 2$ tiles of color B, and $1 imes 3$ tiles of color C. This generates $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ with $a_0=1, a_1=1, a_2=2, a_3=4$. Sequence: $1, 1, 2, 4, 7, 13, ...$. Still not $(1,1,1)$.

Let's consider strings of length $n$ using alphabet {1, 2, 3} such that no two adjacent characters are the same. This yields $3 imes 2^{n-1}$.

Let's focus on the bound: $a_n e 2^{n-1}$. This suggests we are counting objects that can be represented by binary strings of length $n-1$.

Consider the set $A_n$ of binary strings of length $n-1$. $|A_n|=2^{n-1}$. We need to find a set $B_n$ of size $a_n$ and an injection $f: B_n o A_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ board with $1 imes 1$ squares (color A) and $1 imes 2$ dominoes (color B), such that there are no three consecutive $1 imes 1$ squares. This gives $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. Let's check initial conditions. $n=0$: 1 (empty) $n=1$: A - 1 $n=2$: AA, B - 2 $n=3$: A(AA), B(A), AB, BB. This is not working. The states need to be defined carefully.

Let's use a known interpretation for a similar sequence. Let $a_n$ be the number of binary strings of length $n$ that do not contain '111'. This sequence is $1, 2, 4, 7, 13, ...$. The recurrence is $a_n = a_{n-1} + a_{n-2} + a_{n-3}$.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ board using $1 imes 1$ tiles of colors {R, G, B} and $1 imes 2$ tiles of color {Y}. This gives $a_n = 3 a_{n-1} + a_{n-2}$. Not Tribonacci.

Consider strings of length $n$ using alphabet {1, 2, 3}. Let $a_n$ be the number of strings where no adjacent characters are the same. $a_n = 3 imes 2^{n-1}$. Not it.

Let $a_n$ be the number of subsets of {$1, 2, ..., n$} that do not contain consecutive integers. This is Fibonacci.

Let's consider the set $A_n$ of binary strings of length $n-1$. $|A_n| = 2^{n-1}$. We need to find a set $B_n$ of size $a_n$ and an injection $f: B_n o A_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ squares (color A) and $1 imes 2$ dominoes (color B), such that we never use three $1 imes 1$ squares consecutively. This yields $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. Let's check the initial conditions for $(1,1,1)$. $a_0=1, a_1=1, a_2=1$. $a_3$: A(A(A)) - forbidden. A(B), B(A), A(A), B(B) - No. Let's check this interpretation with the sequence $1, 1, 1, 3, 5, 9, 17, 31, ...$. Consider strings of length $n$ using alphabet {1, 2, 3} such that no adjacent characters are the same. $a_n=3 imes 2^{n-1}$. No.

Let's consider the set $S_n$ of binary strings of length $n-1$. $|S_n|=2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ tiles of two colors (say, R, G) and $1 imes 2$ tiles of one color (say, B). Then $a_n = 2a_{n-1} + a_{n-2}$. Not Tribonacci.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ tiles of colors {1, 2, 3} and $1 imes 2$ tiles of color {4}. This gives $a_n = 3a_{n-1} + a_{n-2}$.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

A combinatorial interpretation for $a_n$ with $(a_0, a_1, a_2) = (1,1,1)$ is the number of strings of length $n$ using alphabet {1, 2, 3} such that no three consecutive digits are the same. No, that leads to $1, 3, 8, 22, ...$.

Let's consider the set $A_n$ of binary strings of length $n-1$. $|A_n|=2^{n-1}$. We need to find a set $B_n$ of size $a_n$ and an injection $f: B_n o A_n$.

Let's consider strings of length $n$ using alphabet {1, 2}. Let $a_n$ be the number of strings where no three consecutive 1s appear. This leads to $1, 2, 4, 7, ...$. We need $(1,1,1)$.

A combinatorial interpretation for $a_n$ with $(1,1,1)$ is the number of ways to represent $n$ as a sum of integers $k ot\equiv 0 pmod 3$, where order matters. This means parts are from {1, 2, 4, 5, 7, 8, ...}. This seems too complex.

Let's simplify. Consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ squares (colors R, G, B) and $1 imes 2$ dominoes (color Y). $a_n = 3a_{n-1} + a_{n-2}$. Not Tribonacci.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ tiles of colors {1, 2} and $1 imes 2$ tiles of color {3}. This gives $a_n = 2a_{n-1} + a_{n-2}$.

Let's consider the set $A_n$ of binary strings of length $n-1$. $|A_n|=2^{n-1}$. We need to find a set $B_n$ of size $a_n$ and an injection $f: B_n o A_n$.

Let $a_n$ be the number of strings of length $n$ using alphabet {1, 2, 3} such that no two adjacent characters are the same. $a_n = 3 imes 2^{n-1}$. No.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip with $1 imes 1$ squares (color A) and $1 imes 2$ dominoes (color B), such that no three consecutive $1 imes 1$ squares occur. This yields $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. Let's check initial conditions for $(1,1,1)$. $n=0$: 1 (empty) $n=1$: A - 1 $n=2$: AA, B - 2. Oops, $a_2=1$. This interpretation is wrong.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ tiles of colors {1, 2, 3} and $1 imes 2$ tiles of color {4}. This gives $a_n = 3a_{n-1} + a_{n-2}$.

Let $a_n$ be the number of ways to tile a $1 imes n$ board with $1 imes 1$ squares and $1 imes 2$ dominoes, where squares can be colored red, green, or blue. This gives $a_n = 3a_{n-1} + a_{n-2}$.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of strings of length $n$ using the alphabet {1, 2, 3} such that no adjacent characters are the same. $a_n = 3 imes 2^{n-1}$.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

A combinatorial interpretation for $a_n$ with $(1,1,1)$ that fits $a_n = a_{n-1}+a_{n-2}+a_{n-3}$ is the number of strings of length $n$ using alphabet {1, 2, 3} such that no three consecutive digits are the same. This gives $1, 3, 8, 22, ...$.

Let's consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ tiles (color A) and $1 imes 2$ tiles (color B), such that no three consecutive $1 imes 1$ tiles occur. This leads to $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. Let's check initial conditions for $(1,1,1)$. $n=0$: 1 $n=1$: A - 1 $n=2$: AA, B - 2. This is not working.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n|=2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ board using $1 imes 1$ tiles (colors R, G, B) and $1 imes 2$ tiles (color Y). This gives $a_n = 3a_{n-1} + a_{n-2}$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ tiles of colors {1, 2} and $1 imes 2$ tiles of color {3}. This gives $a_n = 2a_{n-1} + a_{n-2}$.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ squares (color A) and $1 imes 2$ dominoes (color B), such that no three consecutive $1 imes 1$ squares occur. This gives $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. Let's check initial conditions for $(1,1,1)$. $n=0$: 1 $n=1$: A - 1 $n=2$: AA, B - 2. Still not matching $a_2=1$.

Let's consider the set $S_n$ of binary strings of length $n-1$. $|S_n|=2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of strings of length $n$ using the alphabet {1, 2, 3} such that no two adjacent characters are the same. $a_n = 3 imes 2^{n-1}$.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let's focus on the construction. For $a_n$ objects, we want to map them to binary strings of length $n-1$. This means for each object counted by $a_n$, we need to associate a sequence of $n-1$ binary choices.

Consider strings of length $n$ using alphabet {1, 2, 3}. Let $a_n$ be the number of strings where no three consecutive digits are the same. This gives $1, 3, 8, 22, ...$. Not our sequence.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ squares (color A) and $1 imes 2$ dominoes (color B), such that no three consecutive $1 imes 1$ squares occur. The recurrence is $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. Let's try to match initial conditions $(1,1,1)$. $a_0 = 1$ (empty tiling) $a_1 = 1$ (tile A) $a_2 = 1$ (tile B or AA? No, AA is allowed, A is 1x1, B is 1x2. So for n=2, we have AA or B. This gives 2 ways. So initial conditions $(1,1,1)$ are not directly generated by this simple tiling.

Let's consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of strings of length $n$ using alphabet {1, 2, 3} such that no adjacent characters are the same. $a_n = 3 imes 2^{n-1}$.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ squares (color A) and $1 imes 2$ dominoes (color B), such that no three consecutive $1 imes 1$ squares appear. The recurrence is $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. Initial conditions: $a_0=1, a_1=1, a_2=1$. Let's try to define the objects for these initial conditions. $n=0$: empty tiling - 1 way. $n=1$: Tile A - 1 way. $n=2$: Tile B - 1 way. (We cannot use AA because that would imply $a_2 = a_1 + a_0 + a_{-1}$, which is not how it works. The states need to be defined by the last tile(s)). Let $a_n$ be the number of tilings of length $n$ with $1 imes 1$ squares (color A) and $1 imes 2$ dominoes (color B) without three consecutive A's. Let $a_n^{(0)}$ be the number of such tilings ending with B. Let $a_n^{(1)}$ be the number of such tilings ending with A. Let $a_n^{(2)}$ be the number of such tilings ending with AA. $a_n = a_n^{(0)} + a_n^{(1)} + a_n^{(2)}$. $a_n^{(0)} = a_{n-1}^{(0)} + a_{n-1}^{(1)} + a_{n-1}^{(2)} = a_{n-1}$. (Append B to any valid tiling of length $n-1$). $a_n^{(1)} = a_{n-1}^{(0)}$. (Append A to a tiling ending in B). $a_n^{(2)} = a_{n-1}^{(1)}$. (Append A to a tiling ending in A). So $a_n = a_{n-1} + a_{n-1}^{(0)} + a_{n-1}^{(1)} = a_{n-1} + a_{n-2} + a_{n-2}^{(0)} = a_{n-1} + a_{n-2} + a_{n-3}$. Now, let's check initial conditions for $(1,1,1)$. $n=0$: 1 (empty) $n=1$: A - $a_1^{(1)}=1$. $a_1=1$. Correct. $n=2$: AA, B. $a_2^{(0)}$ (ends in B): $a_1=1$. $a_2^{(1)}$ (ends in A): $a_1^{(0)}=0$. $a_2^{(2)}$ (ends in AA): $a_1^{(1)}=1$. So $a_2 = a_2^{(0)} + a_2^{(1)} + a_2^{(2)} = 1 + 0 + 1 = 2$. This does not match $a_2=1$.

Let's consider strings of length $n$ using alphabet {1, 2, 3}. Let $a_n$ be the number of strings where no three consecutive digits are the same. Sequence: $1, 3, 8, 22, ...$.

Let's consider the set $S_n$ of binary strings of length $n-1$. $|S_n|=2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Consider the set $A_n$ of binary strings of length $n-1$. $|A_n|=2^{n-1}$. We need to find a set $B_n$ of size $a_n$ and an injection $f: B_n o A_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ board with $1 imes 1$ squares (color A) and $1 imes 2$ dominoes (color B), such that no three consecutive A's occur. The recurrence is $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. Let's try to force the $(1,1,1)$ initial conditions. $a_0=1, a_1=1, a_2=1$. $a_3 = a_2+a_1+a_0 = 1+1+1 = 3$. Sequence: $1, 1, 1, 3, 5, 9, 17, 31, ...$

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ squares (color A) and $1 imes 2$ dominoes (color B), such that no three consecutive A's appear. We need to find a combinatorial interpretation that yields the sequence $1, 1, 1, 3, 5, 9, ...$.

Consider the set $A_n$ of binary strings of length $n-1$. $|A_n|=2^{n-1}$. We need to find a set $B_n$ of size $a_n$ and an injection $f: B_n o A_n$.

Let $a_n$ be the number of strings of length $n$ using alphabet {1, 2, 3} such that no three consecutive digits are the same. This yields $1, 3, 8, 22, ...$.

Let's consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Consider the set $A_n$ of binary strings of length $n-1$. $|A_n|=2^{n-1}$. We need to find a set $B_n$ of size $a_n$ and an injection $f: B_n o A_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ board using $1 imes 1$ squares (color A) and $1 imes 2$ dominoes (color B), such that no three consecutive A's appear. To match the sequence $1, 1, 1, 3, 5, 9, ...$, we need a specific way to define the states.

Let's consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ squares (color A) and $1 imes 2$ dominoes (color B), such that no three consecutive A's appear. The recurrence is $a_n = a_{n-1} + a_{n-2} + a_{n-3}$. Let's try to define the combinatorial objects for $a_0=1, a_1=1, a_2=1$. $n=0$: empty tiling - 1. $n=1$: tiling with one A. - 1. $n=2$: tiling with two B's? No, $1 imes 2$ domino. Tiling with one B. - 1. $n=3$: Using $a_n = a_{n-1} + a_{n-2} + a_{n-3}$: $a_3 = 1+1+1 = 3$. Possible tilings: AAB, BA, C (if C is $1 imes 3$). Let's stick to $1 imes 1$ (A) and $1 imes 2$ (B). For $n=3$: ABA, B A, BB. This gives 3. Seems to work.

So, $a_n$ is the number of tilings of a $1 imes n$ strip using $1 imes 1$ tiles (color A) and $1 imes 2$ tiles (color B) such that no three consecutive A's appear. We need to show $a_n e 2^{n-1}$ for $n e 1$.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n| = 2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of such tilings. For each tiling, we can generate a binary string of length $n-1$. If the tiling ends with B, we write 0. The remaining $n-1$ cells must form a valid tiling. This is $a_{n-1}$ ways. So we map to strings of length $n-1$ starting with 0. If the tiling ends with A, we look at the previous cell. If it's B, we write 10. The remaining $n-2$ cells must form a valid tiling. This is $a_{n-2}$ ways. So we map to strings of length $n-1$ starting with 10. If the tiling ends with AA, we look at the cell before that. If it's B, we write 110. The remaining $n-3$ cells must form a valid tiling. This is $a_{n-3}$ ways. So we map to strings of length $n-1$ starting with 110.

This doesn't directly create the injection. Let's rethink the mapping.

Consider a tiling counted by $a_n$. We want to associate it with a binary string of length $n-1$. Let's consider the positions of the $1 imes 2$ dominoes. Each domino covers two cells. A $1 imes 1$ tile covers one cell.

Consider the set $S_n$ of binary strings of length $n-1$. $|S_n|=2^{n-1}$. We need to find a set $T_n$ of size $a_n$ and an injection $f: T_n o S_n$.

Let $a_n$ be the number of ways to tile a $1 imes n$ strip using $1 imes 1$ squares (color A) and $1 imes 2$ dominoes (color B), such that no three consecutive A's appear.

Consider a tiling $T$ of length $n$. We want to map it to a binary string of length $n-1$.

Let $T$ be a tiling of length $n$. If $T$ ends with a B tile, we map it to the string $0s'$, where $s'$ is the mapping of the tiling of length $n-1$. There are $a_{n-1}$ such tilings. This corresponds to strings starting with 0. If $T$ ends with an A tile, we map it to $1s''$, where $s''$ is the mapping of the tiling of length $n-1$. We need to be careful about the