$F_k|F_n$ dado $k | n$

Question

El problema: Dado $n, k \in \mathbb{N}$ tal que $k | n$ , demuestran que $F_k|F_n$ .

Mi intento: Tenemos que $F_n = |\tau_{n-1}|$ où $|\tau_{n-1}|$ representa el número de formas de embaldosar una fila de $n-1$ cuadrados utilizando dominós (que pueden cubrir dos cuadrados) y monominós (que pueden cubrir un cuadrado). Del mismo modo, $F_k = |\tau_{k-1}|$ . Entonces, como $k|n$ tenemos que $n = ak$ para algunos $a \in \mathbb{N}$ . Así que $$|\tau_{n-1}| = |\tau_{k-1}|\cdot|\tau_{n-k}| = |\tau_{k-1}|\cdot |\tau_{(a-1)k}| = |\tau_{k-1}|\cdot|\tau_k|^{a-1},$$ donde la última igualdad se obtiene de la regla del producto. Entonces esto demuestra que $|\tau_{k-1}|$ divide $|\tau_{n-1}|$ y así $F_k$ divide $F_n$ .

Pregunta: ¿Es correcto este planteamiento o me he equivocado en alguna parte? Gracias.

Answer 1

Una pista: ¡Te estás acercando! Su fórmula para $\tau_{n-1}$ es incorrecto, ya que no tiene en cuenta los mosaicos en los que una ficha de dominó cubre los cuadrados numerados $k-1$ y $k$ . Entonces, ¿cuántos de esos tilings te has perdido? Sumando el número de inclinaciones que faltan se obtiene la fórmula correcta: $$ \tau_{n-1}=\tau_{k-1}\tau_{n-k}+\underline{\hspace{2cm}} $$ y se puede utilizar la fórmula corregida para demostrar que $F_{n}$ es un múltiplo de $F_{k}$ .

Una pista más, si la necesitas:

Comience con el caso especial $n=2k$ entonces $n=3k$ hasta que el patrón de la prueba esté claro.