16
$\begingroup$

Polya cites this work of Euler as an example of a conjecture which Euler considered impossible to doubt, and yet still needing a demonstration.

It is on pages 90-98 of "Induction and Analogy in Mathematics", which is volume I of "Mathematics and Plausible Reasoning", Princeton 1954. The reference to Euler is in a footnote on page 90. (Opera Omnia ser 1 vol 2 p 241-253).

The conjecture is a recursion formula for the sum of the divisors of any integer, it is stated on page 93 of Polya.

Thanks for any help.

Edit: In response to comments, here is the conjecture. For $n \geq 1$, let $\sigma(n) = \sum_{d|n} d$ be the sum of divisors of $n$. Euler conjectures the remarkable formula

$$\begin{align*} &\ \sigma(n)\\ =&\ \sigma(n-1) + \sigma(n-2) - \sigma(n-5) - \sigma(n-7) + \sigma(n-12) + \sigma(n-15) - \sigma(n-22) + \ldots \\ =&\ \sum_{k \geq 1} (-1)^{\text{floor}\left(\frac{k-1}{2}\right)} \sigma(n - f(k)) \end{align*} $$

where $f(k)$ is defined recursively by $f(1) = 1$ and $f(k) = f(k-1) + \frac{k}{2}$ if $k$ is even, $f(k) = f(k-1) + k$ if $k$ is odd, for all $k > 1$. (Euler stipulates that $\sigma(n - f(k)) := 0$ if $n - f(k) < 0$, and one should substitute $n$ for $\sigma(0)$ if such a summand should arise on the right.)

My question is whether this has ever been proved, and if so where I could find the proof.

Improve this question
$\endgroup$
8
  • 10
    $\begingroup$ could you post the recursion? $\endgroup$
    – Turbo
    Apr 11, 2015 at 5:41
  • 3
    $\begingroup$ indeed, would you think people here would dig up that reference to see what you mean? $\endgroup$
    – Dima Pasechnik
    Apr 11, 2015 at 7:51
  • 4
    $\begingroup$ Oh, I think the author (who is a well-established mathematician -- welcome to MO, Professor Hersh!) made it pretty clear that he meant the conjecture on page 93. I have written it out. $\endgroup$
    – Todd Trimble ♦
    Apr 11, 2015 at 12:47
  • 2
    $\begingroup$ I'm pretty sure Euler proved that formula. See math.stackexchange.com/questions/189157/… for some references. $\endgroup$
    – Gerry Myerson
    Apr 11, 2015 at 12:50
  • 4
    $\begingroup$ There still seems to be room for confusion, since the pentagonal number formula as described at en.wikipedia.org/wiki/Pentagonal_number_theorem is about the generating function for the number of partitions, whereas the present question is about the generating function for the sum of divisors. (One of the references of Gerry Myerson's math.stackexchange post is open only to invited viewers of a blog.) If this is reopened, as seems likely, it might be nice to have details written out; I shouldn't think it would be difficult. $\endgroup$
    – Todd Trimble ♦
    Apr 11, 2015 at 13:44

1 Answer 1

Reset to default
21
$\begingroup$

You can find the outline of a proof of this recursion relation in Surprising Connections between Partitions and Divisors. The line of reasoning first derives the recursion relation for the number of partitions $p(n)$ of $n$ from Euler's pentagonal number theorem, and then shows that the sum of divisors $\sigma(n)$ has the same recursion relation as $p(n)$.

Improve this answer
$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.