А интересующее нас число e2n равно, очевидно, 2cn–1 (рис. 2д).
а) c1 = 1 |
б) a1 = 2 |
в) an+1 = 2an + 2cn |
г) cn+1 = an + 2cn |
д) e2n = 2cn–1 |
Рис. 2. а) |
Из A в C за два прыжка можно попасть только одним способом: c1 = 1. |
б) |
Из A в A за два прыжка можно попасть двумя способами: a1 = 2. |
в) |
В A можно попасть из C двумя способами и из A двумя способами: an+1 = 2an + 2cn. |
г) |
В C можно попасть из A одним способом и из C — двумя: cn+1 = an + 2cn. |
д) |
В E можно попасть из C двумя способами: e2n = 2cn–1. |
Как же найти явную формулу для an и cn? Запишем наше рекуррентное соотношение (7) так:
an+1 + cn+1√2 = (an + cn√2)(2 + √2) |
(8) |
и — как вы уже, конечно, догадались — ещё так:
an+1 – cn+1√2 = (an – cn√2)(2 – √2). |
(9) |
Отсюда по индукции, пользуясь (7), получаем:
an + cn√2 = (2 + √2)n–1(a1 + c1√2) = (2 + √2)n, |
an – cn√2 = (2 – √2)n–1(a1 – c1√2) = (2 – √2)n. |
Поэтому
cn = |
(2 + √2)n – (2 – √2)n 2√2 |
, |
а так как e2n = 2cn–1, получаем окончательно
e2n = |
(2 + √2)n–1 – (2 – √2)n–1 √2 |
, e2n–1 = 0. |
Задача решена. Неясно только, как в этой задаче (и в предыдущей задаче6) можно было додуматься до формул, содержащих ±√2, — ведь в задаче речь идёт о целых числах! (Для участников олимпиады и читателей «Кванта» задача7 была облегчена тем, что в формулировке указывался ответ — «Квант», 1979, №11, М595).
Однако «сопряжённые числа» возникли бы совершенно автоматически, если бы мы владели началами линейной алгебры (см.[12]), и применили стандартные правила этой науки к решению уравнений (7). Эти правила предлагают сначала выяснить, какие геометрические прогрессии (an = a0λn, cn = c0λn) удовлетворяют данному рекуррентному соотношению. Значения, для которых такие прогрессии существуют, — они называются характеристическими значениями или собственными числами — определяются из некоторого уравнения (оно тоже называется характеристическим). Для (7) характеристическое уравнение имеет вид λ2 – 4λ + 2 = 0, его корни — как раз 2 + √2 и 2 – √2. Зная эти корни, любое решение рекуррентного соотношения мы можем получить как «линейную комбинацию» соответствующих геометрических прогрессий ([11]). «Начальное условие» (в нашем случае a1 = 2, c1 = 1) определяет нужное нам решение однозначно.
Неудивительно, что даже самые простые рекуррентные целочисленные последовательности, для которых характеристическое уравнение — квадратное с целыми коэффициентами (примеры — те же (6) и (7) или последовательность Фибоначчи 1, 1, 2, 3, 5, 8, ..., Fn+1 = Fn + Fn–1; см.[9], [10]), выражаются, как функции номера, с помощью «сопряжённых» квадратичных иррациональностей.
Заметим, что большее характеристическое число определяет скорость роста последовательности: при больши́х n в задаче7 en (2 + √2)n/√2. Можно сказать это ещё так:
|
en+1 en |
= 2 + √2. |
Для задачи 6 аналогичное наблюдение:
|
xn yn |
= √2. |
Интересное продолжение этого факта мы увидим в следующей задаче с бо́льшим числом «сопряжённых» иррациональностей.
Поочерёдно меняем все знаки
8. Пусть
(1 + √2 + √3)n = qn + rn√2 + sn√3 + tn√6,
где qn, rn, sn и tn — целые числа. Найти пределы
|
rn qn |
, |
|
sn qn |
, |
|
tn qn |
. |
Конечно, мы здесь можем выразить (qn+1; rn+1; sn+1; tn+1) через (qn; rn; sn; tn), пользуясь тем, что
qn+1 + rn+1√2 + sn+1√3 + tn+1√6 = (1 + √2 + √3)(qn + rn√2 + sn√3 + tn√6),
но, наученные опытом, мы уже знаем, что более простые формулы получаются не для самих чисел qn, rn, sn, tn, a для некоторых их комбинаций. Одну такую комбинацию мы уже знаем: это
qn + rn√2 + sn√3 + tn√6 = (1 + √2 + √3)n.
Нетрудно сообразить, каковы будут другие. Рассмотрим вместе с данным числом
λ1 = 1 + √2 + √3,
ещё три «сопряжённых»:
λ2 = 1 – √2 + √3, λ3 = 1 + √2 – √3, λ4 = 1 – √2 – √3.
Тогда
qn – rn√2 + sn√3 – tn√6 = λ2n,
qn + rn√2 – sn√3 – tn√6 = λ3n,
qn – rn√2 – sn√3 + tn√6 = λ4n.
Мы можем выразить qn, rn, sn, tn через λ1, λ2, λ3, λ4:
qn = |
λ1n + λ2n + λ3n + λ4n 4 |
, |
sn = |
λ1n + λ2n – λ3n – λ4n 4√3 |
, | |
rn = |
λ1n – λ2n + λ3n – λ4n 4√2 |
, |
tn = |
λ1n – λ2n – λ3n + λ4n 4√6 |
. |
Теперь заметим, что λ1 > |λ2|, λ1 > |λ3|, λ1 > |λ4|. Поэтому
|
rn qn |
= |
|
1 – (λ2/λ1)n + (λ3/λ1)n – (λ4/λ1)n 1 + (λ2/λ1)n + (λ3/λ1)n + (λ4/λ1)n |
· |
1 √2 |
= |
1 √2 |
. |
Аналогично найдём, что
|
sn qn |
= |
1 √3 |
и |
|
tn qn |
= |
1 √6 |
. |
Мы говорили выше, что сопряжённые числа a ± b√d возникают часто как корни квадратного уравнения с целыми коэффициентами. В связи с последней задачей возникает такое желание:
9. Написать уравнение с целыми коэффициентами, один из корней которого равен 1 + √2 + √3.
Возникает подозрение, что вместе с этим числом λ1 уравнению с целыми коэффициентами удовлетворяют и сопряжённые, которые в решении предыдущей задачи мы обозначили λ2, λ3, λ4. Нужное уравнение можно записать так:
(x – λ1)(x – λ2)(x – λ3)(x – λ4) = 0;
то есть
(x – 1 – √2 – √3)(x – 1 + √2 – √3)× (x – 1 – √2 + √3)(x – 1 + √2 + √3) = 0;
после преобразований получаем
((x – 1)2 – 5 – 2√6)·((x – 1)2 – 5 + 2√6) = 0, (x2 – 2x – 4)2 – 24 = 0, x4 – 4x3 – 4x2 – 16x – 8 = 0.
Именно такое уравнение получилось бы в качестве характеристического, если бы мы применили упомянутую мелким шрифтом в конце предыдущего раздела общую теорию к исследованию линейного преобразования
(qn; rn; sn; tn) → (qn+1; rn+1; sn+1; tn+1)
в предыдущей задаче. Заметим, кроме того, что мы на самом деле получили уравнение наименьшей степени (с целыми коэффициентами) с корнем λ1 = 1 + √2 + √3. Попробуйте это доказать!
Алгебраическое послесловие
Мы разобрали несколько примеров, в которых затрагивались пограничные вопросы алгебры, математического анализа и теории чисел. (Каждому направлению, которое мы наметили, можно было бы посвятить более подробную статью в «Кванте»!) В заключение покажем ещё, как можно смотреть на основных героев статьи — «сопряжённые числа» — с чисто алгебраической точки зрения.
Предположим, что у нас есть множество P чисел (или выражений с буквами, или ещё каких-то элементов), с которыми можно выполнять четыре действия арифметики с соблюдением обычных арифметических правил. Такое множество называется полем; поля образуют, например, рациональные и действительные числа. Если в поле P не разрешимо, скажем, уравнение x2 – d = 0, то можно расширить его, рассматривая элементы вида p + q√d, где p, q P, a √d — новый символ, который при умножении сам на себя дает d, т.е. √d·√d = d, так что
(p + q√d)·(p' + q'√d) = (pp' + qq'd) + (pq' + qp')√d.
При d = –1 расширением поля вещественных чисел получаются комплексные числа.
В новом поле P1 — «квадратичном расширении» поля P — есть интересное отображение λ = p + q√d → λ = p – q√d (своеобразная «алгебраическая симметрия»), называемое сопряжением, с такими свойствами:
Все элементы старого поля P переходят в себя;
Все равенства, содержащие арифметические операции, при этом отображении сохраняются:
λ + μ = λ + μ; λ · μ = λ · μ; | (10) |
Это отображение является частным случаем так называемых автоморфизмов Галуа расширения P1 поля P.
В задачах 8 и 9 мы видели пример «двукратного» расширения — присоединения √2 и затем √3, — в результате которого получилось поле с бо́льшим количеством автоморфизмов Галуа: кроме тождественного отображения, их уже три
(√2 → –√2, √3 → √3;√2 → √2, √3 → –√3;√2 → –√2, √3 → –√3),
и их «взаимодействие» устроено так же, как во множестве самосовмещений прямоугольника.
Оказывается, к основному полю можно присоединять корни любого алгебраического уравнения. Автоморфизмы возникающего нового поля — предмет одной из красивейших ветвей алгебры XIX–XX века, теории Галуа, которая позволяет, в частности, исследовать вопрос о разрешимости уравнений в радикалах ([13], [14]).
Мы закончим эту статью набором задач, в основном продолжающих уже затронутые темы, но требующих иногда и новых соображений, и обещанным списком литературы.
Список литературы
1. Л.Курляндчик, А.Лисицкий. «Суммы и произведения» («Квант», 1978, №10). назад к тексту
2. Второе решение задачи М514 («Квант», 1979, №5, с.26). назад к тексту
3. Р.Нивен. «Числа рациональные и иррациональные» (М., «Мир», 1966). назад к тексту
4. Д.Фукс, М.Фукс. «О наилучших приближениях» («Квант», 1971, №6, №11) и «Рациональные приближения и трансцендентность» («Квант», 1973, №1). назад к тексту
5. Н.Васильев, В.Гутенмахер. «Прямые и кривые» (М., «Наука», 1978), с.103–105. назад к тексту
6. А.Н.Маркушевич. «Ряды» (М., «Наука», 1979). назад к тексту
7. Избранные задачи из журнала American Mathematical Monthly (М., «Мир», 1977), с.560–561. назад к тексту
8. Л.Курляндчик, Г.Розенблюм. «Метод бесконечного спуска» («Квант», 1978, №1). назад к тексту
9. В.Березин. «Филлотаксис и последовательность Фибоначчи», («Квант», 1979, №5, с.53). назад к тексту
10. Н.Н.Воробьев. «Числа Фибоначчи» (Популярные лекции по математике, вып.6) (М., «Наука», 1978). назад к тексту
11. А.И.Маркушевич. «Возвратные последовательности» (Популярные лекции но математике, вып.1) (М., «Наука», 1978). назад к тексту
12. Л.И.Головина. «Линейная алгебра и некоторые её приложения» (М., «Наука», 1979). назад к тексту
13. М.М.Постников. «Теория Галуа» (М., Физматгиз, 1963). назад к тексту
14. Ван-дер-Варден. «Алгебра» (М., «Наука», 1976). назад к тексту
Страницы: 1, 2