Welcome to our community

Be a part of something great, join today!

Problem Of The Week # 334 - Dec 11, 2018

Status
Not open for further replies.
  • Thread starter
  • Moderator
  • #1

Euge

MHB Global Moderator
Staff member
Jun 20, 2014
1,925
Here is this week's POTW:

-----
Let $f,g : \Bbb R \to \Bbb R$ such that $$f(x) = \sum_{n =1}^{\lfloor x\rfloor} g\left(\frac{x}{n}\right)$$ Show that $$g(x) = \sum_{n = 1}^{\lfloor x\rfloor} \mu(n)\, f\left(\frac{x}{n}\right)$$ where $\mu(n)$ is the Möbius function.


-----

Remember to read the POTW submission guidelines to find out how to submit your answers!
 
  • Thread starter
  • Moderator
  • #2

Euge

MHB Global Moderator
Staff member
Jun 20, 2014
1,925
This week's problem was solved correctly by Ackbach . You can read his solution below.

There is a proof of this on the Möbius Inversion Formula wiki page, but there are a few steps that are lacking in details, so I will add some value there.

First of all, we note that
$$\sum_{d|n}\mu(d)=i(n),$$
where
$$i(n)=\begin{cases}1,&\; n=1\\0,&\;\text{otherwise}\end{cases}.$$

Secondly, we use the Iverson convention that [condition] is the indicator function of the condition, being $1$ if the condition is true, and $0$ if it is false. Also note that we use the convention that if $x$ is a real number, then
$$\sum_{i=1}^xf(i)=\sum_{i=1}^{\lfloor x\rfloor}f(i);$$
that is, the sum is understood to run over integers only, and we round down on the upper end.

Then we expand out the RHS of what we are to prove:
\begin{align*}
\sum_{n=1}^{x}\mu(n)\,f\!\left(\frac{x}{n}\right)
&=\sum_{n=1}^{x}\mu(n)\sum_{m=1}^{x/n}g\!\left(\frac{x}{mn}\right)\qquad \text{(Let $r=mn.$)} \\
&=\sum_{n=1}^{x}\mu(n)\sum_{r=n}^{x}g\!\left(\frac{x}{r}\right).
\end{align*}
Now, we would like to interchange the order of summation, but the problem is that the inner sum currently depends on $n$. If we include the condition $[r==mn],$ we can let the inner sum start at $1:$
\begin{align*}
\sum_{n=1}^{x}\mu(n)\,f\!\left(\frac{x}{n}\right)
&=\sum_{n=1}^{x}\mu(n)\sum_{r=1}^{x}[r==mn]\,g\!\left(\frac{x}{r}\right) \\
&=\sum_{r=1}^{x}g\!\left(\frac{x}{r}\right)\sum_{n=1}^{x}\mu(n)[r==mn] \\
&=\sum_{r=1}^{x}g\!\left(\frac{x}{r}\right)\sum_{n|r}\mu(n) \\
&=\sum_{r=1}^{x}g\!\left(\frac{x}{r}\right)i(r) \\
&=g(x),
\end{align*}
as required.
 
Status
Not open for further replies.