ki!fc2!...fcn! \ V- J V 2! У Л n\ J •

для u{x + z), a Diw/j\ - коэффициент при j/- в выражении для w{u + y). Отсюда следует, что коэффициент при г" в формуле для w(u(x + г)) равен

„! ,•! 2

ki+2k2+ +пк„=п ki,k2, ,кп>0

Формула Арбогаста долгие годы оставалась забытой, а затем была вновь независимо открыта Ф. Фаа ди Бруно (F. Faa di Bruno) [Quarteriy J. Math. 1 (1857), 359-360], который заметил, что производную можно также представить в виде определителя

D" = det

где Uj - (Diu) Du- Обе части этого соотношения представляют собой дифференциальные операторы, которые нужно применить к w- Обобщение формулы Арбогаста для функции многих переменных, а также список ссылок на другие работы по данной теме можно найти в статье И. Дж. Гуда (I. J. Good) Annals of Mathematical Statistics 32 (1961), 540-541.

22. Выдвигаем следующую гипотезу: lim„ >c»(ra + хУ-/{п\п) - 1. Она справедлива для целых Х- Например, если х положительно, то выражение под знаком предела равно

(l-l-l/n)(l--2/n)...(l-l-x/n)

и при га, стремящемся к бесконечности, оно безусловно стремится к единице. Если предположить также, что х\ = х{х - 1)!, то из гипотезы немедленно следует, что

,. (га-1-х)! ... (х + 1)...(х + га)

1 = hm --;-- = х! hm --~---,

п-*оо nin n-*Dc га! га

а это эквивалентно определению, данному в тексте.

23. Из (13) и (15) следует, что z (-г)!Г(г) = lim„,-.cx. Y[n=ii " г/га)-! + г/га)".

24. raVra! = WkZlik + if/k Щ е; ra/ra+i = WkZl k+/ik + 1)*+ < П":[ e".

25. x2i±2 - x-(x-m)-; x"""" = x"(x -m)". Из (21) следует, что эти правила справедливы также для нецелых m и га.

РАЗДЕЛ 1.2.6

1. га, так как каждое сочетание получается отбрасыванием одного элемента.

2. 1. Существует ровно один способ не выбрать ничего из пустого множества.

3. Это число равно 635 013 559 600.

4. 2" 5 7 17 23 • 41 43 47.

5. (10 + 1) = 10000 -I- 4(1000) -I- 6(100) -I- 4(10) -I-1.

е. г = -3: 1 -3 6 -10 15 -21 28 -36 ... г = -2: 1 -2 3 -4 5 -6 7 -8 ... г = -1: 1 -1 1 -1 1-1 1 -1 ...

7. При [га/2] либо при [га/2]. Из (3) следует, что при меньших значениях биномиальный коэффициент строго возрастает, а при больших убывает до нуля.

8. Если обозначить ненулевые элементы в строке ai, аг, ..., an, то они обладают свойством ajt = an - к.

9. Единице, если п положцтельно или равно нулю; нулю, если п отрицательно.

10. (а), (Ь) и (f) непосредственно следуют из (е); (с) и (d) следуют из (а), (Ь) и (9). Поэтому остается доказать (е). Рассмотрим () как дробь, которая задается соотношением (3), где и в числителе, и в знаменателе находится произведение сомножителей. Произведение первых к mod р сомножителей в знаменателе не делится на р; очевидно, что эти члены в числителе и знаменателе сравнимы с соответствующими членами биномиального коэффициента

/nmodp\ V к mod р J

которые отличаются на величины, кратные р. (Если рассматривать величины, не кратные р, то можно брать по модулю р и числитель, и знаменатель, так как если а = с, b = d и а/Ь, c/d-целые, то а/Ь = c/d ) Остается к - к modp сомножителей, каждый из которых входит в [к/р\ групп из р последовательных величин. В каждой группе содержится ровно одна величина, кратная р; остальные р - 1 сомножителей группы сравнимы (по модулю р) с (р - 1)!, поэтому они сокращаются в числителе и знаменателе. Остается рассмотреть в числителе и знаменателе [к/р] величин, кратных р. Разделив каждую из них нар, получим биномиальный коэффициент

( [{п-к mod р)/р]\ V [k/pi J

Если к modp < п modp, то этот биномиальный коэффициент равен

fln/pi\ \[k/pU

как и требуется. Если к mod р > п mod р, то другой множитель ( ) равен нулю. Таким образом, наша формула справедлива во всех случаях. [American J. Math. 1 (1878), 229-230; см также N. J. Fine, АММ 54 (1947), 589-592 ]

11. Если а = йгр + • • -Ь ао, Ь = Ьгр -\- -\- Ьо vi а -\- Ь = Сгр + + Со, то значение п (согласно упр. 1.2.5-12 и соотношению (5)) равно

(ао Ч-----Уаг+Ьо +----1- Ьг - со-----Сг)/(р - 1).

В результате одного переноса Cj уменьшается на р, а Cj+i увеличивается на 1, что дает по этой формуле суммарное изменение на 4-1. [Аналогичные утверждения справедливы для д-номиальных и фибономиальных (Fibonomial) коэффициентов; см работу Knuth, Wilf, Crelle 396 (1989), 212-219.]

12. Согласно любому из двух предыдущих упражнений п должно быть на единицу меньше степени 2. А если обобщить, то () не делится на простое число р, О < А; < п, тогда и только тогда, когда п = ар™ - 1, 1<а<р, то>0

"•-("Г)-Ч°Г)-Ч"Г)Ч"Г)

= ! п п{п + 1)(п + )(3п + Зп - 1)

5 2 3 30 15

15. Проведите доказательство по индукции и воспользуйтесь соотношением (9).

17. Мы можем предположить, что г и s - положительные целые числа. Кроме того, для всех X

Е(Г)- = а-Г-1;а)Е(:)«"

п km

E(lKE(„:j«- = E(Ea)(„!j)".

к n n к

поэтому коэффициенты при ж" Должны быть равны.

21. Левая часть равенства - это многочлен степени п, а правая - многочлен степени то + n + 1. Они совпадают в n + 1 точке. Но этого недостаточно для доказательства их тождественности (хотя оказывается, что при то = О обе части кратны некоторому многочлену; идействительно, при то = О находим, что равенство является тождеством по S, так как оно совпадает с (11)).

22. Предположим, что n > 0. к-Ъ. член равен (fc) П П (n-1-r + ffc-j)

0<j<fc 0<j<n-Jt

= ЦР(;) П (-+*+) П

0<J<*: k<J<n

и эти два произведения дают многочлен степени п - 1 по А;. Поэтому согласно (34) сумма по к равна нулю.

24. Докажем индукцией по п. При п < О тождество очевидно. Если п > О, докажем индукцией по целому то > О, что оно выполняется для (г, п - г + nf + m,t,n) Для этого воспользуемся двумя предыдущими упражнениями и тем, что тождество справедливо для п - 1. Таким образом, тождество {r,s,t,n) выполняется для бесконечно большого числа значений s; более того, оно выполняется для всех s, так как обе его части являются многочленами по s.

25. Используя критерий отношений* и простые оценки для больших значений к, можно доказать сходимость ряда. (Есть и другой способ; воспользоваться теорией комплексного переменного и показать, что функция является аналитической в окрестности точки ж = 1.) Имеем

=Е(-»(:) {Г)7г- Е(-) .еогЛ"

J к J

Теперь положим х = 1/(1 + w), z = -w/{l + ги)"*". Это доказательство принадлежит Г. У. Гоулду (Н. W. Gould) [AMM 63 (1956), 84-91]. См. также более общие формулы в упр. 2.3.4.4-33 и 4.7-22.

26. Можно начать с тождества (35)

в-)(:)Г7)-.

и продолжать по той же схеме, которая использовалась в упр 25. Другой способ состоит в том, чтобы продифференцировать нашу формулу по z; тогда получим

2kAk{r,t)z -z -

Критерий дАламбера. - Прим. ред.