Главная » Просмотр файлов » Дж. Андерсон - Дискретная математика и комбинаторика (2004)

Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 53

Файл №1127091 Дж. Андерсон - Дискретная математика и комбинаторика (2004) (Дж. Андерсон - Дискретная математика и комбинаторика (2004)) 53 страницаДж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091) страница 532019-05-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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.

Характеристики

Тип файла
DJVU-файл
Размер
7,96 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6361
Авторов
на СтудИзбе
310
Средний доход
с одного платного файла
Обучение Подробнее