Demostrar que el número de formas de recubrir una cuadrícula rectangular de $1\times n$ con cuadrados y dominós es igual a $F_{n+1}$, donde $n\geq1$

Question

Aquí $F_n$ se refiere a los números de Fibonacci. Conozco la definición de los números de Fibonacci y varias relaciones de recurrencia que satisfacen, pero no estoy seguro de cómo probar esta afirmación.

Answer 1

Has descrito correctamente los primeros dos casos.

Sea $a_n$ el número de teselados admisibles de un rectángulo de $1 \times n$. Has encontrado que $a_1 = 1$ y $a_2 = 2$. Si $n > 2$, observa que debemos colocar primero un cuadrado o un rectángulo. Si colocamos un cuadrado primero, hay $a_{n - 1}$ formas admisibles de completar los $n - 1$ espacios restantes. Si colocamos un dominó primero, hay $a_{n - 2}$ formas admisibles de completar los $n - 2$ espacios restantes. Dado que estos dos escenarios son mutuamente excluyentes y exhaustivos, tenemos la relación de recurrencia $$a_n = a_{n - 1} + a_{n - 2}$$ y las condiciones iniciales \begin{align*} a_1 & = 1\\ a_2 & = 2 \end{align*} Observa que esta es la relación de recurrencia para la secuencia de Fibonacci, pero los términos iniciales son $a_1 = F_2 = 1$ y $a_2 = F_3 = 2$, por lo que $a_n = F_{n + 1}$.