Задача 61453

Темы:    [ Арифметика остатков (прочее) ] [ Индукция (прочее) ] [ Разложение на множители ]

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

Условие

Докажите, что при всех натуральных n число   f (n) = 2^2n–1 – 9n² + 21n – 14   делится на 27.

Решение 1

  2^2n–1 + 1 = 3(2^2n–2 – 2^2n–3 + 2^2n–4 – ... – 2 + 1) = 3(2^2n–3 + 2^2n–5 + ... + 2) + 3,  поэтому достаточно доказать, что
2^2n–3 + 2^2n–5 + ... + 2 ≡ 3n² – 7n + 2 ≡ 3n² + 2n + 2 (mod 9),  или что  (2^2n–3 + 1) + (2^2n–5 + 1) + ... + (2 + 1) ≡ 3n² + 3n + 3 (mod 9).
  Сокращая на 3, получим  (2^2n–4 – 2^2n–5 + ... + 1) + (2^2n–6 – 2^2n–7 + ... + 1) + ... + 1 ≡ n² + n + 1 ≡ (n – 1)² (mod 3).
  Заменив в левой части 2 на –1, получим  (2n – 3) + (2n – 5) + ... + 1 = (n – 1)².

Решение 2

  Индукция. База.  f(1) = 0.
  Шаг индукции. Достаточно проверить, что  f(n + 1) – 4f(n)  делится на 27. И действительно
2^2(n+1)–1 – 9(n + 1)² + 21(n + 1) – 14 – 4·2^2n–1 + 36n² – 84n + 56 = 27n² – 81n + 54 = 27(3n² – 3n + 2).

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

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	11
Название	Последовательности и ряды
Тема	Последовательности
параграф
Номер	1
Название	Конечные разности
Тема	Последовательности (прочее)
задача
Номер	11.026