Задача 78251

Темы:    [ Числа Фибоначчи ] [ Индукция (прочее) ] [ Деление с остатком ]

Сложность: 3+ Классы: 10,11

Условие

Дана последовательность чисел F₁, F₂, ...;  F₁ = F₂ = 1  и   F_n+2 = F_n + F_n+1.  Доказать, что F_5k делится на 5 при  k = 1, 2, ... .

Решение 1

  Индукция по k. База: F₅ = 5.
  Шаг индукции.  F_5k+2 ≡ F_5k+1 (mod F_5k),  F_5k+3 ≡ 2F_5k+2 (mod F_5k),  F_5k+4 ≡ 3F_5k+1 (mod F_5k),  F_5k+5 ≡ 5F_5k+1 (mod F_5k).  По предположению индукции F_5k делится на 5. Значит, и F_5k+5 делится на 5.

Решение 2

  См. задачу 60570 г).

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	24
Год	1961
вариант
	1
Класс	10
Тур	1
задача
Номер	1