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.

  • 1
    I don't understand the downvote. This seems clearly on topic and shows thought about the question. +1 from me.2011-06-27
  • 0
    I think I managed to keep all of the $\Phi$'s and $\phi$'s straight, but if not please correct it.2011-06-27
  • 0
    Thanks Zev for editing my question. I'm sorry for being such a noob and don't know how to format math symbols.2011-06-27
  • 1
    No problem. I'm looking at my copy of the book, though, and it defines $R(N)$ to be the number of pairs of $(m,n)$ such that $1\leq m\leq N$, $1\leq n\leq N$, and $m\perp n$ - are you sure you've been working from the right definition?2011-06-27
  • 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
    but doesn't R(1) mean counting m's and n's that are strictly less than 1? How can (1,1) be one case to consider?2011-06-27
  • 0
    You are right 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