8. Пусть для всех i > О a(i+i)i = +1, ai{i+i) = -1, а все остальные Uij равны нулю; пусть R(i) = S{i) = "i > О". Тогда в левой части получим -1, а в правой--(-1.

9, 10. Нет; правило (d) применимо только для случаев, когда п > 0. (Для п = -1 формула верна, но доказательство - нет.)

11. {п+1)а.

12. 1(1-1/7"+).

13. т{п - m + 1) + i(n ~ m)(n - m + l); или (n(n + 1) - тп{т - 1)).

14. i(n(n+ 1) -m(m - l))(s(s + 1) - r(r - 1)), если т<пиг<8.

15. 16. Ключевые моменты:

o<i<n i<i<" o<j<n-i

0<i<n 0<><n-l

17. Числу элементов множества S.

18. Sij) = "1 < j < n". RiiJ) = "n кратно i и i > j".

19. a„ - Om-i-

20. (6 - l)I]fc=o(" ~ + n + 1 = X3fc=ob*; эта формула следует из формулы (14) и результата упр. 16.

21. Еяо-, + EsG) »J = аЛЛ(;)] + Е,- а> [5(j)] = aj{[R(j)] + [5(j)]); теперь воспользуйтесь тем, что IRU)] + ISU)] = [RU) или S(j)] + [R{j) и 5(j)]. В целом, обозначение Айверсона позволяет выполнять операции "в строку", а не "под строкой".

22. Для (5) и (7) достаточно просто заменить знак 52 знаком П- Кроме того, имеем Пжо.с; = (Пя(;)Ь.)(Пя(;)С.) и

Я0)или50)

23. Потому что 0+я: = а; и 1 а: = ж. Это позволяет упростить многие операции и равенства, например правило (d) и его аналог из предыдущего упражнения.

25. Первый и последний шаги выполнены верно. На втором шаге г используется для двух различных целей одновременно. А третий шаг, вероятно, должен выглядеть так: 5Z"=i

26. Приведем ключевые этапы доказательства:

i=0 \j=0 У i=0 \ 3=0

i=0 /

