Welcome guest
You're not logged in.
131 users online, thereof 0 logged in

Proof: (related to "Möbius Inversion Formula")

  • By assumptions, $\alpha,\beta$ are arithmetic functions with $\beta(n)=\sum_{d\mid n}\alpha(d).$
  • For any divisor $d\mid n$ we have, therefore, $$\beta\left(\frac nd\right)=\sum_{b\mid \frac nd}\alpha(b).$$
  • Multiplying both sides of the equation by the Möbius function of $\mu(d)$ results in
    $$\mu(d)\beta\left(\frac nd\right)=\sum_{b\mid \frac nd}\mu(d)\alpha(b).$$
  • The sum over all divisors $d\mid n$ results in
    $$\sum_{d\mid n}\mu(d)\beta\left(\frac nd\right)=\sum_{d\mid n}\sum_{b\mid \frac nd}\mu(d)\alpha(b)=\sum_{b\mid n}\sum_{d\mid \frac nb}\mu(d)\alpha(b).$$
  • In the last step, we could exchange the indices $d$ and $b$ because as the index $b$ runs through all divisors $b\mid \frac nd$ so does $d$ run through all complementary divisors $d\mid \frac nb.$
  • Now, the term $\alpha(b)$ does not depend on the index $d$ of the inner sum and we can use the distributivity law to get
    $$\sum_{b\mid n}\sum_{d\mid \frac nb}\mu(d)\alpha(b)=\sum_{b\mid n}\alpha(b)\sum_{d\mid \frac nb}\mu(d).$$
  • The last sum can be significantly simplified using the sum of Möbius function over divisors and we get
    $$\sum_{b\mid n}\alpha(b)\sum_{d\mid \frac nb}\mu(d)=\sum_{b\mid n}\alpha(b)[b=n]=\alpha(n).$$
  • We have shown
    $$\alpha(n)=\sum_{d\mid n}\mu(d)\beta\left(\frac nd\right).$$
q.e.d

| | | | created: 2019-04-06 22:57:06 | modified: 2019-04-06 23:03:00 | by: bookofproofs | references: [701], [1272]


This work was contributed under CC BY-SA 3.0 by:

This work is a derivative of:

(none)

Bibliography (further reading)

[1272] Landau, Edmund: “Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie”, S. Hirzel, Leipzig, 1927

[701] Scheid Harald: “Zahlentheorie”, Spektrum Akademischer Verlag, 2003, 3. Auflage

FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint
© 2018 Powered by BooOfProofs, All rights reserved.