комбинаторика - Задача с домино

Это задача на числа Фибоначчи. Пусть $%a_n$% -- количество способов замощения прямоугольника $%2\times n$%. Тогда $%a_1=1$%, $%a_2=2$%. При $%n > 2$% рассмотрим крайний слева столбец высоты $%2$%. Там либо лежит доминошка (вертикально), и тогда оставшуюся часть можно замостить $%a_{n-1}$% способами, либо две доминошки слева лежат горизонтально, и тогда оставшийся прямоугольник заполняется $%a_{n-2}$% способами. Поэтому $%a_n=a_{n-1}+a_{n-2}$%. По указанным рекуррентным формулам находим $%a_8$%.