Identities involving the tribonacci numbers squared via tiling with combs

Michael A. Allen*, Kenneth Edwards
Article published in The Fibonacci Quarterly 61(1), 21–27 (2023)

Abstract
The number of ways to tile an n-board (an n×1 rectangular board) with (1/2,1/2;1)-, (1/2,1/2;2)-, and (1/2,1/2;3)-combs is T_n+2² where T_n is the n-th tribonacci number. A (1/2,1/2;m)-comb is a tile composed of m sub-tiles of dimensions 1/2×1 (with the shorter sides always horizontal) separated by gaps of dimensions 1/2×1. We use such tilings to obtain quick combinatorial proofs of identities relating the tribonacci numbers squared to one another, to other combinations of tribonacci numbers, and to the Fibonacci, Narayana's cows, and Padovan numbers. Most of these identities appear to be new.

Background
Enumerating tilings of finite boards can give a physical picture of various integer sequences. For example, the number of ways to tile an n-board (a linear array of n square cells) with squares and dominoes is the Fibonacci number F_n+1 where F_n=F_n−1+F_n−2+δ_n,1, F_n<1=0, and δ_i,j is 1 if i=j and 0 otherwise. Likewise, T_n+2², where T_n=T_n−1+T_n−2+T_n−3+δ_n,2 and T_n<2=0, equals the number of ways to tile an n-board with half-squares (h), (1/2,1/2;2)-combs (f), and (1/2,1/2;3)-combs (c). Such combinatorial interpretations of integer sequences can be used to give quick intuitive proofs of identities rather than by using algebra.

A tiling which includes fractional length tiles and/or tiles with gaps, such as combs, can be reduced to a tiling using metatiles. A metatile is a grouping of tiles that exactly covers an integer number of cells and cannot be split into smaller metatiles. Evaluating the number of metatiles of a given length is the key to obtaining convolution-type identities via this class of combinatorial interpretation.

A metatile is said to be mixed if it contains more than one type of comb. The only metatiles which are not mixed are h², f², and c². We therefore just need to count the mixed metatiles. This is made easier by the fact that mixed metatiles occur in pairs: the other member of the pair is obtained by exchanging the two sub-tiles within each cell of the board. We then obtain recursion relations for the number of metatiles with a given ending σ which is a 2-digit string specifying the final two sub-tiles.

Key results
• 7 new identities relating T_n² and T_n. E.g., T_n+1T_n=∑_l=2ⁿ(T_l+T_l−2)T_n−l+2².
• A new identity relating T_n², T_n, and F_n².
• 2 new identities relating T_n², T_n, the Narayana's cows numbers (given by c_n=c_n−1+c_n−3+δ_n,0, c_n<0=0), and the Padovan numbers (given by p_n=p_n−2+p_n−3+δ_n,0, p_n<0=0).

Related resources
[1] Benjamin AT, Quinn JJ (2003) Proofs That Really Count: The Art of Combinatorial Proof, Mathematical Association of America.
[2] Allen MA, Edwards K (2022) Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices. Lin Multilin Alg doi: 10.1080/03081087.2022.2107979.
[3] Edwards K, Allen MA (2020) A new combinatorial interpretation of the Fibonacci numbers cubed. Fibonacci Quart 58(5), 128–134.