женьшень+12

Читая Alice"s Adventures in Wonderland(Lewis Carroll ,1862),отмечаешь,что все зверушки,с которыми общалась Алиса были очень обидчивы।Немудрено,что, когда Алиса, чтобы понравиться Белому Кролику,решила рассказать ему Историю Чисел Фибоначчи,Белый КРОЛИК так разозлился,что пригрозил ей никогда с ней не шутить,ЕСЛИ она не придумает другой способ получения Чисел Фибоначчи।("Алиса,ты должна понимать,что кролики живут не вечно и-и-и это очень обидно, что математики пренебрегают такими фактами,когда устремляют что-то к бесконечности...")। Алису(в ней тогда было росту два дюйма-5 сантиметров) так утомила истерика Кролика,что она решила(дело было в лесу) поспать под любым грибом,чтобы не промокнуть от дождя।Первым попавшимся оказался Мухомор।Проснувшись, она уже знала,как задобрить Кролика।Вот её многогранные мухоморные тру-ля-мысли.Имеется полоска клетчатой бумаги шириной в одну клетку и длиной в n клеток।На первой клетке установлена шашка।Одним ходом шашку можно продвигать вперед на одну или две клетки।Сколько существует способов продвижения шашки на n-ю клетку?Будем называть способ продвижения маршрутом и обозначим число маршрутов с 1-й на n-ю клетку u(n).При небольших n значения u(n) вычисляются непосредственно:u(1)=1: единственный маршрут-оставаться на месте.u(2)=1:единственный маршрут-ход на одну клетку.u(3)=2:один маршрут-ход на две клетки и еще один-два хода на одну клетку.u(4)=3:если ход обозначить буквой О(одна клетка) или Т(две клетки),то имеем маршруты ООО,ОТ,ТО।Легко убедиться,что u(5)=5.Финальные мысли।Поскольку множества маршрутов,ведущих на n-ю клетку и приводящих предпоследним ходом на (n-1)-ю и (n-2) клетки,не пересекаются,имеем u(n)=u(n-1)+u(n-2)।Да при этом u(1)=u(2)=1 ,да кроме того,первые значения в совокупности выглядят очень знакомо: 1,1,2,3,5,॥ । Таким образом, приходим к выводу: когда в тебе два дюйма роста,спать под Мухомором опасно-будешь много знать и скоро состаришься.Белый Кролик остался очень доволен Alice,но посчитал нужным сказать:"Когда Я буду рассказывать эту поучительную историю ГЕРЦОГИНЕ ,для доказательства использую Метод Полной Математической Индукции..."