Рассмотрим разность

27

Рассмотрим разность

Трудно найти сборник олимпидных или алгебраических задач, где не встречались бы задчи такого типа: доказать, что при любом натуральном n

a) $7^{2n} - 5^{2n}$ делится на 24;
b) $n^3 - n$ делится на 6;
c) $\frac{n^5 - 5n^3 + 4n}{120}$ целое число;
d) $3^{2n+3} + 40n - 27$ делится на 64;
e) $2^{2n-1} - 9n^2 + 21n - 14$ делится на 27;
f) $5^n(5^n + 1) - 6^n(3^n + 2^n)$ делится на 91;
g) $\frac{n^5}{5} + \frac{n^3}{3} + \frac{7n}{15}$ целое число.

Попробуйте порешить эти задачи. Верятно, у вас возникнут разные сообщения вроде следующих:
в задаче
a) воспользоваться тем, что $7^2 - 5^2 = 24$, и то жеством
$$a^n - b^n = (1) = (a - b)(a^{n-1} + a^{n-2}b + \ldots + b^{n-1})$$,
показывающим, что $a^n - b^n$ всегда делится на $a - b$;
b) разложить многочлен в числитель на пять множителей $(n-2)(n-1)n(n+1)(n+2)$ и заменить, что из пяты последовательных чисел найдется одно, делящейся на 3, одно — на 5, одно — на 4 и еще одно, делящейся на 2 (и не делящейся на 4);

e) представить разность как $(25^n - 18^n) - (12^n - 5^n)$ и как $(25^n - 12^n) - (18^n - 5^n)$, чтобы доказать ее делимость на 7 и на 13;
ж) доказать отделно делимость $5n^3 + 7n$ на 3 и делимость $3n^5 + 7n$ на 5.

Не умаляя красоты и полезности этих и других подобных расчудений, мы хотим разобраться один общий рецепт для всех таких задач.

Мы увидим, что справедливо каждого из утверждений a) — ж) достаточно проверить лишь для небольшого числа первых значений n (в задаче a) — для двух, г) — для трех и т. п.), чтобы быть уверенным в их справедливости при всех n.

А читатель, который разберется в заметке достаточно основательно, сможет сам составлять новые задачи в неограниченном количестве (причем даже такие, где встречаются irrationalные числа):

3. число $45^n + (-44)^n - 1$ делится на 1980;
   и) число $[(6 + \sqrt{31})^n] - 2^n + 1$ делится на 10; вообщее, если m, a, b — натуральные числа и b < 2a, то число $[(am + 1 + \sqrt{a^2m^2 + bm + 1})^n] - 2^n + 1$ делится на 2m (здесь [x] — целая часть числа x) *).

Сумма разностей

Прежде чем формулировать общие теоремы, продемонстрируем ход наших расчудений на примере d). Эта задача, а также следующее ниже следствие из теоремы 2 и lemma 1 составляют содержание задачи M629 из Заданияка «Кванта».

Рассмотрим разность значений данной функции
$$f(n) = 2^{2n-1} - 9n^2 + 21n - 14$$
в точках n+1 и n:
$$g(n) = f(n+1) - f(n) = 3 \cdot 2^{2n-1} - 18n + 12.$$
Мы хотим доказать, что $f(n)$ делится на 27 при всех n=1, 2,…

*)Эти две задачи прислали в прошлом году наших читателей B. Чучин из с. Вознесенское Хабаровского края и Вальтер Яноус из Инсбрука (Австрария).

29

Как придумать новую задачу?

Нет ничего проще. Подберем, например, $a, b$ и $c$ так, чтобы выражение $f(n) = an + b + c \cdot 9^n$ принадлежало (кале угодно!) целые значения при $n = -1$, $n = 0$ и $n = 1$. тогда по теореме 2 (при $k = 2$) число $f(n)$ будет целым при любом целом $n \geq -1$.

Возьем, скажем, $f(-1) = -1$, $f(0) = 0$, $f(1) = 4$. Решив систему

$$\begin{cases} -a + b + c/9 = -1, \\ b + c = 0, \\ a + b + 9c = 4. \end{cases}$$

мы найдем $a = \frac{5}{8}$, $b = -\frac{27}{64}$, $c = \frac{27}{64}$.

Именно так, возможно, и был придуман когда-то давно пример г). Советуем читателю в качестве отдельxa самому придумать несколько новых примеров.

Но наш путь еще не закончен: теорему хотелось бы обобщить так, чтобы она включала и примеры, где имеется несколько геометрических прогрессий.

Сумма прогрессий

Попробуйте доказать такой аналог наших теorem 1 и 2:

Теорема 3. Если $q_1, q_2, \dots, q_r$ – целые числа $u$
$f(n) = c_1 q_1^n + c_2 q_2^n + \dots + c_{r-1} q_{r-1}^n + c_r q_r^n$
— целое при $n = 1, 2, \dots, r$, то $f(n)$ – целое при любом натуральном $n$.
(Лемма 1 – частный случай теоремы при $r = 2, q_2 = 1$).

