Задача
COM-B1-M10-P014 Докажите рекурсию для домино
#14
★★★☆☆ Уровень 3 из 5
Докажите, что число замощений доски \(2\times n\) домино удовлетворяет \(a_n=a_{n-1}+a_{n-2}\).
Посмотрите, как покрыта правая верхняя клетка.
Если правая верхняя клетка покрыта вертикальным домино, то весь последний столбец закрыт, и остается \(2\times(n-1)\): \(a_{n-1}\) способов. Если она покрыта горизонтальным домино, то правая нижняя клетка тоже должна быть покрыта горизонтальным домино из предпоследнего столбца, и остаются \(2\times(n-2)\): \(a_{n-2}\) способов. Иных вариантов нет, случаи не пересекаются. Значит \(a_n=a_{n-1}+a_{n-2}\).
Формальное доказательство стандартной рекурсии.