9
$\begingroup$

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, 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)$

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 ($\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.

  • 0
    I just searched and found the errata for the book in 1994-1997. I will post what I found as an answer. I'm really sorry to have been wasting everybody's time.2011-06-27

2 Answers 2

2

I did a search and found the 1994-1997 errata for the book.

So, the question was changed to:

Let R(N) be the number of pairs of (m,n) such that 1≤m≤N, 1≤n≤N, and m⊥n 

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.

  • 1
    @P001: The $\le N$ definition is the standard one for such things. Index slippage is a common error, both in student work and in books. To me, no big deal, as long as the general idea is right. Others may not agree.2011-06-27
0

$R(1)=1$, because $m=n=1$ is a solution: they are coprime as the GCD is $1$. So the case $N=1$ works for (b), as both sides are $1$.

  • 0
    You are ri$g$ht that less than is what you asked, and I missed it in my reading. I don't think it works that way, for the reasons you cite.2011-06-27