|
|
 |
Условие
Докажите, что при n > 1 число 11 + 3³ + ... + (2n – 1)2n – 1 делится на 2n, но не делится на 2n+1.
Решение
Лемма 1. k2n ≡ 1 (mod 2n+2) для каждого нечётного числа k.
Доказательство. k2n – 1 = (k – 1)(k + 1)(k² + 1)(k4 + 1)...(k2n–1 + 1) – произведение n + 1 чётных множителей. Вдобавок один из первых двух множителей делится на 4.
Лемма 2. (k + 2n)k ≡ kk(1 + 2n) (mod 2n+2) при n > 1.
Доказательство. а все слагаемые, кроме двух первых, делятся на 2n+2.
Вернёмся к решению задачи. Обозначим сумму из условия через Sn, а разность Sn+1 – Sn через Rn. Будем вести индукцию по n.
База (n = 2) очевидна.
Шаг индукции. Sn+1 = Sn + Rn. Rn есть сумма 2n–1 слагаемых вида mm, где m = 2n + k, k – нечётное число, меньшее 2n. По лемме 1
mm ≡ mk (mod 2n+2). Поэтому
Rn ≡ (1 + 2n) + (3 + 2n)³ + (5 + 2n)5 + ... (mod 2n+2).
По лемме 2 Rn ≡ Sn(1 + 2n) (mod 2n+2). Значит, Sn+1 ≡ 2Sn(1 + 2n–1) (mod 2n+2).
По предположению индукции Sn делится на
2n (значит, Sn+1 делится на 2n+1) и не делится на 2n+1 (значит, Sn+1 не делится на 2n+2).
Замечания
1. См. также задачу М2252 из Задачника "Кванта" ("Квант", 2012, №1).
2. 7 баллов.
