Задача 73773

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

Сложность: 5 Классы: 9,10,11

Условие

Автор: Шлейфер Р.

Для любого натурального числа n сумма     делится на 2^n–1. Докажите это.

Решение

  Обозначим нашу сумму через s_n. Будем вести индукцию по n.
  База.  s₁ = 1  делится на 2⁰,  s₂ = 2  делится на 2¹.
  Шаг индукции. Обозначим     и заметим, что    
Поскольку  aⁿ – bⁿ = (a^n–1 – b^n–1)(a + b) – ab(a^n–2 – b^n–2) = 2(a^n–1 – b^n–1) + 1972(a^n–2 – b^n–2),  то и  s_n = 2s_n–1 + 4·493s_n–2.
  По предположению индукции  s_n–1 кратно 2^n–2,  s_n–2 кратно 2^n–3;  значит,  s_n делится на 2^n–1.

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

журнал
Название	"Квант"
год
Год	1973
выпуск
Номер	12
Задача
Номер	М238