Prove that ## \sum_{d\mid n} f(d)=\sum_{d\mid n} f(\frac{n}{d}) ##.

[Math100]

Homework Statement

Prove that if $f$ is any arithmetical function, then $\sum_{d\mid n}f(d)=\sum_{d\mid n}f(\frac{n}{d})$.
[Hint: if you have difficulty with this, write out both sides in the case $n=10$.]

Relevant Equations

None.

Proof:

Let $n=10$.
Observe that
\begin{align*}
&\sum_{d\mid n}f(d)=\sum_{d\mid n}f(\frac{n}{d})\\
&\sum_{d\mid 10}f(d)=\sum_{d\mid 10}f(\frac{10}{d})\\
&f(1)+f(2)+f(5)+f(10)=f(\frac{10}{1})+f(\frac{10}{2})+f(\frac{10}{5})+f(\frac{10}{10})\\
&f(1)+f(2)+f(5)+f(10)=f(10)+f(5)+f(2)+f(1).\\
\end{align*}
Therefore, $\sum_{d\mid n}f(d)=\sum_{d\mid n}f(\frac{n}{d})$.

 

[fresh_42]

Homework Statement:: Prove that if $f$ is any arithmetical function, then $\sum_{d\mid n}f(d)=\sum_{d\mid n}f(\frac{n}{d})$.
[Hint: if you have difficulty with this, write out both sides in the case $n=10$.]
Relevant Equations:: None.

Proof:

Let $n=10$.
Observe that
\begin{align*}
&\sum_{d\mid n}f(d)=\sum_{d\mid n}f(\frac{n}{d})\\
&\sum_{d\mid 10}f(d)=\sum_{d\mid 10}f(\frac{10}{d})\\
&f(1)+f(2)+f(5)+f(10)=f(\frac{10}{1})+f(\frac{10}{2})+f(\frac{10}{5})+f(\frac{10}{10})\\
&f(1)+f(2)+f(5)+f(10)=f(10)+f(5)+f(2)+f(1).\\
\end{align*}
Therefore, $\sum_{d\mid n}f(d)=\sum_{d\mid n}f(\frac{n}{d})$.

This is the case $n=10.$ What about the general case?

You basically have to show that $\{d\, : \,d|n\}=\{n/d\, : \,d|n\}.$

 

[Math100]

This is the case $n=10.$ What about the general case?

You basically have to show that $\{d\, : \,d|n\}=\{n/d\, : \,d|n\}.$

This is where I don't know how to do, because I got the case $n=10$ from the hint. But how do I show that those two are equal by proving them with the general case?

 

[fresh_42]

A common way to show the equality of sets is to show that they are contained in each other.

a) Say $d|n.$ Then $n=d\cdot e$ for some $e$ and $e=\dfrac{n}{d} \,|\,n.$ This shows $\{n/d\, : \,d|n\}\subseteq \{d\, : \,d|n\}$ since we showed that $e$ is a divisor of $n$.

b) Say $e=\dfrac{n}{d}$ for some divisor $d$ of $n.$ Then $e\cdot d= n$ and therefore $e|n.$
This shows $\{n/d\, : \,d|n\}\subseteq \{d\, : \,d|n\}.$

From a) and b) we get $\{n/d\, : \,d|n\} = \{d\, : \,d|n\}.$

It is a bit tricky to see that this is actually a proof because the sets are so similar. You could try to prove the following with that method:

A number $n$ is said to be odd if it can be written as $n=2k+1.$
A number $n$ is said to be even if it is not odd.
Prove that even numbers are exactly those that can be divided by $2,$ i.e. show that
$$
\{n\, : \,n \text{ is even }\}=\{n\, : \, 2\,|\,n\}
$$
You have to use the definitions here.

 

[Math100]

A common way to show the equality of sets is to show that they are contained in each other.

a) Say $d|n.$ Then $n=d\cdot e$ for some $e$ and $e=\dfrac{n}{d} \,|\,n.$ This shows $\{n/d\, : \,d|n\}\subseteq \{d\, : \,d|n\}$ since we showed that $e$ is a divisor of $n$.

b) Say $e=\dfrac{n}{d}$ for some divisor $d$ of $n.$ Then $e\cdot d= n$ and therefore $e|n.$
This shows $\{n/d\, : \,d|n\}\subseteq \{d\, : \,d|n\}.$

From a) and b) we get $\{n/d\, : \,d|n\} = \{d\, : \,d|n\}.$

It is a bit tricky to see that this is actually a proof because the sets are so similar. You could try to prove the following with that method:

A number $n$ is said to be odd if it can be written as $n=2k+1.$
A number $n$ is said to be even if it is not odd.
Prove that even numbers are exactly those that can be divided by $2,$ i.e. show that
$$
\{n\, : \,n \text{ is even }\}=\{n\, : \, 2\,|\,n\}
$$
You have to use the definitions here.

Suppose $n$ is even.
Then $n=2a$ for some $a\in\mathbb{Z}$.
This implies $2\mid n$.
Thus $\{n\, : \,n \text{ is even }\}=\{n\, : \, 2\,|\,n\}$.

 

[fresh_42]

Suppose $n$ is even.
Then $n=2a$ for some $a\in\mathbb{Z}$.

Yes, but why? More detailed:

$n$ is even, i.e. not odd. So $n\neq 2k+1$. Since $2(k-1)+1=2k-1$ and $2(k+1)+1=2k+3$ are all odd per definition, we can only have $2(k-1)+0,2k+0,2(k+1)+0$ within the gaps of odd numbers for $n.$ Thus $n=2k$ for some $k$ and so $2\,|\,n.$

This implies $2\mid n$.
Thus $\{n\, : \,n \text{ is even }\}=\{n\, : \, 2\,|\,n\}$.

The other direction? So far, we have shown $\{n\, : \,n \text{ is even }\}\subseteq \{n\, : \, 2\,|\,n\}.$

Now assume $2\,|\,n.$ Then $n=2\cdot e$ for some $e.$ If $n$ was odd, then $2e=2k+1$ for some $k.$ Therefore $2(e-k)=1$ and $2\,|\,1$ which is impossible. Hence, $n$ cannot be odd, which is the definition of even, i.e. $\{n\, : \,n \text{ is even }\}\supseteq \{n\, : \, 2\,|\,n\}.$

Both inclusions $\{n\, : \,n \text{ is even }\}\subseteq \{n\, : \, 2\,|\,n\} \subseteq \{n\, : \,n \text{ is even }\}$ imply equality.

You cannot just jump to what you want to show. Read the definition! I defined 'even' as 'not odd', and 'odd' as $2k+1.$ I did not define 'even' as $2k.$ This had to be proven.

This is an almost trivial example, admitted, but it should show you the steps from what we know to what we want to prove.