Классическая задача по числам Фибоначчи. Обозначения: F0 = 0, F1 = 1, Fn+1 = Fn + Fn−1.
Задача (скорректированно по смыслу): доказать, что Fn делит сумму F_{n−2k} + F_{n+2k} при любом натуральном k и n, причём n < 2k.
Шаг 1. Приведём нужную формулу сложения для Фибоначчи
Для любых целых a, b справедлива формула
F_{a+b} = F_a F_{b+1} + F_{a-1} F_b.
Из неё выводим два выражения:
- для b = 2k: F_{n+2k} = F_n F_{2k+1} + F_{n-1} F_{2k},
- для b = −2k: используя аналогичную формулу (или применяя ту же самую идентичность к n−2k и m = 2k) получаем
F_{n-2k} = F_n F_{2k-1} − F_{n-1} F_{2k}.
Шаг 2. Складываем два выражения
F_{n+2k} + F_{n-2k}
= [F_n F_{2k+1} + F_{n-1} F_{2k}] + [F_n F_{2k-1} − F_{n-1} F_{2k}]
= F_n (F_{2k+1} + F_{2k-1}) + F_{n-1}(F_{2k} − F_{2k}).
Так как F_{2k} − F_{2k} = 0, остаётся
F_{n+2k} + F_{n-2k} = F_n (F_{2k+1} + F_{2k-1}).
Шаг 3. Введём числитель как член, делящийся на F_n
Число F_{2k+1} + F_{2k-1} называется числом Лукаса L_{2k}. Это целое число, потому что это линейная комбинация членов последовательности Фибоначчи.
Отсюда получаем
F_{n+2k} + F_{n-2k} = F_n · L_{2k},
то есть сумма F_{n+2k} и F_{n-2k} кратна F_n.
Вывод
Число F_n делит сумму F_{n-2k} + F_{n+2k} (при любых натуральных k, n, и даже при n < 2k, если понимать F_{n-2k} через отрицательные индексы по стандартной ассоциированной с ними формуле).
Замечание
Идея основывается на стандартном тождестве F_{n+m} + F_{n−m} = F_n L_m, где L_m — m-е число Лукаса (L_m = F_{m-1} + F_{m+1}). В приведённом доказательстве мы конкретно взяли m = 2k.
