Решение

  Обозначим нашу сумму через 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.

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