Реферат: Тождество Эйлера

Мы видим, что представлений числа n в виде a1 + 2a2 + ... + kak столько же, сколько есть его при xn в нашем произведении равен p(n), то есть 1/φ(x) = π(x). Теорема доказана. Положив для удобства p(0) = 1, напишем (1 – x – x2 + x5 + x7 + ...)(1 + p(1)x + p(2)x2 + ...) = 1 (коэффициенты в первом множителе пишутся согласно тождеству Эйлера!). Раскроем скобки и приравняем нулю коэффициенты при x, x2, x3, ..., xn в левой части. Получим:p(1) – p(0) = 0;

p(2) – p(1) – p(0) = 0;

p(3) – p(2) – p(1) = 0;

. . . . . . . . . . . . . . . . . . . . . .

p(n) – p(n–1) – p(n–2) + p(n–5) + p(n–7) – ... = 0

(в левой части последней формулы нужно писать слагаемые до тех пор, пока аргумент у p остаётся неотрицательным). Итак, p(n) = p(n–1) + p(n–2) – p(n–5) – p(n–7) + ... .

Эта формула позволяет быстро составить довольно длинную таблицу чисел p(n). Вот практический совет, как это сделать. Возьмите лист клетчатой бумаги – лучше всего двойной тетрадный лист. Отрежьте вдоль его длинной стороны полоску шириной 3–4 клетки. Положите эту полоску перед собой вертикально и у левого среза в нижней клетке поставьте какой-нибудь знак, скажем звёздочку. Затем, двигаясь вверх, поставьте в первой клетке +, во второй +, в пятой –, в седьмой –, в двенадцатой +, в пятнадцатой + и т.д., насколько хватит длины полоски (рис. 1). Оставшуюся часть листа также положите перед собой вертикально и, отступя 10–15 клеток от её левого среза, проведите на ней вертикальную черту – сверху донизу. В клетки, прилегающие к черте слева, двигаясь сверху вниз, впишите уже известные вам числа p(n), начиная с p(0): 1, 1, 2, 3, 5, 7. Чтобы найти следующее значение, приложите отрезанную полоску справа к вертикальной черте так, чтобы звёздочка оказалась против первой пустой клетки. Теперь из суммы чисел, стоящих против плюсов, вычтите сумму чисел, стоящих против минусов. Что получится – впишите в клетку против звездочки: это – следующее значение функции p(n). Опустите полоску на одну клетку вниз и повторите то же самое. И так далее. Через несколько минут вы получите колонку чисел p(n) высотой в ваш лист. Пользуясь этим рецептом, я нашел числа p(n) для n ≤ 50. На это потребовалось – честно, по часам – 17 минут. (Несколько первых шагов вычисления я привожу на рисунке 2; красные числа – это новые значения p(n).) В частности, p(50) = 204226.

Представьте себе, сколько потребовалось бы времени для нахождения этого числа кустарным способом!

3. Доказательство тождества Эйлера

Раскроем скобки в нашем произведении (1 – x)(1 – x2)(1 – x3)(1 – x4)... .

Получится сумма (бесконечная), в которой xn встретится столько раз, сколькими способами n представляется в виде суммы возрастающей последовательности натуральных чисел: n = n1 + n2 + ... + nk , n1 < n2 < ... < nk ; при этом знак при xn будет +, если k чётно, и –, если k нечётно. Ниже в этом параграфе наборы (n1 , ..., nk ) с n1 + ... + nk = n и n1 < ... < nk называются просто «разбиениями». Мы будем различать разбиения трёх типов. Обозначим для разбиения (n1 , ..., nk ) через s наибольшее число такое, что nk – nk–s+1 = s – 1, то есть s чисел nk–s+1, ..., nk идут подряд (очевидно, s ≤ k). Например, для разбиения 12=2+4+6 s = 1, для разбиения 12=1+5+6 s = 2, для разбиения 33=4+5+8+9 s = 3. Мы скажем, что разбиение (n1 , ..., nk ) принадлежит

первому типу, если n1 ≤ s, исключая случай n1 = s = k;

второму типу, если n1 > s, исключая случай n1 = s + 1, s = k;

третьему типу в исключённых случаях, то есть если s = k и n1 равно s или s + 1.

Поставим теперь в соответствие разбиению (n1 , ..., nk ) первого типа разбиение ì (n2, ..., nk–n1 , nk–n1+1, ..., nk + 1), если k – n1 ≥ 2,

(n2 + 1, ..., nk + 1), если k – n1 = 1,

которое относится, очевидно, ко второму типу (проверьте!). Более того, таким образом между разбиениями первого и второго типа получается взаимно однозначное соответствие: обратное отображение ставит в соответствие разбиению (n1 , ..., nk ) второго типа разбиение (s, n1, ..., nk–s , nk–s+1 – 1, ..., nk – 1), если k – s ≥ 1, (s, n1 – 1, ..., nk – 1), если k – s = 0 (обозначение s сохраняет прежний смысл), относящееся к первому типу (проверьте!). Поскольку наше соответствие связывает разбиения, в которых числа слагаемых различаются на 1, соответствующие этим разбиениям xn уничтожатся, и в нашей сумме останутся только слагаемые, отвечающие разбиениям третьего типа. А разбиения этого типа, по определению, имеют вид (k, k + 1, ..., 2k – 1),(k + 1, k + 2, ..., 2k), и им соответствуют (–1)k x½(3k² – k), (–1)k x½(3k² + k) (как вам известно, k + (k + 1) + ... + (2k – 1) = ½(3k2 – k) и (k + 1) + (k + 2) + ... + 2k = ½(3k2 + k) ).

Доказательство окончено.