Тогда искомое произведение равно (ПГ=о")"-

28. (п+1)/2п.

29. (а) Y,o<k<j<i<nзk (Ь) Пусть 5г = JZfo "Г Тогда для исходной суммы получаем следующее выражение: 5з + SiSi + g5f. Более общее решение данной задачи (для большего числа индексов) можно найти в разделе 1.2.9; см. (38).

30. Запишем левую часть в виде Jk k<nikXjyk и выполним аналогичные преобразования в правой части. (Это тождество является частным случаем более общей формулы из упр. 46 для т = 2.)

31. Если положить Uj = Uj, bj - 1, Xj = Vj и = 1, то получится, что исходная сумма равна nE;=i u,v, - «,)(E;=i

33. Это можно доказать индукцией по п, если переписать формулу в виде

1 (у x;{x,-x„i) х;{х,-хп) \

Теперь каждая из этих сумм имеет вид первоначальной суммы, но без (п - 1)-го элемента в знаменателе. По индукции предполагаем, что искомая формула верна для О < г < п - 1. А для г = п рассмотрим тождество

о у- nLi(j-0 х;-(х, + --- + хп)х-+Р{х,) fr{Y[i<k<n,kM~>i 71 UiKkKn.kAxj-к)

где P{Xj) - полином степени п - 2; так как по индукции мы предположили, что формула верна для г = 0,1,...,п-1, отсюда получаем, что она верна и для г = п.

Замечание. На самом деле д-ра Матрицу опередил Л. Эйлер (L. Euler), который написал о своем открытии Христиану Гольдбаху (Christian Goldbach) 9 ноября 1762 года. См. работу Эйлера Institutionum Calculi Integralis 2 (1769), §1169, а также Е. Waring, Phil. Trans. 69 (1779), 64-67. Приведенный ниже альтернативный метод доказательства, в котором используется теория комплексного переменного, не так прост, но более изящен. По теореме о вычетах значение заданной суммы равно

1 Г zdz

J\z\=R {Z-Xi)...(z-Xny

где R> a:i,..., а:„1. Разложение Лорана подынтегральной функции равномерно сходится при \z\ = Д и выглядит следующим образом:

(l-xi/j (l-Xn/J

= г-" + (XI + . • • + Xn)z-"- + {Х\ + XlX2 + )z-- +

При почленном интегрировании пропадет все, кроме члена с коэффициентом z". Этот метод позволяет получить общую формулу для произвольного целого г > 0:

0-1 . . . О-п

31+ +Jn=r-n + l

[J. J. Sylvester, Quart. J. Math. 1 (1857), 141-152.]

34. Если читатель упорно старгшся решить эту задачу, не заглядывая в ответ, то, вероятно, цель упражнения достигнута. Трудно преодолеть искушение рассмотреть числители как многочлены по х, а не по к. И, без сомнения, намного проще доказать значительно более общее соотношение

у. ni<r<n-l(y -Г) 1и1<г<П,Г:кЫ-Уг)

которое является тождеством для 2n - 1 переменных!

35. Если R(j) не выполняетсядакогда, то 8ирд() равен -оо. В основе сформулированного аналога правила (а) лежит тождество о + тах(Ь, с) = тах(а + Ь, а + с). Аналогично, если все а,, bj неотрицательны, то имеем

5иРя(,) о. sups() bj = 8ирд(,) sups() a.bj.

Правила (b) и (с) остаются неизменными, а для правила (d) получаем более простую форму

8ир(8ирд()а, Sups()Oj) =5иря()ог50)а-

36. Вычитаем первый столбец из столбцов с номерами 2,..., п. К первой строке добавим строки с номерами 2,..., п. Теперь остается вычислить определитель треугольной матрицы.

37. Вычитаем первый столбец из столбцов с номерами 2,..., п. Затем вычитаем (А; - 1)-ю строку, умноженную на xi, из /с-й строки, где к = п,п - 1,. .. ,2 (именно в этом порядке) Теперь вынесем коэффициент xi из первого столбца, а коэффициенты Xk-Xi -из столбцов /с = 2,..., п. В результате получим определитель матрицы Вандермонда порядка п - I, умноженный на xi{x2 - Xi)... {хп - Xi). Далее проводим доказательство по индукции.

Приведем альтернативный метод доказательства с использованием высшей математики. Искомый определитель является многочленом от переменных Xi,... ,Хп.

общей степени

1 + 2 +----\-п. Он обращается в нуль, если а: = О или ж, = х (г < j) и коэффициент при

х\х2 - Хп равен +1. Это характерные особенности данного определителя Вообще, если две строки матрицы становятся равными при х, Xj, то их разность обычно делится на X, - Xj, и этот факт часто помогает ускорить процесс вычисления определителей.

38. Вычитаем первый столбец из столбцов с номерами 2,...,п и выносим из второго столбца (г/1 - г/г), из третьего- (j/i - г/з) и т. д. и из п-то - (г/i - уп)- После этого выносим (xi + yi]~ из первой, {х2 + yi)~-из второй и т. д. и (Хп + г/О"-из п-й строки. Теперь вычитаем первую строку из строк с номерами 2,. .,п и выносим (xi - хг)

.. .{xi - x„){xi + г/г)~ ... (a;i -Ь уп)~ В результате остается определитель матрицы Коши порядка п - 1.

39. Пусть / - это единичная матрица {S,j), а J - матрица, состоящая из одних единиц. Так как = nJ, имеем {xl + yj){{x + ny)I - yJ) = x{x + ny)I.

40. Eb,*a;, = ]J {xk - x,) /Хг Ц {xk - x,) = 6,.

t=\ l<.k<n I l<k<n

кфг кф1

41. Это немедленно следует из формулы, выражающей элементы обратной матрицы через алгебраические дополнения. Будет интересно привести здесь также прямое доказательство этого факта. Имеем

f- J 5 у- Ylktii +Ук- Д)П;.(а + yt) •+2" " hi YlkMi ~k)]lktiVt - Ук)

при а; = 0. Правая часть - это многочлен от х, степень которого не превышает п-\. Если положить X = Xj + г/s, 1 < S < п, то все члены обратятся в нуль, за исключением случая, когда S - t Поэтому значение данного многочлена равно

J][(-xfc -ys)I П(х - Xk) = (xj -xk-x)I Y[{xj - Xk)-

кфг I кфз кфх I кф]