42. [НМ10\ Выразите биномиальный коэффициент через бета-функцию, определенную выше (Это позволит распространить определение биномиальных коэффициентов на все действительные значения к )

43. [НМ20] Покажите, что В(1/2,1/2) = тг (Тогда на основании упр 41 можно заключить, что Г(1/2) = v/tF )

44. [НМ20] Исгюльзуя обобщение биномиальных коэффициентов, предложенное в vnp 42, покажите, что

45. [НМ21] Используя обобщение биномиальных коэффициентов, предложенное в упр 42, найдите hmr-+oo (1)/*

► 46. [М21] Используя формулу Стирлинга и соотношение 1 2 5-(7), найдите приближенное значение ") для больших х иу В частности, найдите приближенное значение () для больших п

47. [М21] Покажите, что для целых к

Приведите ботее простую формулу для частного случая г = -1/2 * 48. [М25] Покажите, что

2фк)к + х х{х + \) {х + п) х("+-)

если знаменатели не обращаются в нуль [Обратите внимание, что эта формула дает обратное значение биномиального коэффициента а также раз;южение 1/1;(ж -i-1) (х п) на элементарные дроби ]

49. \М20] Покажите, что из тождества (1 -- хУ = (1 - xYil - х)~ следует соотношение для биномиальных коэффициентов

50. [М20] Докажите формулу Абеля (16) для частного случая х + у - Q

51. [М21] Докажите формулу Абеля (16) следующим способом запишите у в виде у = {х-{-у)-х, разложите правую часть по степеням {х+у) и примените результат предыдущего упражнения

52. [НМ11\ Докажите, что биномиальная формула Абеля (16) не всегда справедлива, если п не является неотрицательным целым числом Для этого вычислите значение правой части при п = X = -1, !/ = 2 = 1

53. [М25\ (а) Докажите следующее тождество индукцией по т, если m и п - целые

£(1) J(-+ = (пг1)(п - пг)(; J J

(b) Используя важные соотношения из упр 47,

/-1/2\ (-1Г/2п\ /1/2\ (-1)"- /2п\ (-1)"- /2п-1\ \ п ) 22" Vn/ \ п) 22»(2п-1) V п У 22"-i(2n-l)V п )

покажите, что следующую формулу можно получить как частный случай тождества из

п (а)

онжоь frS )\п~к)2к-1~ 2п {т )\ п-т )2{п )

(Это значительно более общий результат, чем соотношение (26) для случая г = - 1, s = О, t = -2.)

54. [М21] Рассмотрите треугольник Паскаля (см. табл 1) как матрицу Найдите обратную матрицу.

55. [М21] Рассматривая каждый треугольник Стирлинга (см. табл. 2) в качестве матрицы, найдите обратные к ним матрицы.

56. [20] (Комбинаторная числовая система.) Для каждого целого п = О, 1, 2, ..., 20 найдите три целых а, Ь, с, таких, что п = (") + (j) + (3) и О < а < 6 < с. Как можно продолжить эту последовательность для больших значений п?

► 57. [М22] Покажите, что коэффициент От в формуле Стирлинга 1.2.5-(12), в которой он пытался обобщить факториальную функцию, равен

58. [М23] Используя обозначения соотношения (40), докажите "д-номиальную теорему": (l + x)(l + qx).. (l + 9"") = E(fc) 1

k(k-l)/2k

Найдите qr-номиальные обобщения фундаментальных тождеств (17) и (21). 59, [М.25] Последовательность чисел Апк, п > О, к > О, удовлетворяет соотношениям Апо = 1, Аок = Sok, Апк = А(п-1)к + А(п-1)(к-1) + Ц) для пк > 0. Найдите Апк-► 60. Как вы уже знаете, (1) - это число сочетаний из п элементов по к, т. е. чис-

ло способов выбора к различных элементов из п-элементного множества. Сочетания с повторениями отличаются от обычных сочетаний только тем, что один элемент можно выбрать произвольное число раз. Таким образом, для сочетаний с повторениями список (1) следует продолжить, чтобы включить в него ааа, ааЬ, аас, aad, аае, abb и т. д. Итгьк, сколько существует сочетаний с повторениями из п объектов по к?

61. [М25] Вычислите сумму

получив тем самым формулу, парную для (55).

► 62. [М23] В тексте приводятся формулы для сумм, содержащих произведение двух биномиальных коэффициентов. Для сумм, содержащих произведение трех биномиальных коэффициентов, наиболее полезными будут тождество из упр. 31 и следующая формула:

Е, .,.kfl + m\/m-\-n\/n-\-l\ (l-i-m-\-ny. , . .

[l + k)L + k)L + k)= ПтЫ ™.-"0-

(к пробегает как положительные, так и отрицательные значения.) Докажите это тождество. [Указание. Существует очень короткое доказательство, которое начинается с применения упр. 31.]

63. [М50] Если I, т и п - целые и п > О, докажите, что

В-»- (Г.:) (;) С) (-"г-г)=-»(::;) L--:.,y

* 64. [М20] Покажите, что { } -это число способов разбиения множества из п элементов на т непустых непересекающихся подмножеств. Например, множество {1,2,3,4} можно

разбить на два подмножества {j} = 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).

65. [НМ35] (Б. Ф. Логан (В. F. Logan).) Докажите формулы (59) и (60).

66. [Af.2P] Пусть п - положительное целое число, а ж и у - действительные числа, удовлетворяющие неравенству п<у<х<у+1. Тогда < (J < (J+J) = + (l), так что существует единственное действительное число z, такое, что

Докажите, что

[Указание. Рассмотрите представление („,) = (+) + j: {пЛ)С~1+\)] ► 67. [Af.20] Часто возникает необходимость в получении оценок для биномиальных коэффициентов. Докажите следующее неравенство, представляющее оценку сверху (заметим, что ее легко запомнить):

68. [М25] (А. де Муавр (А. de Moivre).) Докажите, что для целого неотрицательного п Х:()/(1-p)"-=fc-np = 2[пр1(;)рГ"1(1-р)"+-Г"1.

1.2.7. Гармонические числа

В дальнейшем для наг будет иметь бсшьшое значение следующая сумма:

я„ = 1 + 1 + 1 + ... + 1 = ;1, п>о. ш.

Она не очень часто встречается в классической 1,1атематике, и для нее не существует стандартного обозначения. Но в анализе алгоритмов она возникает почти на каждом шагу, поэтому будем использовать для нее обозначение Я„. (Помимо Я„, в математической литературе для этой суммы используются также обозначения Л„, Sn и ф{п + 1) + f. Буква Я обозначает "harmonic" ("гармонический"); Я„ будем называть гармоническгши числами, так как (1) обычно называют гармоническим рядом.)

На первый взгляд может показаться, что при больших п значение суммы Я„ не слишком велико, так как мы постоянно добавляем все меньшие и меньшие числа. Но на самом деле можно показать, что Я„ может достигать сколь угодно больших значений, если взять достаточно большое п, поскольку

Я2".>1+у. (2)

Эту оценку снизу можно получить, если заметить, что для т >0