Estoy confundido en el ejercicio 4.49 en la página 149 del libro "Concreto de las Matemáticas: Una Fundación de Ciencias de la computación":
Deje $R(N)$ el número de pares de enteros $(m,n)$ tal que $0\leq m < N$, $0\leq n<N$, y $m\perp n$.
(a) Expresar $R(N)$ en términos de la $\Phi$ función.
(b) Demostrar que $$R(N) = \displaystyle\sum_{d\geq 1}\left\lfloor\frac{N}{d}\right\rfloor^2 \mu(d)$$
- $m\perp n$ $m$ $n$ son relativamente primos
- $\mu$ es la función de Möbius
- $\Phi(x)=\sum_{1\leq k\leq x}\phi(k)$
- $\phi$ es el totient función
Para la pregunta (a), mi solución es $R(N) = 2 \cdot \Phi(N-1) + [N>1]$ (donde $[\;\;]$ es la Iverson soporte, es decir, [Verdadero]=1, [False]=0)
Claramente $R(1)$ tiene que ser cero, porque la única posibilidad de $(m,n)$ para la prueba es $(0,0)$, que no cumple con los requisitos. Esto está de acuerdo con mi respuesta.
Pero aquí está el libro de la respuesta:
Ya sea $m<n$ ($\Phi(N−1)$ de los casos) o $m=n$ (un caso) o $m>n$ ($\Phi(N−1)$ de nuevo). Por lo tanto $R(N) = 2\Phi(N−1) + 1$.
$m=n$ solo cuenta cuando se $m=n=1$, pero, ¿cómo podía ese caso aparecen al $N=1$?
Pensé que el libro asumido $R$ sólo está definida sobre $N≥2$. Pero su respuesta para la pregunta (b) se basa en las $R(N) = 2Φ(N−1) + 1$, y se demuestra la proposición también para el caso de $N=1$. Ellos prueban $2Φ(N−1) + 1 = RHS$$N≥1$. Y si mi suposición acerca de la $R(1)$ de los casos es cierto, entonces la proposición (b) no puede ser válido para $N=1$$LHS=0$$RHS=1$. Pero el hecho de que no es válido sólo para un valor parece un poco sospechoso para mí.
Mi pregunta es, ¿dónde estoy confundido? Lo que está mal en mi entendimiento sobre el caso de $R(1)$?
Muchas gracias.
