7
$\begingroup$

So the question is:

Prove that $n$ must be a perfect number $\iff$

$$\sum_{k = 1}^{n - 2}k\left \lfloor\frac{n}{k}\right \rfloor = 1 + \sum_{k = 1}^{n - 1}k \left \lfloor \frac{n - 1}{k}\right\rfloor $$

I tried looking up about perfect numbers and found this exact equation on Wolfram Alpha Mathworld but all it said was that it was proven that $n$ had to equal a perfect number, but I do not know how to prove it. My friend Harry gave me this question knowing that I haven't been taught the skills to prove something like this, but he did give me a hint:

$$\sum_{k = 1}^{2^p - 1}k = \sum_{k = 1}^{2^{(p - 1)/2}}(2k + 1)^3 = (2^{p - 1})(2^p - 1) = \left\{P \mid σ(P) = 2P \land p = prime\right\}$$

Could somebody please help me out and tell me what this means and how would I say these equations? I figured out that $2^p - 1 = M_p \iff 2^p - 1 = prime$ such that $M_p$ is a Mersenne prime. I also figured out that $P$ must be a perfect number $\because P = (2^{p - 1})(2^p - 1)$ and that $σ(P) = 2P$ being the divisor function of $P$. I also know what the big sigma $\sum$ means (it means total sum or something like that). All of this is thanks to Wolfram Alpha.

But the rest, I don't know what to do. How do I solve something like this?

$\endgroup$
  • $\begingroup$ There is a typo in the identity, the normal brackets should replaced by the floor function $\endgroup$ – Ronald Blaak Aug 3 '17 at 13:32
  • $\begingroup$ I have changed the title of your question for something that may give more information to the reader. If you preferred the original title, feel free to roll back. $\endgroup$ – Pierre-Guy Plamondon Aug 3 '17 at 15:46
  • $\begingroup$ Oh thanks for changing the brackets in the identity. I thought Harry meant brackets. $\endgroup$ – George N. Missailidis Aug 3 '17 at 21:44
  • $\begingroup$ And thanks @Pierre-GuyPlamondon for changing the title. It sounds much more "mathematical" now :) $\endgroup$ – George N. Missailidis Aug 3 '17 at 22:02
3
$\begingroup$

The equation to be considered for $n$ is $$ \sum_{k=1}^{n-2} k \left\lfloor \frac{n}{k} \right\rfloor = 1 + \sum_{k=1}^{n-1} k \left\lfloor \frac{n-1}{k} \right\rfloor $$ and we assume $n>2$.

If we add $(n-1)\left \lfloor \frac{n}{n-1} \right\rfloor + n \left\lfloor \frac{n}{n}\right \rfloor + (n-1)\left\lfloor \frac{n-1}{n}\right\rfloor= (n-1) + (n) + (0) = 2 n - 1$ for $n>2$ on both the left and right hand side, we can rewrite the equations as $$ \sum_{k=1}^{n} k \left\lfloor \frac{n}{k} \right\rfloor = 1 + (2n-1) + \sum_{k=1}^{n} k \left\lfloor \frac{n-1}{k} \right\rfloor $$ Bringing both sums to the left and combining them then gives: $$ \sum_{k=1}^{n-2} k \left( \left\lfloor \frac{n}{k} \right\rfloor - \left\lfloor \frac{n-1}{k} \right\rfloor\right)= 2 n. $$ On the left hand side we now have a sum over terms of the form: $$ \left\lfloor \frac{n}{k} \right\rfloor - \left\lfloor \frac{n-1}{k} \right\rfloor $$ Since $n$ and $n-1$ only differ by 1, these terms can only be either 1 or 0 whenever $k$ divides $n$ respectively when it doesn't. So only for $k|n$ there is a non-zero contribution on the left. We therefore find the equation $$ \sum_{k|n}^{n} k \left( \left\lfloor \frac{n}{k} \right\rfloor - \left\lfloor \frac{n-1}{k} \right\rfloor\right)= \sum_{k|n}^{n} k = 2 n $$ which is just the definition of a perfect number and establishes the equivalence.

$\endgroup$
  • $\begingroup$ So that's why Harry gave me the "hint" that σ$(P) = 2P$. I was wondering why we didn't use the restricted divisor function anyway, because it is just easier to write and less complicated. $\endgroup$ – George N. Missailidis Aug 3 '17 at 22:01
  • $\begingroup$ Thanks so much :) $\endgroup$ – George N. Missailidis Aug 3 '17 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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