Problem 11344
(American Mathematical Monthly, Vol.115, February 2008) Proposed by A. Stadler (Switzerland).
Letµ be the M¨obius function of number theory. Show that ifn is a positive integer and n > 1 then
n
X
j=1
µ(j) = −
⌊(n−1)/2⌋
X
j=1
j
⌊n/(2j+1)⌋
X
k=⌈(n+1)/(2j+3)⌉
µ(k).
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
In the RHS, the range of the integer k is n + 1
2j + 3 ≤ k ≤ n 2j + 1, hence
1 2
n k− 1
− 1 + 1 2k = 1
2
n + 1 k − 3
≤ j ≤1 2
n k − 1
.
It’s easy to see that there is only one integer j that satisfies the above inequalities and therefore, by exchanging the two sums, the RHS can be written as
−
⌊(n−1)/3⌋
X
k=1
µ(k) 1 2
n k− 1
= −
n
X
k=1
µ(k) 1 2
n k − 1 so it suffices to prove that
n
X
k=1
µ(k)g(n/k) =X
k≥1
µ(k)g(n/k) = f (n) = [n = 1]
where g(x) = 1 +1
2(x − 1) and f (x) = [⌊x⌋ = 1]. Note that X
j≥1
f (x/j) =X
j≥1
x j
= 1
=X
j≥1
[(x/2) < j ≤ x] = 1 + 1 2(x − 1)
= g(x),
Finally, sinceP
k|mµ(k) = [m = 1] andP
j≥1
P
k≥1|f (n/(kj))| < ∞ X
k≥1
µ(k)g(n/k) = X
k≥1
µ(k)X
j≥1
f (n/(kj)) =X
j≥1
X
k≥1
µ(k)f (n/(kj))
= X
m≥1
f (n/m)X
k≥1
µ(k)[m = kj] = X
m≥1
f (n/m)X
k|m
µ(k)
= X
m≥1
f (n/m)X
k|m
µ(k) = X
m≥1
f (n/m)[m = 1] = f (n).
Remark. This inversion law for the M¨obius function holds for more general f and g:
g(x) =X
k≥1
f (x/k) if and only if f (x) =X
k≥1
µ(k)g(x/k)
as soon asP
j≥1
P
k≥1|f (n/(kj))| < ∞ (see for example Concrete Mathematics by Graham, Knuth, and Patashnik).
