Последовательность Фибоначчи.

Чи́сла Фибона́ччи — элементы последовательности
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …
или
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, … (последовательность A000045 в OEIS),
в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи).
Более формально, последовательность чисел Фибоначчи задаётся линейным рекуррентным соотношением.
Иногда числа Фибоначчи рассматривают и для отрицательных значений, как двусторонне бесконечную последовательность, удовлетворяющую тому же рекуррентному соотношению. При этом члены с отрицательными индексами легко получить с помощью эквивалентной формулы «назад».
Последовательность Фибоначчи была хорошо известна в древней Индии, где она применялась в метрических науках (просодии, другими словами — стихосложении) намного раньше, чем стала известна в Европе.
Образец длиной n может быть построен путём добавления S к образцу длиной n-1, либо L к образцу длиной n-2; и просодицисты показали, что число образцов длиною n является суммой двух предыдущих чисел в последовательности. Дональд Кнут рассматривает этот эффект в книге «Искусство программирования».
На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Liber Abaci» (1202). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, предполагая, что: изначально есть новорожденная пара кроликов (самец и самка); со второго месяца после своего рождения кролики начинают спариваться и каждый месяц производить новую пару кроликов; кролики никогда не умирают. Сколько пар кроликов будет через год?
В начале первого месяца есть только одна новорожденная пара.
В конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся
В конце второго месяца первая пара рождает новую пару и опять спаривается
В конце третьего месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара только спаривается
В конце четвёртого месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается
В конце n-го месяца количество пар кроликов будет равно количеству пар в предыдущем месяце плюс количество новорожденных пар, которых будет столько же, сколько пар было два месяца назад.