I'm confused at exercise 4.49 on page 149 from the book "Concrete Mathematics: A Foundation for Computer Science":
Let $R(N)$ be the number of pairs of integers $(m,n)$ such that $0\leq m < N$, $0\leq n<N$, and $m\perp n$.
(a) Express $R(N)$ in terms of the $\Phi$ function.
(b) Prove that $$R(N) = \displaystyle\sum_{d\geq 1}\left\lfloor\frac{N}{d}\right\rfloor^2 \mu(d)$$
- $m\perp n$ means $m$ and $n$ are relatively prime
- $\mu$ is the Möbius function
- $\Phi(x)=\sum_{1\leq k\leq x}\phi(k)$
- $\phi$ is the totient function
For question (a), my solution is $R(N) = 2 \cdot \Phi(N-1) + [N>1]$ (where $[\;\;]$ is the Iverson bracket, i.e. [True]=1, [False]=0)
Clearly $R(1)$ has to be zero, because the only possibility of $(m,n)$ for testing is $(0,0)$, which doesn't qualify. This agrees with my answer.
But here is the book's answer:
Either $m<n$ ($\Phi(N−1)$ cases) or $m=n$ (one case) or $m>n$ ($\Phi(N−1)$ again). Hence $R(N) = 2\Phi(N−1) + 1$.
$m=n$ is only counted when $m=n=1$, but how could that case appear when $N=1$?
I thought the book assumed $R$ is only defined over $N≥2$. But their answer for question (b) relies on $R(N) = 2Φ(N−1) + 1$ and proves the proposition also for the case $N=1$. They actually prove $2Φ(N−1) + 1 = RHS$ for $N≥1$. And if my assumption about the $R(1)$ case is true, then the proposition in (b) cannot be valid for $N=1$, for $LHS=0$ and $RHS=1$. But the fact that it's invalid just for one value seems a little fishy to me.
My question is, where am I confused? What is wrong in my understanding about the case $R(1)$?
Thank you very much.
Best Answer
I did a search and found the 1994-1997 errata for the book.
So, the question was changed to:
This also slightly changes the solution for R(N), and everything makes sense. I don't post the solution to prevent spoilers.
I'm sorry for having wasted everybody's time.