Математические байки

Видно, каждая дробь dx^d/(1-x^d) как раз даёт вклад d в коэффициент при каждой степени x^n с n, делящимся на d — вот "по столбцам" и получается производящая функция для суммы делителей σ(n).

(https://gallica.bnf.fr/ark:/12148/bpt6k6952c/f291.item )

И давайте для следующего шага я приведу скриншот совсем из оригинала:

(кстати, и впрямь много лет назад — с 1740-го прошло 7 лет!)

Собственно — вот, как об этом пишет сам Эйлер:

На самом деле, когда утверждение уже есть, его вывод из пентагональной теоремы очень естественен. Я очень люблю принцип "видишь длинное произведение — прологарифмируй!"; если прологарифмировать произведение
Q(x)=(1-x)(1-x^2)(1-x^3)(1-x^4)(1-x^5)...,
стоящее с одной из сторон равенства в пентагональной теореме, то получается сумма
ln Q(x) = \sum_d ln(1-x^d).
Если её теперь продифференцировать, то логарифмы исчезают, и остаётся
Q'(x)/Q(x) = \sum_d d*x^{d-1}/(1-x^d).
И если теперь домножить на x, то в правой части получается в точности производящая функция для σ(n)!

Мне хочется воспроизвести тут полностью то, что Эйлер пишет в первом абзаце своей статьи:
===
До сих пор математики тщетно пытались обнаружить в последовательности простых чисел какой-либо порядок, и мы имеем все основания верить, что здесь существует какая-то тайна, в которую человеческий ум никогда не проникнет. Чтобы убедиться, следует только взглянуть на таблицу простых чисел, которую некоторые взяли на себя труд вычислить дальше чем до ста тысяч, и осознать, что здесь нет никакого порядка и никакого правила. Это тем более удивительно, что арифметика дает нам определенные правила, с помощью которых мы можем продолжать последовательность простых чисел сколь угодно далеко, не замечая, однако, ни малейшего следа порядка. Я сам, конечно, далек от этой цели, но мне удалось открыть чрезвычайно странный закон, управляющий последовательностью сумм делителей целых чисел, которая на первый взгляд кажется неправильной ровно в такой же степени, как и последовательность простых чисел, и которая в некотором смысле даже включает в себя эту последнюю. Этот закон, который я вскоре объясню, по моему мнению, тем более замечателен, что он имеет такую природу, что мы можем быть уверены в его справедливости, не давая ему безукоризненного доказательства. Тем не менее я представлю в его пользу такие доводы, которые можно рассматривать как почти равносильные строгому доказательству.
===
(цит. по: Д. Пойа, Математика и правдоподобные рассуждения, глава VI)

Так вот, продолжая историю про Эйлера.
1747-й год, пентагональная теорема все ещё только гипотеза.
Эйлер открывает другое утверждение — на этот раз о сумме делителей.
А именно — пусть σ(n) это сумма всех делителей числа n, включая 1 и его самого. Последовательность значений σ(n) —
1, 3, 4, 7, 6, 12, 8, 15, ... .
На вид достаточно нерегулярная — что естественно, σ(n) хорошо связано с разложением n на простые множители, но у n и у n+1 разложения совершенно разные.
Так вот — Эйлер обнаруживает, что она подчиняется практически такому же рекуррентному соотношению, что и p(n), с единственной заменой: если в правой части возникает σ(0), то нужно вместо него подставить n.
Он публикует статью Découverte d'une loi tout extraordinaire des nombres par rapport à la somme de leurs diviseurs — оригинал на французском можно найти тут, а ещё она в переводе вошла в книгу Пойа "Математика и правдоподобные рассуждения", см. главу VI.
Смотрите (подстановку n вместо σ(0) я выделяю жирным) :
σ(1)=1;
σ(2)=σ(2-1)+2=3;
σ(3)=σ(3-1)+σ(3-2)=1+3=4;
σ(4)=σ(4-1)+σ(4-2)=7;
σ(5)=σ(5-1)+σ(5-2)-5=4+7-5=6;
σ(6)=σ(6-1)+σ(6-2)-σ(6-5)=7+6-1=12;
σ(7)=σ(7-1)+σ(7-2)-σ(7-5)-7=12+6-3-7=8;
...
Удивительно, правда?

коллеги из МКН СПбГУ сообщают, что сегодня (27.04) в 17 часов Федор Петров будет разбирать избранные задачи Всероссийской олимпиады по математике этого года

zoom ID 833 2177 9056
pass 225225

тж. обещают трансляцию на
https://www.youtube.com/channel/UCyE7AvYBGTt0uPV_WTWRvTg

Доказал Эйлер её, собственно, далеко не сразу. В 1740-м, заинтересовавшись этой темой после письма Филиппа Науде (Philippe Naudé) — где был, среди прочего, вопрос "сколькими способами можно представить 50 в виде суммы 7 различных слагаемых" — Эйлер её открывает экспериментально. Упоминает в том же 1740-м в письме Даниилу Бернулли, и включает в свою статью "Observationes analyticae variae de combinationibus", которую подаёт в 1741 году.
Вот тут можно посмотреть на скан, видимо, оригинального издания; вот тут — на неё в его полном собрании сочинений, тоже на латыни; а вот тут — на английский перевод. Кстати — выхода статьи ему пришлось ждать 10 лет(!):

А ещё можно задуматься — если инволюцию Франклина придумал аж в 1881-м Франклин, то как же пентагональную теорему (больше, чем на 120 лет раньше!) доказывал сам Эйлер?
И там всё интересно! Собственно, когда я начинал эту байку записывать, я ответа не знал — спасибо Феде Петрову за рассказ и за ссылки!

Мы получаем сумму слагаемых вида p(n-s) со знаками. Причём, если раскрыть все скобки, то p(n-s) появляется по одному разу на способ его представить в виде суммы различных слагаемых: разница аргументов p(.,.) на каждом шаге либо сохраняется, либо уменьшается на j-1 (а на первом шаге, при сумме по j, равна n-j). При этом каждое увеличение на j-1 меняет знак.

Вот и получается, что каждое p(n-s) в итоге участвует с весом, равным числу способов представить s как сумму нечётного числа различных слагаемых минус число способов как сумму чётного их числа.

Поэтому слагаемые p(n,1), p(n,2), p(n,3),..., составляющие p(n), переписываются как

p(n,1) =p(n-1),

p(n,2)=p(n-1,1)-p(n-2,1) =p(n-2)-p(n-3),

p(n,3)=p(n-1,2)-p(n-3,2)=(p(n-2,1)-p(n-3,1))-(p(n-4,1)-p(n-5,1))
=p(n-3) - p(n-4) -p(n-5) + p(n-6),

и так далее.

Да, ещё — к рекуррентной формуле для p(n) можно прийти и "лобовым" подходом (via). А именно, давайте опять посмотрим на более подробную информацию, но на этот раз ограничим не наибольшее слагаемое, а зафиксируем наименьшее: пусть p(n,j) это число разбиений n с наименьшим слагаемым, равным j.

Тогда:
p(n)=p(n+1,1) — потому что можно к любому разбиению дописать 1; иными словами,
p(n,1)=p(n-1).

p(n)=\sum_{j=1}^n p(n,j) — потому что последнее слагаемое должно быть хоть каким-нибудь.

А дальше можно делать индукцию "уменьшением j":
p(n,j) = p(n-1,j-1) - p(n-j,j-1),
первое — это если мы на 1 уменьшили наименьшее слагаемое j, а второе — это лишние слагаемые, которые мы при этом посчитали (предыдущее слагаемое это тоже (j-1), а не хотя бы j, так что 1 обратно к последнему добавить нельзя).

(и — знакомые формы!)

Несколько относящихся к биекции Франклина кусочков из этой большой статьи: