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}) ##.

Mentor
2021 Award
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?

Mentor
2021 Award
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\} ##.

Mentor
2021 Award
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.

Math100