Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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.

share|improve this question
    
I don't understand the downvote. This seems clearly on topic and shows thought about the question. +1 from me. –  Ross Millikan Jun 27 '11 at 14:14
    
I think I managed to keep all of the $\Phi$'s and $\phi$'s straight, but if not please correct it. –  Zev Chonoles Jun 27 '11 at 14:17
    
Thanks Zev for editing my question. I'm sorry for being such a noob and don't know how to format math symbols. –  Phil Jun 27 '11 at 14:18
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? –  Zev Chonoles Jun 27 '11 at 14:20
    
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. –  Phil Jun 27 '11 at 15:00
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
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. –  André Nicolas Jun 27 '11 at 16:17
add comment

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

share|improve this answer
    
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? –  Phil Jun 27 '11 at 14:08
    
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. –  Ross Millikan Jun 27 '11 at 14:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.