Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 53
Текст из файла (страница 53)
Найдите представление числа х конечной цепной дробью в виде х = [со,с1, С2, Сз, Се, Сз, хв] для а) х=т/5; б) х=т/2; В) Х=11; г) х = (1 + 1/5)/2. 4. Пусть [Со,.С1,...,С„] — конечная цепная дробь, где С; > 0 для 1 < 1 < и. Докажите, что если 6 > О, то а) )Со', С1, С2,, С„) > [Со, С1, С2,..., С„+ 6], если и нечетно; б) [Со,'С1 Сю.,Се) ( )Со; СыСг,...,С„+ 6], если и четно.
7.5. ПОДХОДЯЩИЕ ДРОБИ [Со;] = Со = — =— Со Ро 1 Чо где мы положили ро = Со и 17о —— 1. 1 [Со' С1) = Со +— СоС1 + 1 Р1 где р, = С,С, + 1 и 41 = С1. 1 [Со) С!, С2] = [Со', [С1', С2]] = Со + — = [С1', С2] 1 С2 Со+ 1 =Со+ С,С,+1 1 + Сг С2 (СОС! + 1)С2+ Со Р1С2+Ро Р2 СоССС2 + Со + С,С, + 1 ССС2 + 1 В С2 + 7о 42 Вполне очевидно, что [Со, С1, С2,..., Сь) для каждого С4 представляет собой действительное число.
Запишем первые четыре подходящие дроби и упростим их, выразив каждую как отношение двух действительных чисел, где как числитель, так и знаменатель выражены через С;. Особый интерес будут представлять числитель и знаменатель каждой из подходящих дробей. РДЭДЕЛ 7.5. Подходящие дроби 311 гле Рг = РгС2 + Ро И Яг = ФС2 + 00. Подобным образом вычисляем СОС1С2СЗ + СОСС + СОС3 + С2СЗ + 1 [Со С! С2 СЗ] ССС2СЗ + С1 + СЗ (СОС1С2 + Со + С2)СЗ + (СОСС + 1) Р2СЗ + Р1 РЗ (СсС2 + 1)Сз + Сс ЧгСз + 01 Чз ' где Рз = Р2Сз + Р1 и 03 = гС2С3 + В. В каждом случае число [Со,'СыС2,...,Сь] "переформировывается" из представления цепной дробью без какого-либо "сокращения" и образует отношение двух полиномов Р и Я в переменных Со, Сы,,,, Сю т.е.
Р(С0, Сд,..., Сь) [С01С1~ С2 ... Сь] Ч(С0, Сы, Сь) Справедливым является и то, что до, джаз и дз положительны, поскольку получены путем умножения и сложения положительных чисел. Рассмотренные примеры дают основание сформулировать следующую теорему. ТЕОРЕМА 7.11. Пусть и — неотрицательное целое число и [Со, СыС2,...,С„]— конечная цепная дробь, которая рекурсивно определяет конечные последователь- ности Ро, ры, р„и 00, ды..., д„следующим образом: а) РО= Со, Яо = 1. б) р, = С,С, + 1, И =Си в) р, =Р,,С,+Рь 2 гСь = Ф-1Са + Чь-2 при 2 < Ь < п. Тогла Чь > О и [Со, 'Сы С2,..., Сь] = — при О < й < и, Рь И ДОКАЗАТЕЛЬСТВО. Не представляет труда методом математической индукции показать, что Сь > О при О < й < п.
Эту часть теоремы предоставляем доказать читателю. Выше было показано, что теорема справедлива при й = 0,1 и 2, т.е. [Со',] = Ро/гС0, [С01Сг] = Рс/Дс и [Со',СыС2] = Р2/гС2. ПРеДположим, что 2 < й < и, и для любой цепной дроби [Ьо,бы...,6ь] и любого 2 О < с < й справедливо утверждение о том, что [Ьо,Ьы...,Ьд] = р,'/д', где Р' и о' определены способом, аналогичным (а)-(с), но для цепной дроби [Ьо, Ьы.,,,бь]. Тогда [Со,Сы..., Сь, Сьес] = [СО,.Сы...,Сь ы [Сь; Сь.ьс]] (по теореме 7.10) = [6.;6,,...,6,, 6,], 1 где Ь, = С, при О < С < й — 1 и Ьь = [Сь, Сьег] = Сь + †. Таким образом, в силу индуктивного предположения Ь„+ ' [С , , ] Рь 1 ь Рь 2 хе †" + чх-2 312 ГЛАВА 7.
Теория чосел Поскольку Ь, = гг при 0 < г < й — 1, имеем, что для таких г р; = р', и 9г = д,'. Подставляя соответствующие выражения для Ью р', и д,', получаем ) +Рь-г га+ 1 1 ) + Яь-г гьч-г) (Рь — гта + Рь-г) + Рь-г/гьч-г (Чь — ~ь + 9ь-г) + чь-г/та+ Рьгь+г + Рь-г Рьч-г ВАч-г + 9ь-г 9ь+г Следовательно, по индукции, [Со, гы..., Сь] = рь/дь при 0 < й < и. Числа рь и дь (теорема 7.11) определены вне зависимости от того, что они могут быть использованы как числитель и знаменатель выражения, равного й-ой подходящей дроби.
Рекурсивное отношение, заданное теоремой 7.11, обеспечивает быстрый способ вычисления подходящих дробей для заданной цепной дроби, поскольку числитель р, и знаменатель д, можно вычислить одновременно и достаточно пРосто. НапРимеР, длЯ х = [ — 4;2,5,2, Ц = [~о,сг,сг,гз,г4] подходащие дроби можно вычислить согласно приведенной ниже таблице: Рь/Чь Так что х = — 124/35, т.е, числу, породившему цепную дробь [ — 4;2,5,2,1] (см. раздел 5.1). Благодаря рекурсивному способу задания цепных дробей, имеется значительное количество соотношений, связывающих подходящие дроби через числители и знаменатели, рь и дь, введенные теоремой 7.11.
Чтобы запись этих соотношений сделать справедливой при к = О, зачастую удобно определять рь и Вь при й = — 1, положив и — г =1; д г — — О. Таким образом, р, = ро1, +р г = Со1г + 1 и ог — — оотг + о г = 1 ~г + 0 = ~,, как в теореме 7.11. ТЕОРЕМА 7.12. Если [го,ты...,г„] — конечная цепная дробь, где г, — действительные числа, рь и 9ь — заданы теоремой 7.11, тогда а) рябь г — рь гг7ь=( — 1)" 'приО<й<п; — 4 2 5 2 1 р,, с,+ [то' ты, тьег]— и- ~та+ — 4 (-4)(2) + 1 = -7 (-7)(5) + (-4) = -39 — 39)(2) + ( — 7) = — 85 ( — 85)(1) + ( — 39) = — 124 1 2 (2) (5) + 1 = 11 (11)(2) + 2 = 24 (24)(1) + 11 = 35 -4/1 -7/2 -39/11 -85/24 -124/35 РАЗДЕЛ 7.б. Подходящие дроби 313 Ро Р2 Р4 — « — — < Чо Ч2 Ч4 а подходящие дроби нечетного порядка образуют убывающую последовательность, т.е.
Р1 Рз Рз — » — — > Ч1 Чз Ч5 Кроме того Р21 < [ [ < Ргсе1 Ч21 Ч2с е1 при О < 2 < [и/2)' и О < 1 < [(и — 1)/2), где слева равенство имеет место, когда и четное, а справа равенство имеет место, когда и нечетное. д) Если дробь [1о, .й„..., 8„] — простая, то Чь > й при О < й < и. е) Если дробь [го, 81,..., тп[ — простая, то Ч» < Чь4.1 при 1 < й < и — 1 и Чо < Ч1. ДОКАЗАТЕЛЬСТВО. а) При й = 1 р1до — род1 = (йой1+1)(1) — тот1 = 1 = ( — 1)' по теореме 7.11.
Пусть 2 < т < и и допустим, что формула в части (а) справедлива при й = гп. Показано, что формула имеет место при й = т+ 1. Опять, используя теорему 7.11, имеем Рт1-1$п Ртдт1-1 (Ртст4-1 + Рт-1)Чт Рпс(дттте1 + Чт — 1) Рт — 1$п Ртдт — 1 = ( 1)(Рпсдт-1 Р и — 1дпс) = 1)( 1)сп-1 ( 1)(т4-1)-1 Таким образом, формула в части (а) имеет место при 1 < й < п. Также род 1— Чор-1 = ~о Π— 1 1 = — 1 и формула справедлива при й = О. б) Утверждение теоремы следует из части (а), если в соответствующем равенстве при й > 1 произвести деление на Чьдь в) Если й > 2, то по теореме 7.11 Рь = Рь-11ь + Рь-2,' Ч1с = Чь-1сй + Чь-2. Умножение первого из равенств на Чь 2, а второго — на рь 2 дает Р1Чь-2 = Рь-1дь-21ь + Рь-2дь-2', Ч1Рь — 2 = Чь — 1Рь — 21ь + Чв — 2Рь — 2.
Вычитая второе равенство из первого, получаем б) Рь Рь-1 Чь Чй-1 Рй Рй-2 в) — —— Чй Чь — 2 г) Подходящие ность, т.е. ( 1)й-1 при 1<А<и; Чьдй — 1 (-1) ть )1с при 2 < й < и.. Чйдь-2 дроби четного порядка образуют возрастающую последователь- Рьдь-2 — ЧьРь-2 = (Рь-1дь-2 — Рь-2дь-1)11п 314 ГЛЯВА 7. Теория чисел Теперь, учитывая утверждение в части (а), получаем рьЧь 2 — Чьрь 2 = ( — 1)1~ 11 Сь = ( — 1) ( — 1) ~та = ( — 1)~2ю Разделив на ЧьЧь 2 > О, полУчаем желаемый РезУльтат: Рь Рь — 2 ( — 1) гь Чь Чь-2 ЧьЧь-2 г) Если 2 < к < и и к — четное, то и — 2 тоже четное и й — 2 > О. Поэтому ( — 1)ь = 1 и из утверждения в части (в) вытекает, что Рь Рь-2 гь >О, Чь Чь-2 ЧьЧь-2 поскольку 2ь и ЧьЧь 2 положительные при й > 1.
Если 3 < )с < и и и — нечетное, то й — 2 также нечетное и к — 2 > 1. В этом случае ( — 1)" = — 1, так что из утверждения в части (в) вытекает, что Ре 2 (-1)2, <О, Чь Чь — 2 ЧьЧь-г так как аь и ЧьЧь 2 положительны пРи к > 3. Если и нечетное, то согласно (б) — > —, так что [1о,11,12,...,2„) = Чп Чл-1 р„/Ч„больше, чем наибольшая подходящая дробь четного порядка, Р„1/Ч„ Если и четное, то — <:, так что (го,11,22,...,2„) = р„/Ч„меньше, чем Рп Рп — 1 Чл Чл-1 наименьшая подходящая дробь нечетного порядка, р„,/Ч„,.
Доказательство пунктов (д) и (е) оставляем за читателем. Подходящие дроби для х = ( — 4; 2, 5, 2, Ц вычислены ранее в данном разделе и приведены в таблице. Подводя итог этим результатам в контексте части (г), находим, что Ро/Чо < Р2/Чз < Р4/Ч4 х < Рз/Чз < Р1/Ч1 -4/1 < -39/11 < -124/35 = х < -85/24 < -7/2. Непосредственным вычислением определяем также, что РзЧг — Р2Чз = ( — 85)(11) — ( — 39)(24) = ( †9) — ( †9) = 1.
Значение теоремы 7.12 состоит в том, что она точно устанавливает, что последовательные и взаимно исключающие подходящие дроби могут отличаться не более, чем на величину, обратно пропорциональную "знаменателям" подходящих дробей, а также, что подходящие дроби альтернативно больше, чем (со',11,С2,...,С„), и меньше, чем (1о',11,12,...,с !. Практический интерес представляют некоторые отношения Рь/Чь числителей и знаменателей подходящих дробей.
Эти отношения приведены в следующей теореме, доказательство которой предоставляется читателю. РАЗДЕЛ 7.5. Подходящие дроби 315 ТЕОРЕМА 7.13. Для конечной цепной дроби [!о,!ы!з,..., 1„] а) дь/дь 1 = [ть, .!ь ы..., тз, !1] при 1 < !г < п. б) Если !а Ф О, то рь/рь-з = [ть;ть-1 . !ыто] при 1 < гг < п. в) если Фо = О, то рь/рь-1 = [ть; !х-ы ~та, ег] при 2 ( й ( и. ° УПРАЖНЕНИЯ 1. Докажите теорему 7.11 при условии, что дь ) О при О < и < и. 2. Вычислите подходящие дроби для а) [2;5,1,2,4]; б) [2;5,1,2,3,Ц; в) [5;1,2,3]; г) [О; 5, 1, 2, 3]; д) [ — 5;3,8,21.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
