Задача 107984

Темы:    [ Рекуррентные соотношения (прочее) ] [ Делимость чисел. Общие свойства ] [ Индукция (прочее) ] [ Арифметическая прогрессия ]

Сложность: 4 Классы: 8,9,10

Условие

Автор: Конягин С.В.

Найдите x₁₀₀₀, если  x₁ = 4,  x₂ = 6,  и при любом натуральном  n ≥ 3  x_n – наименьшее составное число, большее   2x_n–1 – x_n–2.

Решение

  Докажем по индукции, что  x_n = ½ n(n + 3).
  База. При  n = 3, 4  формула верна:  2x₂ – x₁ = 8,  то есть  x₃ = 9;  2x₃ – x₂ = 12,  то есть  x₄ = 14.
  Шаг индукции.  2x_n – x_n–1 = 2·½ n(n + 3) – ½ (n – 1)(n + 2) = ½ (n + 1)(n + 4) – 1.  По условию, x_n+1 – первое составное число, большее чем
½ (n + 1)(n + 4) – 1.  Но число  ½ (n + 1)(n + 4)  – составное. Действительно, если n нечётно, то  ½ (n + 1)(n + 4) = (n + 4)·½ (n + 1).  Каждый из сомножителей – целое число, большее 2. Аналогично рассматривается случай чётного n. Итак,  x_n+1 = ½ (n + 1)(n + 4).
  Подставляя  n = 1000 , получаем  x₁₀₀₀ = 500·1003.

Ответ

501500.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	56
Год	1993
вариант
Класс	9
задача
Номер	2