Найдите количество слов длины 10, состоящих только из букв  
 "а" и "б" и не содержащих в записи двух букв "б" подряд.  
   
 


			
Обозначим за an  
 количество слов длины n, состоящих только из букв  
 "а" и "б" и не содержащих в записи двух букв "б" подряд.  
 Таким образом, находим  
 a1=2, a2=3.  
 Покажем, что an можно выразить через  
 an-1 и an-2.  
 Количество слов длины n,  
 не содержащих в записи двух букв "б" подряд и начинающихся с  
 буквы "а", равно an-1, так как  
 после первой буквы может следовать любое слово длины n-1,  
 не содержащее двух "б" подряд.  
 Пусть слово длины n начинается с буквы "б".  
 Если в этом слове нет двух "б" подряд, то вторая буква - "а",  
 а далее может следовать любое слово длины n-2,  
 не содержащее двух "б" подряд.  
 Таким образом,  
 количество слов длины n,  
 не содержащих в записи двух букв "б" подряд и начинающихся с  
 буквы "б", равно an-2.  
 Тем самым, мы показали, что  
 an=an-1+an-2.  
 Теперь последовательно вычисляем  
 a3=a2+a1=3+2=5,  
 a4=a3+a2=5+3=8 и т.д.,  
 a10=a9+a8=144.
Заметим, что получающиеся числа an - это хорошо
известные числа Фибоначчи.
			
144
Числа Фибоначчи