Prove that $\sum_{j=1}^{n} f(\frac{n}{j}) = n^2$, where $f(x)$ is the number of coprime pairs $(a, b)$ for which $1 ≤ a ≤ x$ and $1 ≤ b ≤ x$. For each real number $x > 0$ let $f(x)$ be the number of coprime pairs $(a,b)$ where $a$ and $b$ are integers and $1 ≤ a ≤ x$ and $1 ≤ b ≤ x$. For example $f(\frac{5}{2}) = 3$ because there exist exactly three coprime pairs $(1,1), (1,2), (2,1)$ where $1 ≤ a ≤ \frac{5}{2} = 2,5$ and $1 ≤ b ≤ \frac{5}{2} = 2,5$. If $n$ is a positive integer then calculate the sum:
$\sum_{j=1}^{n} f(\frac{n}{j}) = f(n) + f(\frac{n}{2}) + f(\frac{n}{3}) + f(\frac{n}{4}) + ... + f(\frac{n}{n})$.
We are supposed to use combinatorics to solve this.
I calculated some sums by hand and figured out that $f(x)$ outputs A018805. It seems that
$\sum_{j=1}^{n} f(\frac{n}{j}) = n^2$ but I am having problems proving it.
If we use double counting, $n^2$ counts all ordered pairs $(a,b)$ where $a$ and $b$ are integers and $1 ≤ a ≤ n$ and $1 ≤ b ≤ n$. Then $\sum_{j=1}^{n} f(\frac{n}{j})$ should count the same but with more detail. For $j = 1$ we have $f(n)$ which counts all the ordered pairs but with the restriction that they have to be coprime. We can partition the set of all ordered pairs into those that are coprime and those that are not. Then that would mean that if we prove that $\sum_{j=2}^{n} f(\frac{n}{j})$ counts all the ordered pairs that are not coprime then the problem would be solved.
That's all I have figured out for now. Keep in mind again that this should be done using combinatorics.
 A: Of course, $$
n^2 = |[n] \times [n]|
$$
where $[n] = \{1,\ldots,n\}$ and $\times$ is the cartesian product. The question is, what subset of this set could $f\left(\frac nj\right)$ count, so that we can perform a combinatorial argument?
Let $1 \leq j \leq n$ be arbitrary. We know that $$
f\left(\frac nj\right) = \left|\left\{(a,b) : a,b \leq \frac nj,\gcd(a,b) = 1 \right\}\right|
$$
We write this as $$
f\left(\frac nj\right) = \left|\left\{(a,b) : ja,jb \leq n,\gcd(a,b) = 1 \right\}\right|
$$
However, if $\gcd(a,b) = 1$ then $\gcd(ja,jb) = j$. So we write this as $$
f\left(\frac nj\right) = \left|\left\{(a,b) : ja,jb \leq n,\gcd(ja,jb) = j \right\}\right|
$$
Now, make the following rewrite : let $s = ja, r = jb$ on the right hand side. Rewriting the definition appropriately, $$
f\left(\frac nj\right) = \left|\left\{\left(\frac{s}j,\frac {r}j\right) : s,r \leq n,\gcd(s,r) = j \right\}\right| = |A_{nj}|
$$
where $$
A_{nj} = \left\{\left(\frac{s}j,\frac {r}j\right) : s,r \leq n,\gcd(s,r) = j \right\}
$$
Note that $A_{nj}$ is bijective to $B_{nj}$ where
$$
B_{nj} = \left\{\left(s,r\right) : s,r \leq n,\gcd(s,r) = j \right\}
$$
via the map $$
f: A \to B , f((u,v)) = (ju,jv) 
$$
therefore $$
|A_{nj}| = |B_{nj}| = f\left(\frac{n}{j} \right)
$$
Note that $B_{nj} \subset [n] \times [n]$ for all $j$. The result follows once you can prove that :

*

*The $B_{nj}$ are disjoint sets for $1 \leq j\leq n$.


*$[n] \times [n] = \cup_{j=1}^n B_{nj}$.
Both of which are fairly straightforward from the description of $B_{nj}$.
