Д. Кнут - Искусство программирования том 1 (1119450), страница 22
Текст из файла (страница 22)
Ь. [05] С помощью треугольника Паскаля объясните тот факт, что 11 = 14641. 8. [10] Треугольник Паскаля (см. табл. 1) можно продолжить во всех направлениях с помощью формулы сложения (9). Добавьте к табл. 1 три строки сверху (т. е. для г = -1, -2 и — 3). 7.
[18) Если и — фиксированное положительное целое, то при каком значении 6 ("„) принимает максимальное значение? 8. [00) Какое свойство треугольника Паскаля отражено в "свойстве симметрии" (6)? 9. [01] Чему равно („")? (Рассмотрите все целые и.) ь 10, [М85] Пусть р — простое число. Покажите следующее. а) ( ) ав Я (по модулю р). р р Ь) ( ) гн0(помодулюр)для1<6<р — 1. /р~ ~йу ур-1~ с) ( ) ги (-1) (по модулю р) для 0 < й < р — 1. 4) ~ ] ав0 (по модулю р) для 2 < 8 <р — 1.
ур+15 е) (Э. Люка (Е. 1псаэ), 1877.) ( ) ьч ( ) ( ) (по модулю р). 1) Если в системе счисления с основанием р числа и и 6 представляются в виде то ( )и( )...( )~ ) (помцвулюр). ь 11. [М80] (Э. Куммер (Е. Кцпппег), 1852.) Пусть р — простое число. Покажите, что если р" делит а р"ч ~ — нет, то и равно числу перекосов, которые выполняются при сложении чисел а н 6 в системе счисления с основанием р. [Указание. См. упр. 1.2.5-12.] 12. [М88] Существуют ли целые положительные числа и, для которых все ненулевые элементы в и-й строке треугольника Паскаля являются кечеп1нмми? Если да, найдите все такие и.
13. [М13] Докажите формулу суммирования (10). 14. [М81] Вычислите сумму ~» /с~. 15. [М15] Докажите биномиальную формулу (13). 16. [М15] Для положительных целых и и?о докажите свойство симметрии ь 17. [М18] На основании соотношения (15) и тождества (1 + х)"~' = (1 + х)" (1 + х)' докажите формулу Чжу-Вандермонда (21). 18. [М15] На основании соотношений (21) и (б) докажите (22). 19. [М18] Докажите (23) по индукции.
20. [М80] Докажите (24) с помощью (21) и (19), а затем покажите, что еще одно применение формулы (19) дает (25). ь 21. [М05] Обе части равенства (25) — зто многочлены по з; почему это равенство не является тождеством по в? 22. [МОО] Докажите (26) для частного случая в = и — 1 — г + ай 23. [М18] Предполагая, что (26) выполняется для (г, з,в, и) и (г, в — З, 1, п — 1), докажите его для (г, в + 1, Ф, и).
24. [М15] Объясните, как объединить результаты двух предыдущих упражнений для доказательства (26). 25. [НМ80] Пусть многочлен А„(х,в) определяется формулой (30). Пусть в = х'+ — х'. Докажите, что ],з Аь(г,в)з~ = х', если з достаточно мало. [Замечание, При 4 = 0 этот результат, по существу, совпадает с бнномиальной теоремой, поэтому приведенное соотношение является важным обобщением биномиальной теоремы. При доказательстве тождества биномиальную теорему можно считать известной.] Указание.
Начните с тождества ~( 1) ( )( к ) —.з мбзо. 26. [НМ85] Используя предположения из предыдущего упражнения, докажите, что 27. [НМ21] Решите задачу из примера 4, приведенного в тексте раздела, используя результат упр. 25, и на основании двух предыдущих упражнений докажите (26). [Указание. См. упр. 17.] 28. [М85] Докажите, что (г+З!о)(в Гк) ~, (г+в л) ь в к>о если п — неотрицательное целое число.
29. [МЯО] Покажите, что тождество (34) — это просто частный случай общего тождества, доказанного в упр. 1.2.3 — ЗЗ. ь 30. [М84] Покажите, что существует более удачный (по сравнению с приведенным в тексте раздела) способ решения примера 3, который состоит в преобразовании суммы с применением соотношения (26). ь 31. [МЯО] Выразите сумму (пв — г+в) (и+г — в) ( г+й ) 42. [НМ10) Выразите биномиальный коэффициент ([) через бета-функцию, определенную выше (Это позволит распространить определение биномнальных коэффициентов на все действительные значения (с ) 48.
[НМ20] Покажите, что В(1/2,1/2) = л (Тогда на основании упр 41 можно заключить, что Г(1/2) = ь/я ) 44. [НМ20] Используя обобщение биномиальных коэффициентов, предложенное в упр 42, покажите, что 4$. [НМ21] Используя обобщение биномиальных коэффициентов, предложенное в упр 42, найдите !пп,~~ [")/г ь 46. [М21] Используя формулу Стирлинга и соотношение 1 2 5-(7), найдите приближенное значение (*+") для больших х и у В частности, найдите приближенное значение (~в) для больших и 47.
[М21] Покажите, что для целых к ([)( -,'") -(':и",")/" =([;и )/" Приведите более простую формулу для частного случая т = — 1/2 ь 48. [М20] Покажите, что С-/и'1( — ') ' и) 1 ~;;'1 й/ 2+х х(х+ Ц (х+ „),(.+*) если знаменатели не обращаются в нуль [Обратите внимание, что эта формула дает обратное значение бнномиального коэффициента а также разложение 1/х(х+ 1) (х т и) на элементарные дроби ] 49. [М20] Покажите, что из тождества (1+ х)" = (1 — х~)" (1 — х) " следует соотношение для биномиальных коэффициентов 80. [М20] Докажите формулу Абеля (1б) для частного случая х+ у = 0 81.
[М21] Докажите формулу Абеля (16) следующим способом запишите у в виде у = (х+у)-х, разложите правую часть по степеням (х+у) и примените результат предыдущего упражнения 82. [НМ11] Докажите, что биномиальная формула Абеля (1б) не всегда справедлива, если и не является неотрицательным целым числом Для этого вычислите зна ~ение правой части при и = х = — 1, у = х = 1 88. [М20] (а) Докажите следующее тоястество ицлукцвей ио т, если т и и — целые (Ь) Используя важные соотношения из упр 47, ( 1) 2 ) (1/2) ( Ц»- (2 ) ( 1)ч-~ покажите, что следующую формулу можно получить как частный случай тождества из п (а) ~(22 — 1) (2и — 2Й) — 1 и — т(2т) (2и — 2т) 1 (2и) (Это значительно более общий результат, чем соотношение (26) для случая г = -1, я = О, с= — 2,) 54. [Мй?] Рассмотрите треугольник Паскаля (см. табл 1) как матрицу Найдите обратную матрицу. 55.
[М31] Рассматривая каждый треугольник Стирлинга (см. табл. 2) в качестве матрицы, найдите обратные к ним матрицы. 56. [30] (Комбинашарная числовая снсшсма.) Для каждого целого и = О, 1, 2, ..., 20 найдите трн целых а, Ь, с, таких, что и = (;) + (~) + (') н О < а < Ь < с. Как можно продолжить эту последовательность для ббльших значений и? ь 57. [М33] Покажите, что коэффициент а в формуле Стирлинга 1.2.5-(12), в которой он пытался обобщить факторнальную функцию, равен 56. [МЗЯ] Используя обозначения соотношения (40), докажите "д-номиальную теорему" .' Найдите д-номивльные обобщения фундаментальных тождеств (17) и (21), 59. [Мйб] Последовательность чисел А„ы и > О, Ь > О, удовлетворяет соотношениям Ане = 1, Ащ = беы Анэ = АШ Оэ -~- Аш ОЫ О+ (~ь) для ий > О.
Найдите Анм ь 60. [МЗЭ] Как вы уже знаете, (,") — это число сочетаний из и элементов по lс, т. е. число способов выбора Ь различных элементов из и-элементного множества. Сочсглания с иоеглореннямн отличаются от обычных сочетаний только тем, что один элемент можно выбрать произвольное число раз.
Таким образом, для сочетаний с повторениями список (1) следует продолжить. чтобы включить в него ааа, ааЬ, аас, аас(, аае, аЬЬ и т. д. Итак, сколько существует сочетаний с повторениями из и объектов по Й? 61. [Мйб] Вычислите сумму получив тем самым формулу, парную для (55). ° 62. [МЗЗ] В тексте приводятся формулы для сумм, содержащих произведение двух биномиальных коэффициентов. Для сумм, содержащих произведение трех биномиальных коэффициентов, наиболее полезными будут тождество из упр.
31 и следующая формула: (я пробегает как положительные, так и отрицательные значения.) Докажите это тождество. [Укаэаннс. Существует очень короткое доказательство, которое начинается с применения упр. 31.] 63. [МЗО] Если 1, ги и и — целые и п > О, докажите, что ь 64. [М80] Покажите, что ( " ) — это число способов разбиении множества из и элементов на ги непустых непересекающихся подмножеств. Например, множество (1,2,3,4) можно разбить иа два подмножества ( ) = 7 способами.
(1,2,3Ц4); (1,2,4ЦЗ); (1,3,4Ц2); (2,3,4Ц1); (1,2Ц3,4); (1, ЗЦ2,4); (1,4Ц2, 3). Указание. Используйте соотношения (46). 68. [ЛМУЗ] (Б. Ф. Логан (В. Е, Бабаи).) Докажите формулы (69) и (60). 66. [МЯУ) Пусть и--положительное целое число, а х и у — действительные числа, удовлетворяющие иеравеиству п < у < я < у+ 1. Тогда („"„,) < ( +,) < („"+,) ж („+" ) + („"), так что существует единственное действительное число г, такое, что и †1<я.
Докаясите, что © - '(-"')" гдеп>й>О. 68. [Муб) (А, де Муавр (А. Йе Мо1зте).) Докажите, что для целого неотрицательного и к©»"- ""-" -'" (~.",~) '""- "' '"' 1.2.7. Гармонические числа В дальнейшем для наг будет иметь большое значение следующая сумма: 1 1 1 ~ 1 Н„=1+-+-+ "+ — ж~'-, п>О. Она не очень часто встречается в классической математике, и для нее не существует стандартного обозначения. Но в анализе алгоритмов она возникает почти на каждом шагу, поэтому будем использовать для нее обозначение Н„. (Помимо Н„, в математической литературе для этой суммы используются также обозначения Ь„, Я„и ф(п + 1) + 7.
Буква Н обозначает кйагшоп!са ("гармоиическийя); Н„будем называть гармоническими числами, так как (1) обычно называют гармоническим рядом.) На первый взгляд может показаться, что при больших и значение суммы Н„не слишком велико, так как мы постоянно добавляем все меньшие и меньшие числа. Но на самом деле можно показать, что Н„может достигать сколь угодно больших значений, если взять достаточно большое и, поскольку Нг > 1+ —.
т 2 (2) Эту оценку снизу можно получить, если заметить, что для т > О 1 1 1 Нг е = Нг- + 2'" + 1 2"' -~ 2 2"'~-' + — + + 1 1 1 2 е! 2 +1 2уп+1 >На + + + + — =Нз +-'. а' [Укагаиие. Рассмотрите представлеиие („+,) = („*+',) + 2 > („* „)(* „* ,'+ ).] ь 67. [Мйб) Часто возникает необходимость в получении оценок для биномиальных коэффициентов.
Докажите следующее неравенство, представляющее оценку сверху (заметим, что ее легко запомнить): Поэтому, когда т увеличивает9я на 1, левая часть неравенства (2) увеличивается по меньшей мере на —.. 1 Но мы нуждаемся в более подробной информации о Н„, чем та, которую дает неравенство (2). Приближенная оценка Н„хорошо известна (по крайней мере, в математических кругах); она дается следующей формулой: 1 1 1 1 Н„= 1п и+ 7+ — — — + — е, 0 < с < — „ (3) 2п 12пз 120и4 252пэ Здесь 7 = 0.5772156649...— это пос1пояииал Эйлера, введенная Леонардом Эйлером в работе Соттепсаг11' Асай).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