Указание. Для доказательства теоремы 3 полезно рассмотреть разность $g(n) = f(n+1) - q_r f(n)$. Поскольку $g(n) = c_1 (q_1 - q_r) q_1^n + \dots + c_{r-1} (q_{r-1} - q_r) q_{r-1}^n$ – сумма $r-1$ геометрических прогрессий и в условиях теоремы число $g(n)$ – целое при $1 \leq n \leq r-1$, доказать теорему можно индукцией по $r$: ведь
$$f(n) = g(n-1) + q_r g(n-2) + \\ + q_r^2 g(n-3) + \dots + q_r^{n-1} g(1) + q_r^n f(1).$$
(Tak, в задаче 3) можно рассмотреть разность $f(n+1) - 45f(n)$.

Упражнение 1. Проверьте примеры a), e) с помощью теоремы 3 и придумате к ней несколько новых примеров.

Мы надемемся, что пробудили у читателя страсть к обобщениям, и предлагаем ему следующее, более трудные упражнения:

2. Сформируйте и докажите аналоги теорем 1–3

a) для суммы $r$ прогрессий и многочлена степенки $k-1$;

6. для произведения прогрессии (с целым значениемелем) на многочлен.

Придумайте несколько примеров на применение ваших теорем.

3. Какую более общую теорему такого типа вы можете сформулировать?

4. Можно ли в условиях наших теорем уменшить число точек, в которых требуется проверка?

5. Докажите утверждение и и поставайте обобщение и и поставайте обобщение доказывается яснее и проще, чем частное. Прекрасная иллюстрация этому — следующее теорема, довольно громоздкая по формулировке, но обобщшая предыдущие и позволяющая ответить на все вопросы упражнения 2–5.

Теорема 4. Пусть выражение $f(n)$ является суммой $r$ многочленов, умноженных на некоторые геометрические прогрессии. Составим многочлен со старшим коэффициентом 1, корни которого — значенатели этих $r$ прогрессий, а кратность каждого корня на единицу больше степени соответствующего ему многочлена. (Степень $k$ этого характеристикого многочлена равна сумме количества $r$ прогрессий и степени всех многочленов, на которых они умножены.) Если (1) все коэффициенты характеристикого многочлена — целые числа и (2) значения $f(n)$ – целые при $n=1, 2, \dots, k$, где $k$ – степень характеристикого многочлена, то $f(n)$ будет целым и при всех натуральных $n>k$.

Разумеется, для выполнения условия (1) достаточно (но не обязательно), чтобы все значенные прогрессии были целыми числами. Какова роль коэффициентов характеристикого многочлена — ясно из следующего очевидного важной леммы, проверку которой мы оставляем читателю:

30

Лемма 2. Пусть
$$f(x) = B_1(x)q_1^x + B_2(x)q_2^x + \dots + B_r(x)q_r^x,$$
(3)
еде $B_i(x)$ — многочлен степени $k_i-1$ ($i=1, 2, \dots, r$), и
$$D(\lambda) = (\lambda-q_1)^{k_1}(\lambda-q_2)^{k_2} \dots (\lambda-q_r)^{k_r} = \lambda^k + d_1\lambda^{k-1} + d_2\lambda^{k-2} + \dots + d_{k-1}\lambda + d_k.$$
То еда при всех $x$ выполнен равенство:
$$f(x) + d_1f(x-1) + d_2f(x-2) + \dots + d_kf(x-k) = 0.$$

Теорема 4 следует отсюда сразу же: если все коэффициенты $d_1, \dots, d_k$ характеризуются многочлена $D(\lambda)$ — целые, то из равенства (3) вытекает, что $f(n)$ при каждом $n > k$ получается сложением целых значений $f(n-1), f(n-2), \dots, f(n-k)$, умноженных на фиксированные целые коэффициенты.

В качестве иллюстрации рассмотрим два режных примера.

д) Пусть $f(n) = \frac{1}{2} \cdot 4^n + (-9n^2 + 21n-14) \cdot 1^n$. Здесь $D(\lambda) = (\lambda-4)(\lambda-1)^3 = \lambda^4 - 7\lambda^3 + 15\lambda^2 - 13\lambda + 4$. Позному для всех $n$
$$f(n) = 7f(n-1) - 15f(n-2) + 13f(n-3) - 4f(n-4).$$

В частности, вслед за $f(1) = f(2) = f(3) = 0$ и $f(4) = 54$ идут $f(5) = 7 \cdot 54 = 378$, $f(6) = 7 \cdot 378 - 15 \cdot 54 = 1836, \dots$; естественно, все они будут делиться на 27 (далее на 54).

и) Пусть $f(n) = \frac{(6+\sqrt{31})^n}{10} + \frac{(6-\sqrt{31})^n}{10} - \frac{2^n}{10}$. Здесь коэффициенты многочлена $D(\lambda) = (\lambda^2 - 12\lambda + 5)(\lambda-2) = \lambda^3 - 14\lambda^2 + 19\lambda - 10$ — также целые. Вслед за первыми членами $f(0) = \frac{1}{10}, f(1) = 1, f(2) = 13$ все дальнейшие $f(n)$ определяютсяrekурентным соответствием
$$f(n) = 14f(n-1) - 19f(n-2) + 10f(n-3).$$

В частности, $f(3) = 14 \cdot 13 - 19 \cdot 1 + \frac{10}{10} = 124$ — целое, следовательно, будут целыми числами также все $f(n)$ при $n=4, 5, \dots$.

В качестве последнего упражнения предлагаем читателю разобраться в том, как с помощью леммы 2 можно доказать частиные случаи теоремы 4, о которых шла