Трудно найти сборник олимпиадных или алгебраических задач, где не встречались бы задачи такого типа: доказать, что при любом натуральном $n$
- $7^{2n}-5^{2n}$ делится на 24;
- $n^3-n$ делится на 6;
- $\dfrac{n^5-5n^3+4n}{120}$ — целое число;
- $3^{2n+3}+40n-27$ делится на 64;
- $2^{2n-1}-9n^2+21n-14$ делится на 27;
- $5^n(5^n+1)-6^n(3^n+2^n)$ делится на 91;
- $\dfrac{n^5}5+\dfrac{n^3}3+\dfrac{7n}{15}$ — целое число.
Попробуйте порешать эти задачи. Вероятно, у вас возникнут разные соображения вроде следующих: в задаче
а) воспользоваться тем, $7^2-5^2=24$, и тождеством
$$
a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\ldots+b^{n-1}),\tag1
$$
показывающим, что $a^n-b^n$ всегда делится на $a-b$;
б) выделить три случая: $n=3k$, $n=3k+1$ и $n=3k+2$, соответствующие разным остаткам при делении $n$ на 3;
в) разложить многочлен в числителе на пять множителей $(n-2)(n-1)n(n+1)(n+2)$ и заметить, что из пяти последовательных чисел найдётся одно, делящееся на 3, одно — на 5, одно — на 4 и ещё одно, делящееся на 2 (и не делящееся на 4);
е) представить разность как $(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.
Не умаляя красоты и полезности этих и других подобных рассуждений, мы хотим разобрать один общий рецепт для всех таких задач. Мы увидим, что справедливость каждого из утверждений а)—ж) достаточно проверить лишь для небольшого числа первых значений $n$ (в задаче а) — для двух, г) — для трёх и т. п.), чтобы быть уверенным в их справедливости при всех $n$. А читатель, который разберётся в заметке достаточно основательно, сможет сам составлять новые задачи в неограниченном количестве (причём даже такие, где встречаются иррациональные числа):
- число $45^n+(-44)^n-1$ делится на 1980;
- число $[(6+\sqrt{31})^n]-2^n+1$ делится на 10; вообще, если $m$, $a$, $b$ — натуральные числа и $b\lt2a$, то число $[(am+1+\sqrt{a^2m^2+bm+1})^n]-2^n+1$ делится на $2m$ (здесь $[x]$ — целая часть числа $x$).
Сумма разностей
Прежде чем формулировать общие теоремы, продемонстрируем ход наших рассуждений на примере д). Эта задача, а также следующие ниже следствие из теоремы 2 и лемма 1 составляют содержание задачи М629 из Задачника «Кванта».
Рассмотрим разность значений данной функции
$$
f(n)=2^{2n-1}-9n^2+21n-14
$$
в точках $n+1$ и $n$:
$$
g(n)=f(n+1)-f(n)=3\cdot2^{2n-1}-18n+12.
$$
Мы хотим доказать, что $f(n)$ делится на 27 при всех $n=1$, 2, $\ldots$. Поскольку $f(n)$ можно представить как сумму разностей$$
\begin{gather*}
f(n)=(f(n)-f(n-1))+(f(n-1)-f(n-2))+\ldots+(f(2)-f(1))+f(1)=\\
=g(n-1)+g(n-2)+\ldots+g(1)+f(1)
\end{gather*}
$$
и число f(1)=0 делится на 27, нам достаточно доказать, что $g(n)$ делится на 27 при всех $n$.
Поступим так же с $g(n)$: рассмотрим разность
$$
h(n)=g(n+1)-g(n)=9\cdot2^{2n-1}-18
$$
и представим $g(n)$ как сумму $h(n-1)+h(n-2)+\ldots+h(1)+g(1)$. Поскольку $g(1)=0$, достаточно доказать, что $h(n)$ делится на 27 при всех $n$. Но это уже нетрудно: ведь $h(1)=0$, а при $n\ge2$ число $h(n)=2\cdot9(4^{n-1}-1)$ делится на $2\cdot9(4-1)$ согласно (1). Тем самым задача д) решена.
Нам помог здесь тот факт, что для многочлена $\phi(x)$ степени $s$ разность $\Delta\phi(x)=\phi(x+1)-\phi(x)$ — многочлен на единицу меньшей степени $s-1$, «вторая разность» $\Delta(\Delta\phi(x))=\Delta^2\phi(x)$ — многочлен степени $s-2$ и т. д., так что $s$-я разность $\Delta^s\phi(x)$ — просто число (многочлен степени 0). Отметим также полезную формулу для суммы разностей, которую мы применили дважды:
$$
\phi(n)=\textstyle\sum\limits_{1\le j\le n-1}\Delta\phi(j)+\phi(1).\tag2
$$
Многочлен плюс геометрическая прогрессия
Сформулируем теперь две общие теоремы, которые можно доказать тем же приёмом («рассмотрим разность»).
Теорема 1. Если число $b_0+b_1n+\ldots+b_{k-1}n^{k-1}$ — целое при $n=1$, $n=2$, $\ldots$, $n=k$, то оно целое при всех натуральных $n$. (Здесь $n_i$ — не обязательно целые!)
Теорема 2. Если число $q$ — целое и $$
f(n)=cq^n+b_0+b_1n+\ldots+b_{k-1}n^{k-1}
$$
— целое при $n=1$, $n=2$, $\ldots$, $n=k+1$, то $f(n)$ — целое при всех натуральных $n$.
Следствие. Если число $q$ — целое и число $f(n)$ делится на $m$ при $n=1$, $n=2$, $\ldots$, $n=k+1$, то $f(n)$ делится на $m$ при всех натуральных $n$.
(Конечно, аналогичное следствие можно сформулировать и для многочлена из теоремы 1.)
Чтобы вывести следствие, достаточно применить теорему 2 к выражению $\overline{f}(n)=\dfrac{f(n)}m$, у которого все коэффициенты поделены на $m$: условие «$f(n)$ делится на $m$» эквивалентно тому, что $$
\overline f(n)=\dfrac cmq^n+\dfrac{b_0}m+\dfrac{b_1}mn+\ldots+\dfrac{b_{k-1}}mn^{k-1}
$$
— целое число.
Например, для функции $f(n)$ из примера д) и $m=27$ можно применять теорему 2 к выражению
$$
\overline{f}(n)=\dfrac{f(n)}{27}=\dfrac1{54}4^n-\dfrac13n^2+\dfrac79n-\dfrac{14}{27}.
$$
Легко проверить, что $\overline f(1)=\overline f(2)=\overline f(3)=0$, $\overline f(4)=2$ и по теореме 2 число $\overline f(n)$ — целое (т. е. $f(n)$ делится на 27) при любом натуральном $n$.
Теперь перейдём к доказательству теоремы 2 (доказательство теоремы 1 мы оставляем читателям в качестве упражнения).
Пусть сначала $k=1$.
Лемма 1. Если $q$, $cq+b$ и $cq^2+b$ — целые числа, то $cq^n+b$ — целое при любом натуральном $n$.
В самом деле, рассмотрим разность
$$
(cq^{n+1}+b)-(cq^{n}+b)=cq^n(q-1)=q^{n-1}[(cq^2+b)-(cq+b)].
$$
Это число — целое, а потому, согласно (2), $cq^n+b$ — целое при любом натуральном $n$. (Можно рассуждать несколько иначе: рассмотреть разность $(cq^{n}+b)-(cq+b)$ и воспользоваться (1).)
Итак, при $k=1$ теорема 2 верна. Теперь точно так же, рассмотрев разности, можно доказать её для $k=2$, затем для $k=3$ и т. д. — индукцией по $k$. В самом деле,
если степень $k-1$ многочлена $b(n)=b_0+b_1n+\ldots+b_{k-1}n^{k-1}$ больше нуля, то разность
$$
g(n)=f(n+1)-f(n)=cq^{n+1}-cq^n+b(n+1)-b(n)=c(q-1)q^n+\Delta b(n)
$$
будет представляться как сумма геометрической прогрессии (с тем же знаменателем $q$) и многочлена, степень которого на единицу меньше, причём в условиях теоремы 2 числа $q$ и $g(n)$ при $1\le n\le k$ — целые, так что для $g(n)$ теорему 2 можно считать доказанной.
Замечание. Теорему 2 можно, очевидно, слегка обобщить: достаточно проверить, что в каких-то $k+1$ последовательных целых точках $n-0\le n\le n_0+k$ данное выражение принимает целые значения — тогда оно будет принимать целые значения при всех следующих $n$. Например, иногда удобно при проверке начинать с $n_0=0$ или $n_0=-1$.
Это замечание, как и доказанное выше следствие, относятся также к теореме 1 и ко всем обобщениям, о которых пойдёт речь ниже.
Как придумать новую задачу?
Нет ничего проще. Подберём, например, $a$, $b$ и $c$ так, чтобы выражение $f(n)=an+b+c\cdot9^n$ принимало (какие угодно!) целые значения при $n=-1$, $n=0$ и $n=1$. Тогда по теореме 2 (при $k=2$) число $f(n)$ будет целым при любом целом $n\ge-1$.
Возьмём, скажем, $f(-1)=-1$, $f(0)=0$, $f(1)=4$. Решив систему
$$
\left\{\begin{array}{l}
-a+b+\dfrac c9=-1,\\
b+c=0,\\
a+b+c=4,
\end{array}\right.
$$
мы найдём $a=\dfrac58$, $b=-\dfrac{27}{64}$, $c=\dfrac{27}{64}$. Именно так, возможно, и был придуман когда-то давно пример г). Советуем читателю в качестве отдыха самому придумать несколько новых примеров.
Но наш путь ещё не закончен: теорему хотелось бы обобщить так, чтобы она включала и примеры, где имеется несколько геометрических прогрессий.
Сумма прогрессий
Попробуйте доказать такой аналог наших теорем 1 и 2:
Теорема 3. Если $q_1$, $q_2$, $\ldots$, $q_r$ — целые числа и $$
f(n)=c_1q_1^n+c_2q_2^n+\ldots+c_{r-1}q_{r-1}^n+c_rq_r^n
$$
— целое при $n=1$, 2, $\ldots$, $r$, то $f(n)$ — целое при любом натуральном $n$. (Лемма 1 — частный случай этой теоремы при $r=2$, $q_2=1$.)
Указание. Для доказательства теоремы 3 полезно рассмотреть разность $g(n)=f(n+1)-q_rf(n)$. Поскольку
$$
g(n)=c_q(q_1-q_r)q_1^n+\ldots+c_{r-1}(q_{r-1}-q_r)q_{r-1}^n
$$
— сумма $r-1$ геометрических прогрессий и в условиях теоремы число $g(n)$ — целое при $1\le n\le r-1$, доказать теорему можно индукцией по $r$: ведь
$$
f(n)=g(n-1)+q_rg(n-2)+q_r^2g(n-3)+\ldots+q_r^{n-1}g(1)+q_r^nf(1).
$$
(Так, в задаче з) можно рассмотреть разность $f(n+1)-45f(n)$.)
Упражнение 1. Проверьте примеры а), е) с помощью теоремы 3 и придумайте к ней несколько новых примеров.
Мы надеемся, что пробудили у читателя страсть к обобщениям, и предлагаем ему следующие, более трудные упражнения:
Упражнение 2. Сформулируйте и докажите аналоги теорем 1—3
- для суммы $r$ прогрессий и многочлена степени $k-1$;
- для произведения прогрессии (с целым знаменателем) на многочлен.
Придумайте несколько примеров на применение ваших теорем.
Упражнение 3. Какую более общую теорему такого типа вы можете сформулировать?
Упражнение 4. Можно ли в условиях наших теорем уменьшить число точек, в которых требуется проверка?
Упражнение 5. Докажите утверждение и) и постарайтесь обобщить теорему 3 так, чтобы она годилась и для прогрессий с иррациональными знаменателями.
Указание. $[(6+\sqrt{31})^n]+1=(6+\sqrt{31})^n+(6-\sqrt{31})^n$, причём $y_1=6+\sqrt{31}$ и $y_2=6-\sqrt{31}$ — корни квадратного уравнения $y^2-12y+5=0$ с целыми коэффициентами.
Самая общая теорема
Найти естественное обобщение ряда фактов бывает интересно ещё потому, что очень часто более общее утверждение доказывается яснее и проще, чем частное. Прекрасная иллюстрация этому — следующая теорема, довольно громоздкая по формулировке, но обобщающая предыдущие и позволяющая ответить на все вопросы упражнений 2—5.
Теорема 4. Пусть выражение $f(n)$ является суммой $r$ многочленов, умноженных на некоторые геометрические прогрессии. Составим многочлен со старшим коэффициентом $1,$ корни которого — знаменатели этих $r$ прогрессий, а кратность каждого корня на единицу больше степени соответствующего ему многочлена. (Степень $k$ этого характеристического многочлена равна сумме количества $r$ прогрессий и степеней всех многочленов, на которые они умножены.) Если
- все коэффициенты характеристического многочлена — целые числа и
- значения $f(n)$ — целые при $n=1$, 2, $\ldots$, $k$, где $k$ — степень характеристического многочлена,
то $f(n)$ будет целым и при всех натуральных $n\gt k$.
Разумеется, для выполнения условия (1) достаточно (но не обязательно), чтобы все знаменатели прогрессий были целыми числами. Какова роль коэффициентов характеристического многочлена — ясно из следующей очень важной леммы, проверку которой мы оставляем читателю:
Лемма 2. Пусть
$$
f(x)=B_1(x)\,q_1^x+B_2(x)\,q_2^x+\ldots+B_r(x)\,q_r^x,\tag3
$$
где $B_i(x)$ — многочлен степени $k_i-1$ ($i=1$, 2, $\ldots$, $r$), и
$$
D(\lambda)=(\lambda-q_1)^{k_1}\,(\lambda-q_2)^{k_2}\ldots(\lambda-q_r)^{k_r}=
\lambda^k+d_1\lambda^{k-1}+d_2\lambda^{k-2}+\ldots+d_{k-1}\lambda+d_k.
$$
Тогда при всех $x$ выполнено равенство:
$$
f(x)+d_1f(x-1)+d_2f(x-2)+\ldots+d_kf(x-k)=0.\tag4
$$
Теорема 4 следует отсюда сразу же: если все коэффициенты $d_1$, $\ldots$, $d_k$ характеристического многочлена $D(\lambda)$ — целые, то из равенства (3) вытекает, что $f(n)$ при каждом $n\gt k$ получается сложением целых значений $f(n-1)$, $f(n-2)$, $\ldots$, $f(n-k)$, умноженных на фиксированные целые коэффициенты.
В качестве иллюстрации рассмотрим два прежних примера.
д) Пусть $f(n)=\dfrac12\cdot4^n+(-9n^2+21n-14)\cdot1^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\cdot54=378$, $f(6)=7\cdot378-15\cdot54=1836$, $\ldots$; естественно, все они будут делиться на 27 (даже на 54).
и) Пусть $f(n)=\dfrac{(6+\sqrt{31})^n}{10}+\dfrac{(6-\sqrt{31})^n}{10}-\dfrac{2^n}{10}$. Здесь коэффициенты многочлена
$$
D(\lambda)=(\lambda^2-12\lambda+5)(\lambda-2)=\lambda^3-14\lambda^2+19\lambda-10
$$
— также целые. Вслед за первыми членами $f(0)=\dfrac1{10}$ $f(1)=1$, $f(2)=13$ все дальнейшие $f(n)$ определяются рекуррентным соотношением
$$
f(n)=14f(n-1)-19f(n-2)+10f(n-3).
$$
В частности, $f(3)=14\cdot13-19\cdot1+\dfrac{10}{10}=124$ — целое, следовательно, будут целыми числами также все $f(n)$ при $n=4$, 5, $\ldots$.
В качестве последнего упражнения предлагаем читателю разобраться в том, как с помощью леммы 2 можно доказать частные случаи теоремы 4, о которых шла речь выше, и придумать новые упражнения (например, в качестве $q_1$, $q_2$, $q_3$ можно взять числа $2\cos\dfrac\pi7$, $2\cos\dfrac{2\pi}7$, $2\cos\dfrac{3\pi}7$; впрочем, убедиться, что это — корни члена с целыми коэффициентами, не так просто!).
Заканчивая наш рассказ, заметим, что для выяснения более глубоких вопросов делимости целых чисел наши теоремы не приносят большой пользы (например, чтобы доказать, что $n^{1693}-n$ при всех $n$ делится на 1981 или хотя бы на 6, требуется проверка в 1694 точках!).
Однако замечательный результат, который скрыт в лемме 2, относится по существу уже к совершенно другой, не менее интересной и важной теме: линейным рекуррентным уравнениям. Можно показать, что все последовательности $f(n)$, определяемые формулой (4) и любыми начальными членами $f(1)$, $\ldots$, $f(k)$, задаются формулой (3) (для того, чтобы этот результат сформулировать в естественной общности, нужно рассматривать не только вещественные, но и комплексные корни многочлена $D(\lambda)$). С выражениями (3) наши читатели, без сомнения, ещё встретятся, когда будут знакомиться с дифференциальными уравнениями: общий вид решений любого линейного дифференциального уравнения степени $k$
$$
y^{(k)}+d_1y^{(k-1)}+\ldots+d_{k-2}y''+d_{k-1}y'+d_ky=0
$$
имеет такую же форму (3).
