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

  • Thread starter Math100
  • Start date
  • #1
Math100
611
171
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}) ##.
 

Answers and Replies

  • #2
fresh_42
Mentor
Insights Author
2021 Award
17,257
17,289
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\}.##
 
  • #3
Math100
611
171
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?
 
  • #4
fresh_42
Mentor
Insights Author
2021 Award
17,257
17,289
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.
 
  • #5
Math100
611
171
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\} ##.
 
  • #6
fresh_42
Mentor
Insights Author
2021 Award
17,257
17,289
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.
 

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

Replies
20
Views
156
Replies
4
Views
112
  • Last Post
Replies
2
Views
156
Replies
2
Views
171
Replies
3
Views
177
Replies
5
Views
298
Replies
5
Views
132
  • Last Post
Replies
2
Views
183
Replies
10
Views
319
Top