Числа Фибоначчи

Последовательность Фибоначчи была хорошо известна в древней Индии, где она применялась в метрических науках(просодии, другими словами — стихосложении) намного раньше, чем стала известна в Европе.

Образец длиной n может быть построен путём добавления S к образцу длиной n-1, либо L к образцу длиной n-2; и просодицисты показали, что число образцов длиною n является суммой двух предыдущих чисел в последовательности. Дональд Кнут рассматривает этот эффект в книге «Искусство программирования».

На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Liber Abaci» (1202). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, предполагая, что: изначально есть новорожденная пара кроликов (самец и самка); со второго месяца после своего рождения кролики начинают спариваться и каждый месяц производить новую пару кроликов; кролики никогда не умирают. Сколько пар кроликов будет через год?

• В начале первого месяца есть только одна новорожденная пара (1).
• В конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся (1)
• В конце второго месяца первая пара рождает новую пару и опять спаривается (2)
• В конце третьего месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара только спаривается (3)
• В конце четвёртого месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается (5)

В конце {\displaystyle n}-го месяца количество пар кроликов будет равно количеству пар в предыдущем месяце плюс количество новорожденных пар, которых будет столько же, сколько пар было два месяца назад. Таким образом: {\displaystyle F_{n}=F_{n-2}+F_{n-1}.}