Demostrar que Spec() y Spec(ß) parten enteros positivos si y ß son irracionales y 1/ + 1/ß = 1

Question

En el problema 3.13 de Concrete Math se pregunta:

"Sean y ß números reales positivos. Demostrar que Spec() y Spec(ß) parten enteros positivos si y sólo si y ß son irracionales y 1/ + 1/ß = 1"

La solución afirma:

"Si forman una partición, la fórmula del texto para N(,n) implica que 1/ + 1/ß = 1, porque los coeficientes de n en la ecuación N(,n) + N(ß,n) = n deben coincidir para que la ecuación se cumpla para n grandes" (pasa a la siguiente parte de la prueba pero sólo me importa esta parte)

En este capítulo, definen Spec() como un subconjunto infinito de enteros: $\{\lfloor\rfloor,\lfloor2\rfloor, ...\}$ y definir N(,n) como el número de elementos en Spec() que son $\le$ n. Demuestran que N(,n) = $\lceil(n+1)/\rceil - 1$ . También muestran que una condición necesaria para que Spec() y Spec(ß) dividan los enteros positivos es N(,n) + N(ß,n) = n

Puedo escribir la ecuación N(,n) + N(ß,n) = n sustituyendo esa ecuación: $$\lceil(n+1)/ß\rceil + \lceil(n+1)/\rceil - 2 = n$$ y luego convertirlo en suelo $$\lfloor (n+1)/ß\rfloor + \lfloor (n+1)/\rfloor = n$$ luego dividir el piso en la parte fraccionaria y real de sus argumentos $$n(1/ß + 1/) + 1/ + 1/ß - \{(n+1)/ß\} - \{(n+1)/\} = n$$ ...pero, en ese punto, no veo cómo puedo concluir que 1/ + 1/ß = 1. Veo que 1/ + 1/ß aparece como coeficiente de n, pero está el problema de las partes fraccionarias de la derecha. Para que su afirmación sea correcta, las partes fraccionarias tendrían que sumar 1 para anular el 1 de 1/ + 1/ß. Sé que las partes fraccionarias tienen valores menores que uno (ya que son partes fraccionarias de números reales), pero no veo cómo concluir que suman 1. ¿Puedo afirmar que, puesto que n aparece en el lado derecho con un coeficiente de 1, el coeficiente de n en el lado izquierdo debe ser 1?

Answer 1

La pista está en la frase "para grandes $n$ ".

Como has demostrado, debemos tener eso para todos $n$ , $$n(1/\beta + 1/\alpha) + 1/\alpha + 1/\beta - \{(n+1)/\beta\} - \{(n+1)/\alpha\} = n.$$

Denotemos $1/\beta + 1/\alpha$ por $c$ para reescribirlo como $$nc + c - \{(n+1)/\beta\} - \{(n+1)/\alpha\} = n.$$

Como $0 \le \{x\} < 1$ para todos $x$ y aquí tenemos $\{(n+1)/\beta\} - \{(n+1)/\alpha\} = nc + c - n$ Esto significa que $$0 \le nc + c -n < 2.$$

Ahora consideremos lo que ocurre con los grandes $n$ . Si $c < 1$ entonces $nc + c - n = c - n(1-c)$ acaba siendo negativo (de hecho, se vuelve negativo para $n > \frac{c}{1-c}$ ), violando la " $0 \le$ "desigualdad". Y si $c > 1$ , entonces, para los casos muy grandes $n$ Tendremos $nc + c - n > 2$ En concreto, para $n > 2/(c-1)$ Tendremos $nc + c - n > nc - n > 2$ . Así que debemos tener $c = 1$ .

Otra forma de escribir lo mismo es dividir $0 \le nc + c - n < 2$ por $n$ y decir que $$0 \le c + \frac{c}{n} - 1 < \frac{2}{n},$$ y tomando el límite como $n \to \infty$ da $c - 1 = 0$ ya que se encuentra entre los límites izquierdo y derecho, ambos iguales a $0$ .

Answer 2

Recuerde que la última ecuación es válida para todo números enteros positivos $n$ .

Si, por ejemplo, $1/\alpha + 1/\beta$ fueran mayores que 1, entonces para un tamaño suficientemente grande $n$ El lado izquierdo de la última ecuación sería mayor que el derecho. (Esto es ciertamente cierto si ignoramos las partes fraccionarias, pero incluso con las partes fraccionarias, sigue siendo cierto, porque los 2 lados se alejan cada vez más a medida que $n \to \infty$ mientras que las partes fraccionarias permanecen acotadas).

Una contradicción similar surge si $1/\alpha + 1/\beta$ eran inferiores a 1.

Answer 3

El conjunto de enteros positivos iguales a $[nx]$ para algunos $n$ (donde $x > 1$ para evitar la situación trivial de cubrir todos los enteros positivos) tiene densidad $\frac{1}{x}$ . Si cada número es cubierto exactamente una vez por el $\alpha$ et $\beta$ conjuntos, entonces la suma de sus densidades es $1$ .

http://en.wikipedia.org/wiki/Natural_density

El resto de la prueba se puede encontrar en

http://en.wikipedia.org/wiki/Beatty_sequence

Answer 4

En la derivación de Chairbender, hay un pequeño error entre las dos primeras ecuaciones, que dice $$\lceil(n+1)/\rceil + \lceil(n+1)/\rceil - 2 = n$$ se convierte en $$\lfloor (n+1)/\rfloor + \lfloor (n+1)/\rfloor = n$$ Convirtió dos expresiones de techo en suelo restando de los techos respectivamente. Pero esta conversión es correcta sólo si $\frac{n+1}{}$ (y $\frac{n+1}{}$ ) es no entero para cada n, lo que significa que y son ambos irracionales. Pero no podemos garantizar que, de hecho, la propiedad de irracionalidad sea lo que Knuth nos pide que demostremos.

---

Así que deberíamos utilizar otro método para expresar los techos por facciones. $$\lceil\frac{n+1}{}\rceil=-\lfloor-\frac{n+1}{}\rfloor=- \Big( \big(-\frac{n+1}{}\big)- \{ -\frac{n+1}{} \}\Big)=\frac{n+1}{}+\{ -\frac{n+1}{} \}$$ $$\lceil\frac{n+1}{}\rceil=-\lfloor-\frac{n+1}{}\rfloor=- \Big( \big(-\frac{n+1}{}\big)- \{ -\frac{n+1}{} \}\Big)=\frac{n+1}{}+\{ -\frac{n+1}{} \}$$ así que $$\lceil \frac{n+1}{} \rceil + \lceil \frac{n+1}{} \rceil - 2 = n$$ implica $$\frac{n+1}{} + \{ -\frac{n+1}{} \} + \frac{n+1}{} + \{ -\frac{n+1}{} \} - 2 = n$$ El resto de la prueba es casi la misma, para los detalles, por favor vea la respuesta de ShreevatsaR.