Коды и шифры

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

Будем следовать обозначениям, введенным в М5. Элементы этой последовательности порождаются линейной рекуррентой

U₍_n+₁₎ = 2U_n + U₍_n_-1).

Для доказательства делимости на 5 каждого третьего элемента последовательности заметим, что, согласно рекуррентной формуле,

U_n = 2U₍_n_-1) + U₍_n_-2),

поэтому, подставляя выражение для U_n в выражение для U₍_n₊₁₎, получаем:

U₍_n+₁₎ = 5U₍_n_-1) + 2U₍_n_-2).

И если U_n_-2 делится на 5, то отсюда следует, что U₍_n₊₁₎ также должно делиться на 5. Так как элемент U₀ (который равен 0) делится на 5, то на 5 делятся также элементы U₃, U₆ и т.д.

Теперь рассмотрим утверждение о том, что отношение соседних элементов последовательности стремится к значению (1+2). Как и раньше, будем предполагать, что общий член последовательности U_n можно представить в виде:

Применив рекуррентную формулу и начальные условия U_n = 0 и U₁ = 1, получаем: для того, чтобы общий член последовательности был представим в указанном виде, необходимо, чтобы  и  являлись корнями квадратного уравнения

X² - 2X - 1 = 0,

причем B = -A, откуда получаем значения

 = (1+2),  = (1-2) и A =(1/22).

Отношение соседних элементов последовательности довольно быстро сходится к значению , так как  по абсолютной величине меньше единицы и поэтому значения его степеней довольно быстро убывают. Поскольку  = (1+2), то утверждение доказано.

Содержание