Похожие
Текст
ЛГопцлярные лекции
ПО МАТЕМАТИКЕ
А.И.МАРКУШЕВИЧ
ВОЗВРАТНЫЕ
1 ПОСЛЕДОВАТЕЛЬНОСТИ
ГОСУ- • ;ЕННОЕ ИЗДАТЕЛЬСТВО
ТЕХНИКО-ТЕОРЕТИЧЕСКОЙ ЛИТЕРАТУРЫ
195O
тктмил
ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ
А. И. МАРКУШЕВИЧ
ВОЗВРАТНЫЕ
ПОСЛЕДОВАТЕЛЬНОСТИ
ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО
ТЕХНИКО-ТЕОРЕТИЧЕСКОЙ ЛИТЕРАТУРЫ
МОСКВА 1950 ЛЕНИНГРАД
ПРЕДИСЛОВИЕ
В этой брошюре содержится расширенное изложение лек-
лекции, читанной автором для школьников !Х и X классов —
участников Московской математической олимпиады, а затем —
в несколько изменённом виде — в Московском институте усо-
усовершенствования учителей.
Тема «Возвратные последовательности» близка к школь-
школьному курсу (арифметические и геометрические прогрессии,
последовательность квадратов натуральных чисел, последо-
последовательности коэффициентов частного многочленов, располо-
расположенных по возрастающим степеням, и т. п.). Вместе с тем
это настоящая маленькая математическая теория*), закон-
законченная, простая, ясная, как и всё то, что вышло из рук круп-
крупнейших мастеров математического анализа, создавших эту
теорию.
Основы теории возвратных последовательностей были раз-
разработаны и опубликованы в двадцатых годах восемнадцатого
века французским математиком Муавром [имя которого носит
формула: (cos a-{-/sin a)" = cos/гг-}-/'sin ш] и [одним из
первых по времени членов Петербургской Академии наук
швейцарским математиком Даниилом Бернулли. Развёрнутую
теорию дал крупнейший математик восемнадцатого века петер-
петербургский академик Леонард Эйлер, посвятивший возвратным
*) Для искушённого в математическом анализе читателя мы ука-
укажем, что это точный аналог теории линейных дифференциальных
уравнений с постоянными коэффициентами.
последовательностям (рядам) тринадцатую главу своего «Вве-
«Введения в анализ бесконечно-малых» A748)*). Из более позд-
поздних работ следует выдглить изложение теории возвратных
последовательностей в курсах исчисления конечных разностей,
читанных знаменитыми русскими математиками академиками
П. Л. Чебышевым и А. А Марковым **).
*) См. русский перэвод пзрвэго тома этого труда, написанного
Эйлером иа латинском язакз: Л. Эйлер, Введэаие в анализ беско-
бесконечно-малых, т. I, M. — Л., 1936, сгр. 197—218.
**) См. П. Л. Чебышев, Теория вероятностей, лекции 1879 —
1830 гг., М.—Л., 1936, сгр. 13)—147; А. А. Марков, Исчисление
конечных разностей, 2-е изд., Одесса, 1910, стр. 209—239.
1. Понятие возвратной последовательности является широ-
широким обобщением понятия арифметической или геометрической
прогрессии. Как частные случаи оно охватывает также последо-
последовательности квадратов или кубов натуральных чисел, после-
последовательности цифр десятичного разложения рационального
числа (и вообще любые пгриодическне последовательности),
последовательности коэффициентов частного от деления двух
многочленов, расположенных по возрастающим степеням х,
и т. д. Отсюда видно, что с возвратными последовательно-
последовательностями в курсе математики средней школы приходится встре-
встречаться весьма часто. Теория возвратных последовательностей
составляет особую главу математической дисциплины, называ-
называемой исчислением конечных разностей- Мы изложим здесь
эту теорию, не требуя от читателя каких-либо предваритель-
предварительных специальных сведений (лишь в одном месте мы сошлёмся
без доказательства на общее предложение, устанавливаемое
в теории линейных алгебраических уравнений).
2. Будем записывать последовательности в виде
аг, иг, и3, . . . , ulV . . . , A)
или, коротко, {«„}. Если существует натуральное число k и
числа а,, а2, ... , ak (действительные или мнимые), такие,
что, начиная с некоторого номера п и для всех следующих
номеров,
"n+ft=aiMn+ft-i + <VW-2+- ••+«*",. Xn^m^l), B)
то последовательность A) называется возвратной последова-
последовательностью порядка k, а соотношение B) — возвратным
уравнением порядка k.
Таким образом, возвратная последовательность характери-
характеризуется тем, что каждый член её (начиная с некоторого из
них) выражается через одно и то же количество k непосред-
непосредственно предшествующих ему членов по формуле B). Самое
название «возвратная» (а также рекуррентная, от французского
recurrente — возвращающаяся к- началу) употребляется именно
потому, что здесь для вычисления последующего члена воз-
возвращаются к предшествующим членам. Приведём несколько
примеров возвратных последовательностей.
Пример 1. Геометрическая прогрессия. Пусть
имеем геометрическую прогрессию:
и1 = а, u2 — aq, :us = ag2, ... ,уп = ад"-\ ...;) C)
для неё уравнение B) принимает вид:
un+i = 4ttn- D)
Здесь ?—1 и ax~q. Таким образом геометрическая про-
прогрессия является возвратной последовательностью первого
порядка.
Пример 2. Арифметическая прогрессия. В слу-
случае арифметической прогрессии
и1 = а, u2 = a-Ard, us = aAr2d, . . . , ип = а-\-(п— \)d,. ..
имеем:
— соотношение, не имеющее вида уравнения B)*). Однако,
если мы рассмотрим два соотношения, написанные для двух
соседних значений п:
то получим из них, путём почленного вычитания:
или
— уравнение вида B). Здесь k = 2, at = 2, а2 = —1. Сле-
Следовательно, арифметическая прогрессия является возвратной
последовательностью второго порядка.
*) Для последнего характерно то, что в правую часть его вхо-
входят одни только члены последовательности с постоянными коэффи-
циевтами при них.
Пример 3. Рассмотрим старинную задачу Фибоначчи*)
о числе кроликов. В ней требуется определить число пар зре-
зрелых кроликов, образовавшихся от одной пары в течение года,
если известно, что каждая зрелая пара кроликов- ежемесячно
рождает новую пару, причём новорождённые достигают пол-
полной зрелости в течение месяца. В этой задаче интересен отнюдь
не результат, получить который совсем нетрудно, но последо-
последовательность, члены которой выражают общее число зрелых
пар кроликов в начальный момент (м^, через месяц (м2), через
два месяца (м3) и, вообще, через п месяцев (и„-ц). Очевидно,
что «1=1. Через месяц прибавится пара новорождённых, но
число зрелых пар будет прежнее: и„=1. Через два месяца
крольчата достигнут зрелости и общее число зрелых пар будет
равно двум:-«3=2. Пусть мы вычислили уже количество зре-
зрелых пар через п—1 месяцев — ип и через п месяцев — мк+ь
Так как к этому времени ип ранее имевшихся зрелых пар
дадут ещё ип пар приплода, то через п-\-\ месяцев общее
число зрелых пар будет:
Отсюда
ui = Us-\-u2 = 3, и5 = «44-и3 = 5, us = иъ -{- ui = 8,
Мы получили таким образом последовательность
«1=1, «2=1> «3-"-=2> «4=3> \ G)
в которой каждый последующий член равен сумме двух пре-
предыдущих. Последовательность эта называется последователь-
последовательностью Фибоначчи, а члены её — числами Фибоначчи. Урав-
Уравнение F) показывает, что последовательность Фибоначчи есть
возвратная последовательность второго порядка.
Пример 4. В качестве следующего примера рассмотрим
последовательность квадратов натуральных чисел:
и, = 12, и2 = 22, к3 = 33, ..., йп=«2, ... (8)
*) Фибоначчи, или Леонардо Пизанский, — итальянский средне-
средневековый математик (около 1200 г.)—оставил после себя книгу «Об
абаке>; (Liber abaci), содержащую обширные арифметические и алге-
алгебраические сведения, заимствованные у народов Средней Азии и ви-
византийцев и творчески им переработанные и развитые.
Здесь ип+1 = (п-\- \J—п2-\-2п-\-\ и, следовательно,
«я+1 = «я + 2я+1-
Увеличивая п на единицу, получим:
«„+2 = «„+1 + 2« + 3-
И, следовательно [вычитая почленно (9) из A0)],
или
«„+2 = 2«„+1 —ии + 2. A1)
Увеличивая в равенстве A1) п на единицу, будем иметь:
«»-гЗ=2«я + 2-«я+1 + 2; A2)
откуда [вычитая почленно A1) из A2)]
«ячз—ия+8 = 2я„+2—Зи„+1 + ия,
или
я„+3=3я|1т!!—Зая+1 + яя. A3)
Мы получили возвратное уравнение третьего порядка.
Следовательно, последовательность (8) есть возвратная после-
мовательность третьего порядка. Подобным же образом
дожно убедиться в том, что последовательность кубов нату-
натуральных чисел
I3, 23, З3 я3, ... A4)
есть возвратная последовательность четвёртого порядка.
Члены её удовлетворяют уравнению
ип.н-— 4й;г+3 — 6м„+2 +4«„+1 — ия, A5)
которое предлагаем вывести читателю.
Пример 5. К возвратным относятся все периодические
последовательности. Рассмотрим, например, последователь-
последовательность цифр десятичного разложения числа
761г = 0,57132132132...
1332"
Здесь
, о ,. -| i О |
Очевидно, что
«я+з=«„ (я =эЗ). A7)
Чтобы представить это уравнение в виде B), перепишем его
следующим образом:
Отсюда видно, что это возчратное уравнение третьего
порядка (k=3, aj = 0, a2 = 0, as=l). Итак, последователь-
последовательность A6) есть воззратная последовательность третьего
порядка.
Пример 6. Рассмотрим теперь последовательность коэф-
коэффициентов частного от деления двух многочленов, располо-
расположенных по возрастающим степеням х. Пусть
Будем делить Р(х) на Q(x); если Р(х) не делится
на Q (л:) без остатка, то деление можно продолжать неогра-
неограниченно. В частном один за другим будут получаться члены:
Do -f Dxx + D,x* -\- D3xB -f ... + Dnx" + ...
Рассмотрим последовательность
Ml=Dc, «, = ?>!,..., uH=Dn_v ... A8)
и докажем, что она является возвратной порядка k (напомним,
что k есть степень делителя). Для этой це.-.и фиксируем про-
произвольное натуральное число п, удовлетворяющее единствен-
единственному условию я^/—-/е —|— 1, и остановимся в процессе деле-
деления на члене частного, содержащем x"+k. Тогда в остатке
получится некоторый многочлен R(x), содержащий х в сте-
степенях выше, чем n-\-k. Записывая соотношение между дели-
делимым, делителем, частным и остатком, получим следующее
тождество:
(До4" • • • +Dn+kx"+k) + R(х).
Найдём коэффициенты при хп+к в левой и гравой частях
этого тождества и приравняем их между собой. Так как
я-j-& 5= /-|~ 1> то коэффициент при r'I + ft в левой части равен
нулю. Поэтому должен равняться нулю и коэффициент при
хп+к в правой части. Но члены с xn+k содержатся здесь только
в произведении (?0+ ... + Яй**)-(О0+ .. . -fDn+ftx»+A)
[остаток R(x), как мы указывали, содержит х в более высо-
высоких степенях]. Поэтому искомый коэффициент есть
Dn+k So + Dn+k_x Вх + • ¦ • + DnBk; A9)
mo предыдущему он должен равняться нулю:
откуда (вспомним, что
%^ ). B0)
Это — возвратное уравнение порядка k, откуда и следует,
что последовательность A8) есть возвратная последователь-
последовательность порядка k.
3. Из всех рассмотренных примеров наиболее общий харак-
характер имеет пример 6. Покажем, что произвольная возвратная
последовательность порядка k
«ь и2, ... , и„, ... , B1)
удовлетворяющая уравнению вида
un+k=a\lln+k~i+---+akun («>/«> 1), B2)
совпадает с последовательностью коэффициентов частного,
полученного от деления некоторого многочлена Р(х) на мно-
многочлен
Q (х) = 1 — ахх — ... — akxh. B3)
Пусть п — произвольное натуральное число, удовлетворяю-
удовлетворяющее условию п~^> k-\-m—2; умножим многочлен Q(x) на
их -\- иъх -\- usx2 -j- . .. -|-мн + 1х". Получим:
A — а,дг — а2х2— . . . —akxk) (ux-\-u2x-\-
— ахих)х-\- .. .-f-
Здесь в цервой квадратной скобке находится многочлен
степени не выше l = k-\-m— 2, коэффициенты которого не
10
зависят от взятого нами числа я; мы обозначим его через Р{х):
Р (X) = «! + («2 — «l«l) * +
+ • • • +(«*+«-! - «!«*+«-»— • • •—«*«„_,)**+"-«. B5)
В следующей квадратной скобке находится многочлен, все
коэффициенты которого равны нулю, в силу равенства B2).
Наконец, в последней квадратной скобке заключается много-
многочлен, коэффициенты которого зависят от п; он не содержит
членов степени ниже «—j— 1. Обозначая его через Rn{x),
перепишем тождество B4) в виде
Р{х) = (\— ахх — агх*— ...— а#ж*)(в1 + и2х +
+ ¦¦¦+««+!*") + /?«(*)• B6)
Отсюда видно, что их -J- игх -}-... -\-чп+\Хп представляет
частное, a Rn(x) — остаток от деления Р(х) на
Q (х) = 1 — atj; — агхг — ... — akxk,
т. е.
а,, а2 , и„, й„+]) ...,
действительно является последовательностью коэффициентов
частного, получаемого от деления многочлена B5) на B3).
В виде примера рассмотрим последовательность Фибоначчи:
«i = l, и2=1, и3 = 2, и4 = 3, и5 = 5, ...
Так как её члены удовлетворяют уравнению
то здесь т—\, k =2, а,=^1, а2=1 и Q(дг) = 1—л- — х2.
Многочлен Р(х) должен иметь степень не выше
k-\-m — 2 = 1. По формуле B5) получаем:
Итак, числа Фибоначчи совпадают с последовательностью
коэффициентов частного от деления 1 на 1—х — х2.
4. Один из вопросов, который приходится решать в курсе
средней школы относительно арифметической и геометрической
прогрессий, а также последовательности квадратов натуральных
чисел, заключается в отыскании суммы п членов каждой из
этих последовательностей.
Пусть, вообще,
«,, «2, . . . , ип, . . . B7)
11
—. возвратная последовательность порядка k, члены которой
удовлетворяют уравнению:
«*+* = eia*+*-i + eiB«+*-s+-¦•+«*«« («>'")• B8)
Рассмотрим новую последовательность, образованную сум-
суммами sn чисел B7):
si=uu *2 = й1+и2)... , 5n=a1-j-M2 + - •• + «„,.-•. B9)
и покажем, что эта последовательность сумм является также
возвратной, порядка k-\-\, причём её члены удовлетворяют
уравнению
— ak_l)sn+l — aksn. C0)
Для доказательства заметим, что
«1 = *1, И2 = 52 —Hi=S2 —5Х, ... \_
... ,an==su — {ul-\-...-{-ttH_l)z=sn — slt_v ... J
Полагая s0 = 0 так, что и1 = 51—s0, и подставляя в урав-
уравнение B8) вместо ии и2, ..., и„, ... их выражения через
s0, s1 sn, ..., получим:
откуда
-f (о, —а,
или, заменяя здесь п через я-J-l:
Это—возвратное уравнение порядка &-J-1.
Приведём несколько примеров:
а) Геометрическая прогрессия. Здесь un — aqn-x
И Sn=="l + M2+--- + Mn = a + fl:<74-'- .+ a7"- Так как
члены {ип} удовлетворяют уравнению вида un + 1 = qun, то
члены \sn\ должны удовлетворять уравнению
*я+,= A+?К+1 —9V C2)
б) Последовательность квадратов натураль-
натуральных чисел. Здесь ип = я2 и sn=\ -\-22-\-.. ,-\~п2. Так
12
как члены {ип) удовлетворяют уравнению
(см. стр. 8), то члены {sn} удовлетворяют уравнению вида
*в+4 = Ч+в— К+2+4,+1 — V
в) Числа Фибоначчи. Так как они удовлетворяют
уравнению
Sr. + 3 == "я +2 Stf
5. В случае простейших возвратных последовательностей!
например арифметической и геометрической прогрессий, по-
последовательности квадратов или кубов натуральных чисел,
а также периодической последовательности, мы можем нахо-
находить любой член последовательности, не прибегая к вычи-
вычислению предшествующих членов. В случае же последователь-
последовательности чисел Фибоначчи или общей последовательности
коэффициентов частного от деления двух многочленов, мы,.на
первый взгляд, не имеем возможности для этого, и чтобы
вычислить тринадцатое число Фибоначчи и]8, находим
предварительно, один за другим, все предшествующие члены
(пользуясь уравнением «я+2 = «п+1 + и„):
13, и8 = 21, и9 =
Займёмся теперь детальным исследованием структуры чле-
членов возвратной последовательности и в результате получим
формулы, позволяющие вычислять в самом общем случае лю-
любой член возвратной последовательности, не прибегая к вы-
вычислению предшествующих членов. Формулы эти можно будет
рассматривать, как далеко идущие обобщения формул для
общего члена арифметической или геометрической прогрессий.
Пусть
+ ...+ аЛ C3)
— возвратное уравнение порядка k. Если оно выполняется
для всех натуральных значений л=1, 2, 3, ..., то, положив
я= 1, получим:
13
Итак, зиая uv a2, ..., uk, можно вычислить uk+v Пола-
Полагая затем в уравнении C3) я = 2, найдём:
Следовательно, нам известно теперь и значение %+2- Вообще,
если т — какое-либо натуральное число, и мы вычислили уже
члены последовательности
то, полагая в уравнении C3) п = т, мы найдём из него сле-
следующий член um+k.
Итак, члены возвратной последовательности порядка k,
удовлетворяющей уравнению C3), определяются единствен-
единственным образом с помощью этого уравнения, если известны пер-
первые k членов последовательности: и{, а2, ..., ak. Выбирая
их различными способами (этот выбор не связан никакими
ограничениями), можем получить бесконечное множество раз-
различных последовательностей, удовлетворяющих уравнению C3).
Их различие между собой будет проявляться уже в первых
k членах (по крайней мере, в одном из них) и будет обна
руживаться также и в дальнейших членах.
Так, например, уравнению первого порядка
«»+г
удовлетворяют всевозможные геометрические прогрессии со
знаменателем q (они различаются друг от друга значениями
первого члена Uj); уравнению второго порядка
(или ип+2 — un+i = un+i — и») удовлетворяют всевозможные
арифметические прогрессии, различающиеся друг от друга,
по крайней мере в одном из членов их = а и u2'=a-\-d., и,
следовательно, различающиеся либо значением первого чле-
члена (а), либо значением разности (d), либо тем и другим вместе.
Рассмотрим ещ8 уравнение второго порядка
«„+2 = "»+! + «„•
Ему, кроме последовательности Фибоначчи:
1, 1, 2, 3, 5, 8, 13, 21, 34, ....
характеризующейся тем, что здесь ut — и2 = 1, удовлетво-
удовлетворяет ещё бесконечное множество других последовательностей,
14
получающихся при различном выборе значений и1 и и2. Так,
например, при ах= — 3 и и2=1 получаем последователь-
последовательность:
— 3, 1, —2,-1,-3, —4, — 7, —11, —18, —29,,..
Пусть мы имеем некоторое количество последовательно-
последовательностей, удовлетворяющих одному и тому же уравнению C3):
хъ х2, .. ., хп, ....
.Ук У2, ¦ • •- Уп< ¦ ¦ •¦¦
C4)
zv z2, ...,
Тогда выполняются уравнения:
Возьмём произвольные числа А, В, ..., С, по числу по-
последовательностей C4), умножим все члены первого из урав-
уравнений C5) на А, второго на В, . .., последнего на С и сло-
сложим. Тогда получим равенство:
C6)
Из него следует, что последовательность
tl=Ax1-\-By1+ ...-
t2 ^ Ахг-{-Вуг-\- .. .-
C7)
получающаяся из последовательностей C4) путём умножении
всех членов первой из них на А, второй на В, ..., последней
на С и затем почленного сложения последовательностей (первых
членов с первыми, вторых со вторыми и т. д.), удовлетворяет
данному уравнению C3). Пользуясь произволом в выборе чисел
А, В, ..., С, мы можем, изменяя эти числа, получать, во-
вообще говоря, различные значения членов tx, tit ts, ...
15
Пусть теперь
и\, и2, . . ., ип, .. . C8)
— какая-либо последовательность, удовлетворяющая уравне-
уравнению C3); спрашивается, нельзя ли придать числам А, В, ..., С
такие значения, чтобы первые k членов последовательности C7)
совпали бы с первыми k членами последовательности C8)?
Если это удастся, то по предыдущему совпадут и все члены
последовательностей C7) и C8), т. е. мы будем иметь при
любом натуральном п:
ин = Ахп -Г ВУ» + • • •+ Сгп. C9)
Таким образом, перед нами открывается возможность
(пока гипотетическая) представлять любую из бесконеч-
бесконечного множества последовательностей, удовлетворяющих одному
и тому же возвратному уравнению порядка к, через некото-
некоторые из них C4), по формуле C9). Реализация этой воз-
возможное ш зависит от того, возможно ли подобрать числа
А, В, ..., С так, чтобы удовлетворялись уравнения:
Ах.2 -|- By 2 ~\-...-\-Сг2 = «2)
Axk
с произвольно заданными значениями правых частей ии
«2- ••¦, «ft-
Так как неизвестными здесь являются числа Л, В, ..., С,
а число уравнений равно порядку k возвратного уравнения,
то отсюда следует, что и количество неизвестных А, В, ..., С
[а оно совпадает с количеством последовательностей C4)],
целесообразно взять также равным k. Мы знаем, что наличие
решений у системы k алгебраических уравнений D0) с k
неизвестными А, В, . . ., С зависит от того, каковы коэф-
коэффициенты этой системы: хг, _уь ..., zu ..., xk, yk, ...,zk,
т. е. от. того, каковы начальные члены последовательностей C4).
Решение наверное будет существовать, при произвольных
правых частях и1? а2, . .., uk, если мы положим, например,
16
В самом деле, в этом случае система D0) принимает
простейший вид, сразу обнаруживающий решение системы
Конечно, возможен и иной выбор чисел
при котором система D0) имеет решение, каковы бы ни
были правые части уравнений. Например, положим
лг2 = О, уг=\, ..., гг=\; I D2)
Тогда система примет вид:
C=uk,
откуда последовательно получаем:
C=-uk В = и2 — и3, Л = И1 — й2.
Обращаясь к общему случаю, формулируем следующую
теорему:
Для того чтобы система k линейных алгебраических
уравнений D0) с k неизвестными имела решгние А, В, ..., С
и притом единственное, при любых значениях правых
частей ии и2, ..., uk, необходимо и достаточно, чтобы
соответствующая ей однородная система
D0')
2 Возвратные последовательности 17
имела бы одно только нулевое решение *):
А ^^ В ^=-. а . =^ С =^ О .
Читатель легко проверит, что условие этой теоремы вы-
выполняется в частных случаях D1) и D2). В дальнейшем мы
столкнёмся со случаями, в которых высказанное предло-
предложение окажется полезным. Пока же будем просто опираться
иа тот факт (установленный независимо от последней теоремы),
что всегда существуют числа xv ..., zu ..., xk, ..., zk
[начальные члены последовательностей C4)], такие, что
система уравнений D0) имеет решения при любых
av и2, ..., uk.
Если числа такого рода выбраны в качестве начальных
членов последовательностей C4), то, по предыдущему, любая
последовательность, удовлетворяющая возвратному уравне-
уравнению C3), выразится по формуле C9), где числа Л, В, ..., С
определяются из уравнений D0). Система k последователь-
последовательностей C4), через которые члены любой последовательности,
удовлетворяющей данному уравнению C3), выражаются по
формулам C9) (т. е. путём умножения на некоторые числа
А, В, . .., С и сложения), называется базисом возвратного
уравнения.
Из изложенного следует, что каждое уравнение обладает
базисом, который можно выбирать по-разному. Например,
*) Указанное предложение удобно тем, что оно не требует
для своего применения знакомства с теорией определителей. Для
читателя, знакомого с этой теорией, напомним, что для существо-
существования решения системы D0), при любых значениях правых частей
этих уравнений, необходимо и достаточно, чтобы определитель
системы
Ч У\ ¦¦¦
2 Уг ... г
1 Уп ¦¦¦ z
был отличен от нуля. Это же условие необходимо и достаточно
для того, чтобы решение системы D0) являлось единственным при
каких-либо фиксированных правых частях (например, равных нулю).
Таким образом для системы k линейных уравнений с k неизвест-
неизвестными условия существования решения при любых правых частях
совпадают с условиями единственности решения при нулевых пра-
правых частях. Именно этот факт и выражен в предложении, приве-
приведённом в тексте.
18
системы с начальными членами:
1.
0,
0,
0, .
1, •
0, .
.., 0
.., 0
. . .
... 1
или
1,
о,
о,
1,..
1,..
0, ..
., 1
., 1
., 1
(ft)
(ft)
образуют базис произвольного возвратного уравнения порядка*.
Подведём игоги сказанному в п. 5.
Для каждого возвратного уравнения порядка k сущест-
существует бесконечное множество различных, удовлетворяющих
ему последовательностей. Любую из них можно составить
из k последовательностей, удовлетворяющих этому уравне-
уравнению и образующих его базис, путём умножения каждой
из k последовательностей соответственно на некоторые
числа А, В, ..., Си почленного сложения.
Таким образом для полного решения возвратного уравне-
уравнения порядка k достаточно найти лишь конечное число k
удовлетворяющих ему последовательностей, образующих
базис этого уравнения.
Поясним сказанное примерами.
Пример 1. Пусть дано возвратное уравнение второго
порядка:
«я+« = 2«я+1 —«„.
Его базис должен состоять из двух последовательностей:
¦*1> "**2» *8> • • • > ^п' • • • >
Уи Уг, Л. • • • - Л>- ¦ • •
Мы выберем их, положив
Так как возвратное уравнение, переписанное в виде
показывает, что разность соседних членов последовательности
является постоянной, т. е. что последовательность, удовле-
удовлетворяющая данному уравнению, необходимо является арифме-
арифметической прогрессией, то в случае последовательности \хп}
с начальными членами х1=\ и х2= 1 мы получаем ариф-
арифметическую прогрессию с разностью нуль, т. е.
1, 1, 1, ..., 1, ... (*я=1),
2* 19
а в случае последовательности {уп} с начальными членами
у1 = 0 и у2=1—арифметическую прогрессию с разностью,
равной единице, т. е.
О, 1, 2, .... я—1, ... {Уп = п— 1).
По формуле C9) член любой возвратной последователь-
последовательности, удовлетворяющей данному уравнению, может быть
представлен в виде
где А и В должны быть определены из уравнений:
и1=А + В(\ — 1),
т. е.
«1 = Л,
иг=А-\-В.
Отсюда
А = и1, В=иг —
и, следовательно,
Это и есть общая формула для члена любой последователь-
последовательности, удовлетворяющей уравнению
Полагая ^ = 0, и2 — ul = d, мы представим её в виде:
Это—известная формула для общего члена арифметической
прогрессии.
Пример 2. Рассмотрим другое возвратное уравнение
второго порядка:
и — и —I— и
Полагая дг1=1, ^2 = 1, получим уже знакомую последова-
последовательность Фибоначчи:
1, 1, 2, 3, 5, 8, ...
В качестве второй последовательности, входящей в состав
базиса, возьмём последовательность {уп\, Для которой у± = О
20
а у2=\. Будем иметь:
Здесь _у2 = лг,, _ys = Jf2, .у4=л:3, _Уб = лг4. ... и, вообще,
уп — хп_х (га =2, 3, ...). В самом деле, если мы уже уста-
установили эти равенства для всех значений п sg m -j- 1 так, что,
в частности, ym+l=xm, ym — xm_v то для ут+г получим:
Ут+^—Ут+х ~\~Ут == Хт "Г "^m-i== ^m+l'
т. е. предполагаемые равенства справедливы и для п=/и -(- 2.
Итак,
Поэтому для любой последовательности, удовлетворяющей
уравнению
находим по предыдущему [формула C9)]:
где Л и В определяются из уравнений
откуда
А = ии В~и2 — и,
и
При л^2 _у„ можно заменить через #n_i, откуда
или
При л
•*я == -^n-i "Г -^и-г» т- е- хп хп-1==хп-2
и, следовательно,
Итак, члены любой последовательности {«„}, удовлетво»
ряющей уравнению
21
выражаются через числа Фибоначчи по найденной нами формуле.
В частности, если ul = — 3, и2=-\ (см. стр. 15), то
б. Покажем теперь, что при некоторых весьма общих
условиях можно найти базис возвратного уравнения C3)
состоящий из k геометрических прогрессий с различными
знаменателями. С этой целью выясним, при каких условиях
некоторая геометрическая прогрессия
х1==\, x2 = q, ..., x^q"-1, ... (q=?0)'_
удовлетворяет уравнению C3). Замечая, что
хп+к Я ' xn + k-i—Я > •••' хп Я
и подставляя эти величины в уравнение C3) (вместо ия ^
"«+*-!> •••> и„)> получим:
откуда
»+...+**• D3)
Итак, геометрическая прогрессия только тогда может
удовлетворять возвратному уравнению C3) порядка k.
когда знаменатель прогрессии q удовлетворяет алгебраи-
алгебраическому уравнению D3) степени k с теми же коэффициен-
коэффициентами, как м в уравнении C3).
Уравнение D3) называется характеристическим для воз-
возвратного уравнения C3). Если q=a — какой-либо корень
характеристического уравнения (действительный или мнимый),
то, положив
хп = ап-1 (л = 1,2,...), D4)
получим геометрическую прогрессию с первым членом л:1=1
и со знаменателем а, которая удовлетворяет уравнению C3).
В самом деле, по условию, а есть корень уравнения D3),
т. е.
а* = й1а*-1 + а2а*+ • • • +ak-
Умножая обе части на а"-1, где п — произвольное натураль-
натуральное число, получаем:
a»+*-i = tf1a"+*-I-feia"+*-e+ . ..-\-aka"-\
т. е. последовательность D4) удовлетворяет уравнению C3).
22
Итак, каждому корню <7 = а характеристического уравне-
уравнения D3) соответствует геометрическая прогрессия D4) со
знаменателем а, удовлетворяющая возвратному уравнению C3).
Чтобы составить базис из одних лишь геометрических
прогрессий с различными знаменателями, нужно иметь их
в достаточном количестве, равном k, а для этого нужно
иметь k различных корней характеристического уравнения.
Допустим, что все корни характеристического уравнения
различны между собой:
Тогда получим k геометрических прогрессий, удовлетворяю-
удовлетворяющих уравнению C3):
1, а, а2, ..., а"-1, ...,
Ivy2 v"-1
Покажем, что система последовательностей D5) составляет
базис уравнения C3), т. е. что для всякой последователь-
последовательности {и„}, удовлетворяющей уравнению C3), можно подо-
подобрать такие числа А, В, .. ., С, что будем иметь при
любом п:
Для доказательства достаточно проверить, что система
уравнений, получаемых из D5), при я=1, 2, ..., к:
D7)
имеет решение относительно неизвестных А, В, .. ., С при
любых значениях правых частей этих уравнений, а для этого
в свою очередь достаточно (см. стр. 17), чтобы соответству-
соответствующая однородная система
-|_...-[-С=0,
23
допускала одно только нулевое решение. Но это действи-
действительно так.
В самом деле, допустим, что существует нулевое ре-
решение D8), т. е. что существуют числа А, В,... С, из
которых по крайней мере одно, например А, отлично от
нуля, удовлетворяющие системе D8). Чтобы вывести отсюда
противоречие, построим сначала многочлен М (х) степей»
k — 1, обращающийся в нуль при л::=[5, ..., лг = у и
в единицу при х = а. Так как многочлен этот ст°пени k—1
и обращается в нуль при k — 1 различных значениях х:
Р, ... у> т0 он должен иметь вид:
М (Х) = ц{х-$)...(х-ч),
где ja—какое-либо число. Полагая х = а, мы должны полу-
получить М (а) = 1, откуда
Итак,
^W —(«_(i)... («--,) '
очевидно, что он действительно удовлетворяет поставленным
условиям. Раскрывая скобки и приводя подобные члены,
представим его в виде
М (х) = т0-}-тхх-\- .. . -\~mk_1xk-1.
Если теперь умножить уравнения D8) на т0, mv. . ., mk_-i
я сложить почленно, то получим:
А К -\-ща + ... + от*-,»*)
+ С(т0 + wlY + . .. + %_Jft-г) = О,
или
Но М(а)= 1, Ж(Р) = 0, ..., Ж(у)=^0 и, следовательно,
А = 0,
что противоречит предположению.
Итак, система D8) имеет одно только нулевое решение,
и следовательно, система D7) имеет решение (единственное)
24 .
при любых И], и2, ..., uk, а это в свою очередь означает,
что система D5) образует базис уравнения C3).
Мы нашли, таким образом, что дли всякого возвратного
уравнения
для которого соответствующее характеристическое уравнение
имеет различные корни: q = u, <7=i^ ••-•. <7 = Y'
ствует базис, образованный k геометрическими прогрес-
прогрессиями со знаменателями: а, ^, ..., у- Иными словами, для
членов любой последовательности {м„}, удовлетворяющей
уравнению C3), существует k чисел: А, В, ..., С [они на-
находятся из уравнений D7)] таких, что
йя-=Да"-1 + 5?"-1+ ••• +C-f-' (я== 1,2,3,...).
Подведём итоги сказанному в п. 6.
Возвратному уравнению порядка k соответствует алге-
алгебраическое уравнение степени k с теми же коэффициен-
коэффициентами — его характеристическое уравнение. Каждый из
корней характеристического уравнения представляет зна-
знаменатель геометрической прогрессии, удовлетворяющей
данному возвратному уравнению. В случае, когда все корни
характеристического уравнения различны между собой,
получаются k различных геометрических прогрессий, обра-
образующих базис возвратного уравнения. Следовательно, в этом
случае члены любой последовательности, удовлетворяющей
возвратному уравнению, можно получить путём почленного
сложения некоторых геометрических прогрессий (числом k).
7. Займёмся приложениями найденных результатов. Нач-
Начнём с последовательности Фибоначчи. Здесь возвратное урав-
уравнение таково:
и, следовательно, характеристическое уравнение D3) имеет
вид:
Решая его, получим два различных действительных корня:.
и 1 = 1-±
^ 2 2
25
Поэтому общий член последовательности Фибоначчи иоишо
записать так:
Чтобы найти неизвестные коэффициенты А и В, положим
л=1 и я=2; получим:
Решая последнюю систему, найдём:
и, следовательно,
2У5
или
¦)"-'.
<«•
Это и есть общее выражение для чисел Фибоначчи. На пер-
первый взгляд выведенная формула представляется громоздкой и
мало удобной для вычислений. Однако с её помощью можно
получить ряд любопытных результатов. Покажем, например,
что сумма квадратов двух соседних чисел Фибоначчи есть
также некоторое число Фибоначчи.
В самом деле:
¦> 1
я+1 —5"
следовательно,
1
Итак,
Например,
и13 = и) -f- «|= 132 + 82 = 233.
Это, между прочим, и есть ответ на задачу Фибоначчи.
Предлагаем читателю доказать для чисел Фибоначчи
соотношение более общее, чем E0), а именно:
В качестве другого приложения формулы D9) докажем
следующую теорему:
Пусть а и b — два натуральных числа, причём а<^Ь;
тогда число операций последовательного деления в алгорифме
Евклида, необходимых для отыскания наибольшего общего
делителя (сокращённо: н. о. д.) а и Ь, не превосходит
упятерённого числа цифр числа а, записанного по десятич-
десятичной системе счисления.
Применяя к отысканию н. о. д. чисел Ъ и а алгорифм
Евклида, получаем цепь равенств:
2) а=у'х"-\-у\
з) /=/'*"<+/
A-f 1) у*-»)=_у1*)лг(*+1).
Здесь последовательные остатки удовлетворяют неравенствам
<*>/>/'>/">• • .>у*-»>у*» 1.
В последнем из равенств E2) остаток равен нулю. Сле-
Следовательно, предыдущий остаток У*) и есть н. о. д. чисел
Ь и а. Поэтому k обозначает число операций, потребных для
отыскания н. о. д. Наша задача, как мы уже сказали, заклю-
заключается в оценке числа k. С ' этой целью будем сравнивать
числа У*), у*-», ..., у, а с числами Фибоначчи ии и2,
и3, ... Заметим, чтоУ*)^1=«2> н0 предыдущий остаток
У*-*) больше у*) и, следовательно, У*~1)^2 = и8. Поэтому
из^равенства k заключаем, что
У*-Ч =у*-1)лг(*) +У*> Эз y*-i). 1 +У*) 5з «8 + «2 = й4.
Итак, У*>3*«8, У'-Ч^Ид» У*~аMз«4.
27
Допустим, что мы уже доказали справедливость неравенств
Тогда из равенства _у1т~2)=Уп)-*г('")Ч"У'п) заключаем
Итак, продолжая наши рассуждения, мы дойдём до неравенств
и далее, из соотношения 2) выведем, что
Но «ft+2 по формуле D9) имеет следующий внд:
Поэтому
W
так как
1 и, следовательно,
1-V5
2
Из E3) получаем, что
, так как
Поэтому
Заметим теперь, что
E3)
E4)
откуда
Следовательно,
E5)
Если число а по десятичной системе счисления записы-
записывается с помощью п цифр (а — я-значное число), то очевидно,
что
откуда
a -f К Ю"
я, следовательно, в силу неравенства E5),
или
/е<5я. E6)
Это и есть нужный результат: количество k последова-
последовательных делений в алгорифме Евклида меньше, чем упятерён-
упятерённое число цифр наименьшего из чисел b и а, записанного
по десятичной системе счисления. Из прнвгдённого здесь до-
доказательства можно усмотреть, что наиболее невыгодный случай
применения алгорифма Евклида (в смысле значительного ко-
количества операций, близкого к установленному в теореме
пределу) будет тогда, когда b и а являются соседними чис-
числами Фибоначчи. Для подтверждения этого возьмём, напри-
например: ? = м20 = 6765 и а^и,9 = 4181. Здесь а—четырёх-
а—четырёхзначное число и, следовательно, по доказанной теореме, коли-
количество операций в алгорифме Евклида должно быть меньше
5-4 = 20. В действительности мы получаем здесь k= 17 опе-
операций. В самом деле:
1)
2)
3)
4)
5)
6)
7)
8)
9)
6765 =
4181 =
2584 =
1597 =
987 =
610 =
377 =
233 =
144 =
4181-
-
2584-1-
1597-
987-
610-
377-
233-
144-
89-
-2584,
-1597,
- 987,
- 610,
- 377,
- 233,
- 144,
- 89,
- 55,
10)
П)
12)
13)
14)
15)
16)
17)
18)
89 = 55-
55 = 34 •
34 = 21-1
21=13-
13= 8-
8= 5-
5= 3-
3= 2-
2= 1-:
-
-
2-
-34,
-21,
-13,
- 8,
- 5,
- з,
- 2,
- 1,
- 0.
29
В качестве остатков здесь получаются одно за другим в
убывающем порядке числа Фибоначчи. Все частные (кроме
последнего) равны единице, чем и объясняется наличие боль-
большого числа операций. Наибольший общий делитель оказался
равным единице [равенство A7I, что для соседних чисел Фи-
Фибоначчи можно было предвидеть с самого начала. Действи-
Действительно, из того, что м„ + 2 —мл+1~Ьил> вытекает, что н.о.д.
чисел ап+2 и ип+1 совпадает с н.о.д. ип+1-\~ап. Поэтому
для каждой пары соседних чисел Фибоначчи н.о.д. один и
тот же. Чтобы найти его, достаточно рассмотреть пару иг=
— их = 1 ,v откуда и следует, что он равен единице.
8. В качестве следующего примера рассмотрим периодиче-
периодическую последовательность A6):
и, =5, «2=7> «з=Ь "* —3> «б=2, ив=1, «7— 3, ...
Здесь возвратное уравнение имеет вид:
и, следовательно, характеристическое уравнение таково:
Эго уравнение имеет следующие корни:
Поэтому общий член последовательности следует искать
в виде [см. формулу D6)]
+с(-т-'тг) ¦
Мы можем требовать, чтобы формула эта выполнялась для
всех значений п, для которых выполняется и возвратное урав-
уравнение: я=3, 4, 5, ...
Заметим, что
1 , . Уз ( и . . п
- 2+1 — = ~ [COS -г sin Т
80
поэтому по формуле Муавра:
[cos у(я—1) — / sin-1(я—1)]
-f/( — Я-f Q( — ly-isin j(n— I).
Положим В -\- С = А1 и i ( — В -(- С) = Л2; тогда фор-
формула эта перепишется так:
и останется лишь определить неизвестные коэффициенты Л, Л]
и Л2. Полагая я=3, я = 4 и л = 5, получим три уравне-
уравнения с тремя неизвестными:
iti^ = /l— 1А*+~Т А*'
и4 = 3=Л —/Ijcos-^ — A2sin ~=A-\-A1,
y4"'42sin-j- = '4— ~2 А\ — — Af
Отсюда находим:
А = 2, Л,= 1 и At=—^=.
Итак,
Мы видим, что общий член последовательности выра-
выражается в этом примере через тригонометрические функции,
что вполне согласуется с периодичностью последовательности.
Приведём, наконец, пример, непосредственно относящийся
к делению многочленов,
31
Пусть нам даны два многочлена: Р(х) = 3-\- х2— х6 и
Q(x)=2— х — 2х2-\-х3; задача заключается в определе-
определении структуры коэффициентов частного, получающихся от
деления Р(х) на Q(x). Последовательность коэффициентов
частного
«! = /)(,, И2=?>1. ••• , t*n=Dn-V
как мы видели в п. 2, является возвратной последователь-
последовательностью, члены которой удовлетворяют уравнению B0):
DDD («>'
Здесь k—степень Q(x), Bo, Blt ... , Bk — коэффициенты
Q(x) и / — степень Р(х).
Следовательно, &=3, В0 = 2, В1=—1, Bs= —,
В,= \, 1-=Ь:
DD + ^D±D (я>53 + 13)
т. е.
Характеристическое уравнение имеет вид:
или
Поэтому его корни суть
и для D получаем формулу
Положим /z = 3, л = 4 и лг=5; получим уравнения:
D3=±A + B— С,
4 16
6 32
32
Здесь неизвестны не только коэффициенты А, В и Cf
но и числа Dv D4, D5. Чтобы определить их, произведём
фактически деление Р(х) на Q (х) так, чтобы в частном по-
получить члены до пятой степени включительно. Получим:
3+лг* — л* 2 — х —
'— ЛГ° — 1—.
Отаода Do = |, ?>, = !, D2 = 2|-, D,= li,
O=2— D - - —
Следовательно, полученная выше система уравнений имеет
вид:
" 32'
51
" 64'
откуда находим:
3 Возвратные последовательности
Итак,
Наша задача решена. Из найденной формулы получаем:
^в 128' 7 256' и» — ^512 ' • • •
9. Во всех разобранных выше примерах характеристиче-
характеристическое уравнение имело только простые корни. Рассмотрим,
однако, пример последовательности сумм квадратов натураль-
натуральных чисел, приведённый на стр. 13. Для этой последователь-
последовательности возвратное уравнение имеет вид:
1 — sn,
и, следовательно, характеристическое уравнение таково:
Оно обладает только одним четырёхкратным корнем: д^= 1;
поэтому мы и получаем здесь только одну геометрическую
прогрессию со знаменателем 1, члены которой удовлетворяют
данному возвратному уравнению.
В подобных случаях приходится искать другие простей-
простейшие возвратные последовательности, которые вместе с указан-
указанной геометрической прогрессией могут составить базис дан-
данного уравнения. В нашем примере такими последовательно-
последовательностями будут:
о,
о,
о,
1,
1,
1,
2,
4,
8,
з,
9,
27,
. . . , п —
...,(«-
...,(«-
1, •
IJ,
I)8,
(как это легко сможет проверить читатель). Не разбирая са-
самого общего случая, требующего довольно громоздких вы-
выкладок, мы остановимся на следующем типичном примере.
Пусть имеем возвратное уравнение
+ ... -f (-1 )* - >Cft° аЧ,- E7)
где Сй~ , Ck , . ¦ ¦ , Сь — биномиальные коэффициенты по-
34
рядка k. Соответствующее характеристическое уравнение
ф = CV aqk'x - Cf1 aV +•••+(- I)* C?«*
может быть представлено в виде
(«7 — о)*=0.
Оно имеет ^-кратный корень д = а; очевидно, что
(a — a)k = ak— ct~V +
+ CJ-V—...+(-l)*cJa*--O. F8)
Рассмотрим вообще следующие тождества:
(а — а)*- = а"- — ^Г'
где т = 0, 1,2, . .., k— 1, или:
A -1 )* -т=с?% - d=r: + с??~2 —... +
+ ( — iKCJt!T|l4-•••+( — 1)*-тсГт = о. E9)
Равенство E9), соответствующее значению т = 0, имеет вид
+ ...+(—1)*С2==О. E9')
Замечая, что
_ /fe(fe- I)... (k —
L* — 1-2 ...(*—ix) (k-
(m.= 1,2, ...,k— 1;
или
A<A— 1).. .(*—*»+ 1) CjZS~tl =
--=(& — да — ii-l- 1). . .(A — ji) Cj-1', F0)
помножим каждое из равенств E9') (т— 1, 2, ..., k— 1) на
соответствующий множитель k(k—l)...(k — т-\-1) и после
этого, пользуясь F0), перепишем их в виде:
f-...-Н— l)*-ml -2... mC°k=0 E9")
/« = 1, 2 ft—1).
Докажем теперь, что при /я = 0, 1,2, ...,k—1 спра-
справедливы следующие равенства:
к»>С% — (k— 1)'»сГ1+..
+ ...+( — 1)*.О*С2=О. F1)
В самом деле, равенство, соответствующее /и = 0, сов-
совпадает с E9') и, следовательно, справедливо.
Рассуждая по индукции, допустим, что равенства F1) уже
доказаны для /я —0, 1, ...,J(/^k — 2), и докажем тогда,
что равенство, соответствующее т= j-\-1, также справедливо.
С этой целью введём многочлен степени /'-J-1:
/•(*) = (*—у) (*—/•-{-1 )...(*—1)* =
= */+> — руУ_..._ fax. F2)
Умножая равенства F1) при /я= 1, 2, ...,/' соответственно
на числа E1( [|2, . .., [|у, получим:
=0,
F3)
/ Л- у
Запишем ещё равенство E9"), соответствующее значению
т —у'-|- 1, в виде:
f{k)dth—f{k-~\)C\~x-\- .. .+( — lVfik — Р-)С%~*-\-
+ •••+(—1)*/(°)с* = ° F4)
[мы воспользовались здесь тем, что (k—J)...k=f(k),
(k —у—1)... (k— l)=/(ft— 1),... ,(k—у— pi).. ,(k — fi) =
Складывая F3) и F4) почленно, будем иметь:
|fcft-|-...+p/A/-f/(*)]c? —
-[P,(ft—1)+...+M*-l>'+/(*—!)] С* + ••¦ +
+(_ 1), [ Pl (ft _ ^ _|_ ... _|_ ?/ (А __ ^)/+/ (А _ ^ cj- +
-f...+(- i)*[M+ • • ¦ +?/-o/+/(O)] c2=o.
Но в силу F2):
Поэтому полученный результат принимает вид
Это и есть равенство F1) для m=j-\-\. Таким образом,
доказательство справедливости соотношений F1) закончено.
Рассмотрим, наконец, произвольный многочлен степени не
выше k — 1:
Р(х)=:Л,_1хА-1 + Л,_2х*-2+...+Л0. F5)
Умножая равенства F1), при /л = 0, 1, 2, . . ., &—1, со-
соответственно на Ао, Ах, ...,Ak__v получим:
Складывая их почленно, будем иметь:
или
P(k)-ckk—P(k— 1).с^+...+( — i)*P(O)-c2=o. F6)
Следовательно, произвольный многочлен Р(х) степени не
выше k — 1 удовлетворяет соотношению F6).
Положим, в частности, Р(х) = (х-\~п—\)т, где п —
произвольное натуральное число и т — целое, Q^msSik—1.
37
Тогда равенство F6) примет вид.
(A-f«— \)mC\ — (k + n — 2ГС^-1+...+
+ (— 1)*(я — 1ГС2 = О,
или, помножая на <z*+"-i и заменяя С* через 1:
{k-\-n— \)ma4+n-l = Cki~l
— Ct~2a2 (k+n—
+ (-1)*-1С»а'(я-1)а11-1. F7)
Сравнивая F7) с E7), заключаем, что возвратному урав-
уравнению E7) удовлетворяет каждая из k аоследовательностеи
1,а,а2, ...,ап-\ ..., (т = 0); )
0,а,2аг,...,(п—\)а"-\..., (m = l); j
О, а, 22а2 (я —1)»а»-', .... (и = 2); f F8)
i
О, а,2*-'а2, ..., (n — \)k-lan-\ ..., (m = k— 1). J
Если мы установим, что они образуют базис, то отсюда
будет следовать, что общий член произвольной последова-
последовательности, удовлетворяющий уравнению E7), имеет вид:
= Q(n— \)an~\ F9)
где Q(x)^=B0-\-B1x-\-. ..-\-Bk_lxk~1 многочлен степени
не выше k—1, с произвольными коэффициентами.
Достаточно доказать, что система k линейных уравнений
имеет решение относительно неизвестных Во, Вх, . . ., Bk_l
при любых «J, . .., uk, т. е. (в силу предложения на стр. 17),
что система
имеет только нулевое решение. Но уравнения последней си-
системы обозначают, что
1) = 0,
т. е. что уравнение
степени не выше k—1 имеет, по крайней мере, k различных
корней: 0, 1, 2, . .., k—1. Отсюда следует, что
чем и заканчивается доказательство того, что последователь-
последовательности F8) образуют базис возвратных последовательностей,
удовлетворяющих уравнению E7).
В случае произвольной возвратной последовательности,
удовлетворяющей общему уравнению
). G0)
характеристическое уравнение
9*=о19*-Ч-...+аЛ G1)
может иметь некоторый корень а кратности а, корень р крат-
кратности Ь, ..., корень у кратности с, а всего а-\-Ь-\- ... -4-
-|-с—6 корней.
Для этого наиболее общего случая можно доказать, что
базис состоит из следующих k последовательностей:
1,о, а2, ..., а«-\ ...,
О, а, 2°-'а2 ,.. ., (n—I)"-1!*"-1, .. .;
1,р, р2, ....р»-1, ...,
О, р, 26-i^, ...,(я—l)»-ip»-', ...;
Поэтому
1,y,y2. ••
О, у, 2с-и>2
й —1)y"-', G2)
39
где Q(x), R(x), ..., S(x) — какие-либо фиксированные много-
многочлены, степеней не выше а—1, Ъ—1, ...,с—1 соответ-
соответственно.
Итак, общий, член ип любой возвратной последователь-
последовательности имеет вид суммы произведений многочленов относи-
относительно п—1 (или, что сводится к тому же, относительно я)
на общие члены геометрических прогрессий, знаменатели
которых равны корням характеристического уравнения G1).
В случае, когда все корни последнего уравнения — про-
простые, указанные многочлены являются постоянными и общий
член возвратной последовательности представляется в виде
суммы членов геометрических прогрессий.
Мо+сно доказать также справедливость обратного пред-
предложения. А именно, любая последовательность {и,,}, общий
член которой выражается по формуле G2), является воз-
возвратной*). Соответствующее характеристическое уравнение
{71) строится по его корням а, [3, ...,у « по их кратностлм
а, Ь, ..., с (представляющим степени многочленов Q, R, ... ,S,
увеличенные на единицу). Отсюда немедленно находится и воз-
возвратное уравн:ние G0).
Рассмотрим в виде примера последовательность
Сравнивая с G2), заключаем, что корни характеристического
уравнения таковы: а = 2, [5 = 3, причём кратность а равна
2-(-1=3. Поэтому характеристическое уравнение должно
иметь вид:
(<7 — 2)з (</ — 3) = q* — V + Щг — 44<7 -f 24 = 0,
г возвратное уравнение запишется так:
Предоставляем читателю проверить, что данная последова-
последовательность удовлетворяет последнему уравнению.
10. Иллюстрируем результаты п. 9 несколькими приме-
примерами. Мы видели в п. 2, что члены арифметической прогрес-
*) Доказательство прямой и обратной теоремы, которое мы
здесь опускаем, можно найти в четёртой главе нашей книжки
«Деление с остатком в арифметике и алге'ре» АПН РСФСР, М.— Л.,
1949, где теория возвратных последовательностей изложена спосо-
способом, отличным от принятого в этой брошюре.
40
сии удовлетворяют уравнению вида
квадраты натуральных чисел — уравнению
ип+з -- - Зи„ +
а кубы — уравнению
Зи„ + ,
Очевидно, что все эти уравнения содержатся как частные
случаи в уравнении
un+k= СГ V*-i - Ct~\+k_2 + ...+(- 1 )*-ic2«B, E7')
рассмотренном в п. 9 (здесь а=1).
Общий член любой последовательности, удовлетворяющей
этому уравнению, должен иметь вид [формула F9)]:
!(«—I)*- F9')
Чтобы найти коэффициенты Во, Bt, ..., ^_г достаточно
решить следующую систему к линейных алгебраических урав-
уравнений с k неизвестными:
В случае арифметической прогрессии k = 2 и формула
F9') примет вид:
«„ = ?„-!-?! (л—1),
а система G3) — вид:
В0 = аъ
& О Ч~ &1 == U2 ¦
Отсюда видно, что Б0 = и1 есть первый член прогрессии, а
В1=и2 — ul = d — разность прогрессии. Следовательно,
и„ = ^1+^(« — 1).
Мы получили хорошо известную формулу.
Нет нужды производить соответствующие выкладки дли
случая последовательности квадратов или кубов натуральных
чисел, так как мы с самого начала знаем здесь, что «„^w2,
Однако представляет некоторый интерес при-
применить соотношения F9') и G3) к выводу формул для суммы
членов арифметической прогрессии, а также суммы квадратов
или кубов натуральных чисел.
В п. 4 мы доказали, что если члены некоторой последо-
последовательности {ип} удовлетворяют уравнению вида
то суммы {snj членов этой последовательности (Sj = и1г s2=
=и1-|~и2, s2 = ul-\-u2-{-as,. ..) удовлетворяют уравнению
вида
i— aksn.
В случае уравнения E7') очевидно, что
Поэтому
1 -\- аг = 1 -\- Си = Ci^x,
а2— ах = — (Cl + С*) = - Cifл,
'\C = Cfrj^i,
Г1) = (-1 )* -1
и уравнение для {sn} может быть представлено в виде:
или
sn±k+i— cif i sn+k + c^+15Я4Л_1 __... + (— i )*+*c?{:I *„ = o.
Итак, если последовательность {ип} удовлетворяет урав-
уравнению вида E7') порядка А, то последовательность соответ-
соответствующих сумм {sn} удовлетворяет уравнению того же вида,
но порядка k-{-\. В частности, для арифметической прогрес-
прогрессии k = 2, для последовательности квадратов натуральных
чисел & = 3 и для последовательности кубов k = 4; следо-
следовательно, для последовательностей соответствующих сумм
нужно в указанных выше равенствах E7'), F9'), G3) брать
k на единицу большим: 3, 4 и 5.
а) Сумма членов арифметической прогрес-
прогрессии. На основании сделанных замечаний, sn выражается по
42
формуле F9') (с заменой ип на sn) при /е = 3. Следовательно,
*„ = Яо + В, (л — 1) + Вг (п — 1 )*.
Коэффициенты 50, 5^ Вг определяются из системы G3;
(с той же заменой ип на sn и при /е = 3):
2 • ^ + 22/?2 =
Решая её, получаем:
u
lt
Следовательно,
d (n— l)« =
б) Сумма квадратов натуральных чисе...
Беря в формулах F9') и G3) ?=4 и заменяя ип через sn,
получаем:
fi0 + 2В! + 4?2 + 853 = s3 = 1 + 22 + З3 = 14,
Во + 3Si + 952 + 2753 = s4 = 1 -f 22 -f З2 + 43 = 30.
Из последней системы находим:
Поэтому
— ±„_1_±И2 I ' -а _л
~6 +2 +уй - 6
Мы получили знакомую формулу.
43
в) Сумма кубов натуральных чисел. Для неё
имеем:
Этот вывод мы предоставляем читателю в качестве упражнения.
В заключение рассмотрим ещё пример последовательно-
последовательности: а, 2а2, За3,..., па",... (а^О, а=ф\).
Здесь
ип = па« (л-—1,2, 3,...).
Легко видеть, что
в самом деле
2аи„+1 — а%„= 2а (я + 1 )ап+1—а?па.п= (п -\- 2) ап+2 = а
Так как ?—2, ах = 2а и а2=—я2, то последователь-
последовательность сумм {sn} (><?j = а, 52 = a -f- 2а2, s3 = а -f- 2a2 + За3,.. .)
будет удовлетворять уравнению [см. C0)]:
a2 — ai) *и+1 ~ а2*„ ;=
= Bа +1) *я+2 — (а> + 2а) sn+1 + а»*я.
Соответствующее характеристическое уравнение таково:
«f = Bа -f-1) 92 — (а2 + 2а) ? + «2-
Легко видеть, что оно удовлетворяется при q=a. Деля
многочлен #3 — Ba-j- 1) <72 ~Ь (а3 + 2а) q — а2 на q — а, по-
получаем в частном:
Следовательно, остальные два корня характеристического урав-
уравнения удовлетворяют следующему уравнению:
Эти корни суть: а и 1.
Итак, характеристическое уравнение имеет корень а крат-
кратности а=2 и простой корень [5=1.
Поэтому для sn получаем [см. формулу F9), где вместо ип
следует писать sn, a= a, Q(x)^Bu-\-Blx — многочлен пер-
первой степени, $=] и /?(х) = С0 — постоянная]:
sn = [Bu-\-B1{n— 1)]а"-'+С0 (/1=1,2,3,...).
44
Коэффициенты Bq, Bl и Со находятся из системы урав-
уравнений, соответствующих значениям ге=1, 2 и 3:
(В+ 2SJ12 + Со = s3 = а + 2а2 + За3.
Отсюда находим:
^о — (а _ 1J- «1 —^гг и с° — (« — iy> •
Следовательно,
1 i /-. лс.п+2 — (я4-1)ая+14
1 + С=^^
(а-1J
ЗАКЛЮЧЕНИЕ
Эта книжка должна была дать читателю представление о
эа шообразии возвратных последовательностей и их роли в
математике. Вместе с тем мы показали, что возвратные после-
последовательности недалеко ушли от наиболее простых из них —'
геометрической прогрессии и последовательностей степеней
натуральных чисел (в частности, последовательности самих
натуральных чисел, составляющих арифметическую прогрес-
прогрессию)— и могут быть выражены с помощью этих простейших
последовательностей.
Но уже в элементарной математике на каждом шагу встре-
встречаются последовательности, не являющиеся возвратными. Та-
Такова, например, одна из наиболее важных во всей математи-
математической науке последовательность простых чисел:
2,3,5,7, 11, 13, 17,19,23,...
Эта последовательность, с её глубокими и сложными свой-
свойствами, изучается в теории чисел.
Не являются возвратными также последовательности зна-
значений многих элементарных функций, например:
1 _L JL _L 1
(последовательноегь значений функции у = — при х =
= 1, 2, 3, . . .), или
1, VI, }Т, VT, ... У/7,...,
1оц1, log'2, log; 3, log 4,. . . , lo<jw,. . .
(последовательности значений ф\нкииЧ \х и \og x) и т. д.
46
Изучением этих и им подобных последовательно-
последовательностей*) (а вместе с ними и возвратных последователь-
последовательностей) занимается упоминавшаяся выше математи-
математическая дисциплина—и счисление конечных раз-
разностей.
Наконец, в курсе элементарной математики и в
особенности в курсе математического анализа, изу-
изучаемого в высшей школе, весьма важную роль играют
сходящиеся последовательности, т. е. последователь-
последовательности, обладающие конечными пределами. Их изуче-
изучение составляет важнейшую задачу теории пределов
и относится к основам математического ана-
анализа. Свойства отдельных членов последовательно-
последовательностей играют при этом более чем второстепенную
роль: важен лишь факт существования предела и
величина этого предела.
Все эти замечания мы считаем необходимым сде-
сделать для того, чтобы читатель понял, что изложен-
изложенная нами теория возвратных последовательностей,
как с точки зрения своего предмета, так и с точки
зрения выявляемых ею закономерностей, представ-
представляет собой лишь весьма частную и скромную главу
учения о последовательностях.
*) Речь идёт о последовательностях значений так называемы*
аналитических функций, простейшими представителями ко-
которых являются элементарные функции.
Редактор А. 3. Рывкин.
Техн. редактор М. Д. Каслиновская,
Корректор Н. Г. Зайцева.
Ь
Подписано к печати 20/VII 1950 г. Т-05933.
Бумага 81X108/32. 0.75 бум. л. 2,44 печ. л. 2,6.
уч.-изд. л. 42 100 тип. зн. в печ. л. Цена
КНИ1Н 90 коп. Тираж 15 000 экз. Зак. № 711.
17-я тип. Главполиграфиздата
Москва, ул. 25 Октября. 5.
Цснэ 90 к.