Задача 31251

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

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

Условие

Доказать, что  2^2n–1 + 3n + 4  делится на 9 при любом n.

Решение 1

  2^2n–1 + 3n + 4 = (2^2n–1 + 1) + 3n + 3 = 3(2^2n–2 – 2^2n–3 + ... – 2 + 1 + n + 1),  а
2^2n–2 – 2^2n–3 + ... – 2 + 1 + n + 1 ≡ (–1)^2n–2 – (–1)^2n–3 + ... – (–1) + 1 + n + 1 = 3n (mod 3),  то есть делится на 3.

Решение 2

  Индукция по n. База.  2¹ + 3 + 4 = 9.
  Шаг индукции.  2^2(n+1)–1 + 3(n + 1) + 4 = 4·2^2n–1 + 3n + 7 = 4(2^2n–1 + 3n + 4) – 9n – 9,  а выражение в скобках делится на 9 по предположению индукции.

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

книга
Автор	Иванов С.В.
Название	Математический кружок
глава
Номер	11
Название	Остатки
Тема	Деление с остатком
задача
Номер	21