AOP_Tom1 (1021736), страница 23
Текст из файла (страница 23)
[М20] Покажите, что из тождества (1+ х)" = (1 — хэ)" (1 — х) " следует соотношение для биномиальных коэффициентов 60. [М20] Докажите формулу Абеля (16) для частного случая х + у = 0 61. [М21] Докажите формулу Абеля (16) следующим способом запишите у в виде у = (х+у) — х, разложите правую часть по степеням (х+у) н примените результат предыдущего упражнения 62. [НМ/1] Докажите, что биномиальная формула Абеля (16) не всегда справедлива, если и не является неотрицательным целым числом Для этого вычислите значение правой части при и = х = — 1, у = х = 1 63. [Мхе] (а) Докажите следующее тождество инлукцией по тп, если тп и и — целые Е(;)(.',)(-- " ж"».--)(.;,)(.' ) »=е (Ь) Испол»зги важные соотношения из упр 47, ( 1/г) (-1)" (2 ) (1/г) (-1)"-' (2 ) (-Ц"-' (г -1) покажите, что следующую формулу можно получить как частный случай тождества из п (а) ~- (2к — 1) (2п — 2к) -1 и — тп(2тп) (2и — 2тп) 1 (2и) (Это значительно более общий результат, чем соотношение (26) для случая г = — 1, я = О, 1 = — 2.) 54.
[М21) Рассмотрите треугольник Паскаля (см. табл 1) как матрицу Найдите обратную матрицу. 55. [М31) Рассматривая каждый треугольник Стирлингв(см. табл. 2) в качестве матрицы, найдите обратные к ним матрицы. 56. [20) (Комбинаториая числовая система.) Для каждого целого и = О, 1, 2, ..., 20 найдите три целых а, 6, с, таких, что и = (1) + (") + (') и 0 < а < Ь < с. Как можно продолжить эту последовательность для ббльших значений и? ь Ьт.
[М23) Покажите, что коэффициент а в формуле Стирлинга 1.2.5-(12), в которой он пытаэся обобщить факторнальную функцию, равен — ( — 1) ( ) 1пй. е>! 58. [МЗ3) Используя обозначения соотношения (40), докажите "а-номиэльную теорему": (1+кН1+Чх).. (1+4" 'к)=~ („) О"~ Найдите а-номиальные обобщения фундаментальных тождеств (17) и (21). 59. [МЯ5] Последовательность чисел А„ю и > О, Ь > О, удоюеетворяет соотношениям А о = 1, Ась = бою А„е = Аы,1е + Ат пы 0 + (") для пй > О.
Найдите Ааы ь 60. [Мйу] Как вы уже знаете, ("„) — это число сочетаний из и элементов по Ь, т. е. число способов выбора )е различных элементов из и-элементного множества. Сочетания с повторениями отличаются от обычных сочетаний только тем, что один элемент можно выбрать произвольное число раз. Таким образом, для сочетаний с повторениями список (1) следует продолжить. чтобы включить в него ааа, аа6, аас, аа4, аае, аЬЬ и т. д. Итак, сколько существует сочетаний с повторениями нз и объектов по?е? 61. [М25] Вычислите сумму получив тем самым формулу, парную для (55).
ь 62. [М23) В тексте приводятся формулы для сумм, содержащих произведение двух биномиальных коэффициентов. Для сумм, содержащих произведение трех биномнальных коэффициентов, наиболее полезными будут тождество из упр. 31 и следующая формула: ( це(1+ т)(т+ п) ( и+1) (1+ т+ и).' 1 т и > 0 (6 пробегает как положительные, так и отрицательные значения.) Докажите это тождество. [Указание.
Существует очень короткое доказательство, которое начинается с применения упр. 31.) 63. [МЯО] Если 1, т и и — целые и и > О, докажите, что ь 64. [М30] Покажите, что (" ) — это число способов разбиения множества из и элементов на т непустых непересекающихся подмножеств. Например, множество (1,2,3,4) можно разбить па два подмножества (э) = 7 способами.
(1,2,3Ц4); (1,2,4Ц3); (1.,3,4Ц2); (2,3,4Ц1); (1,2Ц3, 4); (1,3Ц2,4); (1,4Ц2, 3), Указание. Используйте соотношения (46). 66. [НМ35] (В. Ф. Логан (В. Р. Ьобап).) Докажите формулы (59) и (60), 66, [МЯУ] Пусть и — положительное целое число, а х и у — действительные числа, удовлетворяющие неравенству и < у < х < у+ 1. Тогда („"„,) < ( +,) < (я++',) = („я+,) + („"), тэк что существует единственное действительное число я, такое, что Докажите, что (л) < ( е)" где и > а > О.
68, [Мха] (А. де Муавр (А. Йе Мо!тге).) Докажите, что для целого неотрицательного и ( )р (1 — р)" ]й — пр] = 2[пр] ~ )рЫЯ1(1 — р) а' 1.2.7. Гармонические числа В дальнейшем для наг будет иметь большое значение следующая сумма: 1 1 1,~" 1 Н„= 1+ — + — + ". + — = з —, и > О. 2 3 и а. й' а=1 Она не очень часто встречается в классической математике, и для нее не существует стандартного обозначения.
Но в анализе алгоритмов она возникает почти на каждом шагу, поэтому будем использовать для нее обозначение Н„. (Помимо Н„, в математической литературе для этой суммы используются также обозначения Ая, Я„и ф(п + 1) + у. Буква Н обозначает япзгшоп1ся (агармоническийя); Н„будем называть гармоническими числами, так как (1) обычно называют гармоническим рядом.) На первый взгляд может показаться, что при больших и значение суммы Н„не слишком велико, так как мы постоянно добавляем все меньшие и меньшие числа.
Но на самом деле можно показать, что Н„может достигать сколь угодно больших значений, если взять достаточно большое п, поскольку На > 1+ —. 2 (2) Эту оценку снизу можно получить, если заметить, 1 1 Нз-~~ = Нз-+ + — + 2ы+1 2™+2 1 1 что для гп > О 1 + 2"'+" 1 1 2'я+' — Нз-+ 3 [Указание. Рассмотрите представление („,) = („*+~) + 2 (* ")(* * ~+~).] я 67. [М20] Часта возникает необходимость в получении оценок для биномиальных коэффициентов. Докажите следующее неравенство, представляющее оценку сверху (заметим, что ее легко запомнить): Поэтому, когда гп увеличивается на 1, левая часть неравенства (2) увеличивается по меньшей мере на —. 1 2' Но мы нуждаемся в более ппдробной информации о Н„, чем та, которую дает неравенство (2).
Приближенная оценка Н„хорошо известна (по крайней мере, в математических кругах); она дается следующей формулой: 1 1 1 1 Нд =1пп+(+ — — — + — — е, 0 (с ~ 2п 12пз 120п4 252п' (3) Здесь у = 0.5772156649... †э посп1олппол Эйлера, введенная Леонардом Эйлером в рабюте Сотшепгагй Аеас(. ЯН. 1тр. Ре(. 7 (1734), 150-161. Точные значения Н„ для малых п, а также значение з с точностью до 40-го десятичного знака, приведены в приложении А. Формула (3) будет выведена в разделе 1.2.11.2. Таким образом, Н„является достаточно близким к натуральному логарифму п. В упр. 7, (а) будет показано, что Н„и ведет себя в некоторой степени, как логарифмическая функция.
В этом смысле по мере увеличения п функция Н„стремится к бесконечности очень медленно, так как сумма 1 1 1 14 — + — +" +— (4) 2" 3' п' остается ограниченной для всех п, если показатель г †э любое действительное число, которое больше единицы (см. упр, 3), Сумму (4) обозначим через Н„. (г) Если показатель т в (4) болыпе или равен, то величина Нь лов< ~ьно близка ч (г) к своем1 максимальному значению Н для всех п.
кроме совсем малы» Величина (с) „ Н > хорошо известна в математике как дзегпа-4упкцил Рьмаиа. (~) Н(г) = аг) = Е— 1 (6) ьк1 Если г- — четное целое число, то известно, что значение Дг) равно Н(,,') = — (Н,! —,, целое г(2 > 1., 1 (2х)" (61 г! где ̈́— это число Бернулли (см.
раздел 1.2.11.2 и приложение А). В частности, (7) 6 90' 945' 9450 Эти результаты получены Эйлером; подробное обсуждение данной темы, а также доказательства формул приводятся в СМай, 36.5. А теперь рассмотрим несколько важных сумм, в которых участвуют гармони- ческие числа. Во-первых, " Нь — — (и + 1)̈́— п. ь=г Это получается в результате простой замены индекса суммирования: ь ь ЕЕ; ь=г,=з 1 ~ п+1 — у р=1 ь=х з=! Из данного равенства и того факта, что Нс —— х, следует Сумма справа является частной суммой бесконечного рцца для 1п(1/(1 — 1/(х+1))) = 1п(1+1/х), этот рцд сходится при х > О, разность между 1й(1+1/х) и частной суммой равна 1 1 1 1 й(х + 1)ь (и + 1)(х + 1)"'"' ~~- (х + 1)ь (й + 1)(х + 1)"х Таким образом, мы доказали следующую теорему.
Теорема А, Если х > О, то где О < е < 1/(х(и + 1)). $ УПРАЖНЕНИЯ 1. [01] Чему равны Но, Нс и Нзо 2. [10] Покажите, что, несколько видоизменив простое доказательство, которое было использовано в тексте для вывода неравенства Но > 1+ т/2, можно показать, что Нс < 1+т 8. [М81] Обобщите доказательство, использованное в предылущем упражнении, и покажите, что для г > 1 сумма Н„остается ограниченной для всех и Найдите верхнюю О1 грань 4. [10] Какие из следующих утвервсдений верны для всех положительных целых и.
(а) Нп <1пй; (Ь) Нв >1пй (с) Нл >1пй+7 б. [15] Пользуясь таблицамн из приложения А, укавсите значение Нюооо с точностью до 15-го десятичного знака б. [М15] Докавсите, чта гармонические числа непосредственно связаны с числами Стирлинга, которые рассматривались в предыдущем раэцеле, т е 7. [М21] Пусть Т(пс, и) = Н + ̈́— Н „(а) Покажите, что если т или и возрастает, то Т(т,и) не возрастает (в предположении, что пс и п лоложительны) (Ь) Вычислите минимальное и максимальное значения Т(т, и) дпя т, и > О 8. [НМИ] Сравните сумму (8) с 2,",, 1и 1с, найдите их разность как функцию от и 9. [МИ] Теорема А применима только для х > О Чему равна рассматриваемая сумма при х = -1о 10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
