№ 13178

У плиточника $n$ одинаковых плиток размером $1\times 2$ фута. Он должен выложить дорожку шириной 2 фута и длиной $n$ футов. Докажите, что количество различных способов укладки дорожки равно $(n+1)$-му числу Фибоначчи. Способы считаются различными, если они отличаются порядком укладки плиток вдоль и поперёк дорожки; на рисунке показан один из возможных способов выложить дорожку длиной 5 футов.

Два первых числа Фибоначчи равны единице: $f_1=1$, $f_2=1$, а далее каждое число равно сумме двух предыдущих: $f_{n+1}=f_n+f_{n-1}$.