*Kenneth Edwards, Michael A. Allen**

open access article published in *The Fibonacci Quarterly* **58(5)**, 128–134 (2020)

**Abstract**

We consider the tiling of an *n*-board (an *n*×1 rectangular board) with third-squares (1/3×1 tiles with the shorter sides always aligned horizontally) and (1/3,2/3)-fence tiles. A (*w*,*g*)-fence tile is composed of two *w*×1 subtiles separated by a *g*×1 gap. We show that the number of ways to tile an *n*-board using these types of tiles equals *F*_{n+1}^{3} where *F*_{n} is the *n*th Fibonacci number. We use these tilings to devise straightforward combinatorial proofs of identities relating the Fibonacci numbers cubed to one another, to other combinations of Fibonacci numbers, and to the Pell numbers. Some of these identities appear to be new. We also show that for *p*=2,3,…, the number of ways to tile an *n*-board using either 1/*p*×1 tiles and (1/*p*,1−1/*p*)-fences or (1/2*p*,1/2−1/2*p*)- and (1/2*p*,1−1/2*p*)-fences is *F*_{n+1}^{p}.

**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. These combinatorial interpretations can be used to give quick intuitive proofs of identities instead of using algebra. A tiling which includes fractional length tiles and/or tiles with gaps, such as fence tiles, 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.

**Key results**

• Two new combinatorial interpretations of *F*_{n}^{p} for *p*=2,3,….

• A new method for enumerating metatiles of a given length.

• 7 new identities relating *F*_{n} to the Pell numbers *P*_{n} (where *P*_{n}=2*P*_{n−1}+*P*_{n−2}+δ_{n,1}, *P*_{n<1}=0). E.g.,

**Related publications**

[1] Sloane NJA (2010) *The Online Encyclopedia of Integer Sequences*, `oeis.org`.

[2] Benjamin AT, Quinn JJ (2003) *Proofs That Really Count: The Art of Combinatorial Proof*, Mathematical Association of America.

[3] Edwards K (2008/2009) A Pascal-like triangle related to the tribonacci numbers. *Fibonacci Quart* **46/47(1)**, 18–25.

[4] Edwards K, Allen MA (2019) A new combinatorial interpretation of the Fibonacci numbers squared. *Fibonacci Quart* **57(5)**, 48–53.

[5] Edwards K, Allen MA (2020) A new combinatorial interpretation of the Fibonacci numbers squared. Part II. *Fibonacci Quart* **58(2)**, 169–177.