Tribonacci Numbers and Tiling Counts

The Fibonacci sequence answers "how many ways can I climb $n$ stairs taking 1 or 2 steps at a time?" — each count is the sum of the two before it. The Tribonacci sequence answers the same question when you're also allowed to take 3 steps at once: each term is the sum of the three preceding terms, $T_n = T_{n-1} + T_{n-2} + T_{n-3}$, because your last move onto stair $n$ was a step of size 1, 2, or 3, landing you from stair $n-1$, $n-2$, or $n-3$ respectively.

With seeds $T_0 = 0$, $T_1 = 1$, $T_2 = 1$, the sequence runs $0, 1, 1, 2, 4, 7, 13, 24, 44, \ldots$. Check $T_6 = T_5 + T_4 + T_3 = 13 + 7 + 4 = 24$ — matching the table.

The same recursion counts tilings: the number of ways to tile a $1 \times n$ strip using tiles of length 1, 2, and 3 follows exactly this rule, since the last tile placed has one of those three lengths. Interview variants dress this up as step-counting, tiling, or "how many binary strings of length $n$ avoid three consecutive identical digits" — all reduce to the same three-term recursion once you identify what the "last move" could have been.