Otra forma de pensar Taylor

En primer lugar, en el post anterior había dejado planteado el siguiente problema:

Dado un conjunto de 51 números dentro del intervalo 1-100 (incluyendo los extremos), demostrar que existen al menos dos números en ese conjunto que no comparten ningún divisor (a excepción de 1, obviamente).

Así que, antes de empezar con el tema en sí de este post, no puedo hacer menos que presentar mi demostración 😉

El problema de los 51 números

La prueba que pensé se divide en dos pasos:

  • Paso 1: Determinar que al menos dos de los 51 números deben ser adyacentes.
  • Paso 2: Determinar que dos números adyacentes no comparten divisores no triviales.
Paso 1

Es intuitivamente razonable que, dados 51 números en un intervalo de 100, al menos dos deben ser adyacentes. Pero como la demostración que encontré no es muy elegante, la separé en una página auxiliar. (Dejo la primera demostración como ejemplo de cuanto más complejo de lo necesario puede hacerse algo…)

Definamos 100 variables 0-1 x1, x2, …, x100 para representar el subconjunto en cuestión. Claramente la condición sobre la cantidad de elementos puede representarse como

\displaystyle \sum_{i=1}^{100} x_i = 51

Si agrupamos la suma en 50 pares obtenemos

\displaystyle \sum_{i=0}^{49} x_{2i+1} + x_{2i+2} = \sum_{i=0}^{49} y_i = 51

Esto implica que el valor medio de los yi es 51/50 = 1.02 > 1. Pero como los yi solo pueden tomar los valores enteros 0, 1 y 2, eso implica que existe al menos un yi que vale 2. En consecuencia, existen necesariamente en el subconjunto dos números adyacentes.

Paso 2

Es bien conocido, y la base del algoritmo de Euclides, que

\mathrm{gcd}(a, b) = \mathrm{gcd}(a, b \% a),

donde \% se utiliza para indicar reducción modular al estilo C.

Ahora, si dos números a y b son adyacentes, entonces podemos decir sin pérdida de generalidad que b = a + 1. Por lo tanto:

\mathrm{gcd}(a, b) = \mathrm{gcd}(a, a+1) = \mathrm{gcd}(a, (a+1) \% a) = \mathrm{gcd}(a, 1) = 1.

Por ende, dos números adyacentes no pueden tener factores en común.

Conclusión

Como los 51 números en {1, 2, …, 100} deben incluir al menos un par de números adyacentes y los números adyacentes no tienen factores en común, entonces los 51 números en {1, 2, …, 100} deben incluir al menos un par de números sin factores comunes.

Taylor

Las demostraciones normales del Teorema de Taylor siempre me parecieron poco motivadas: son indudablemente correctas, pero no queda claro porqué uno iría por ese camino. Hace unos años encontré una demostración que, aunque no me cabe duda que debe haber sido conocida por los egipcios :-P, nunca vi en otro lado.

Para simplificar realicemos la expansión alrededor de cero (serie de Maclaurin). No cambia los resultados pero disminuye el “ruido” en las expresiones.

La idea básica es utilizar el hecho de que toda función derivable f(x) puede ser representada en función de su valor en 0 y su derivada del siguiente modo:

\displaystyle f(x) = f(0) + \int_0^x dx_1 f'(x_1)

Si la función puede ser derivada múltiples veces, el proceso puede ser aplicado en forma recursiva:

\displaystyle f'(x) = f'(0) + \int_0^x dx_1 f''(x_1)

\displaystyle f''(x) = f''(0) + \int_0^x dx_1 f'''(x_1)

\displaystyle \ldots

Combinando estas representaciones podemos representar a una función en término de su valor, el de las n-1 primeras derivadas en cero y su derivada n-ésima:

\displaystyle f(x) = f(0) + \int_0^x dx_1 \left( f'(0) + \int_0^{x_1} dx_2 \left( f''(0) + \ldots \right) \right)

Para poder simplificar estas expresiones es necesario resolver integrales de la forma

\displaystyle \int_0^x dx_1 \int_0^{x_1} dx_2 \ldots \int_0^{x_{n-1}} dx_n.

Esto podría hacerse por inducción pero, como estoy un poco quemado de utilizar esa técnica, podemos hacerlo por inspección simplemente:

\displaystyle \int_0^x dx_1 = x

\displaystyle \int_0^x dx_1 \int_0^{x_1} dx_2 = \int_0^x dx_1 x_1 = \frac{x^2}{2}

\displaystyle \int_0^x dx_1 \int_0^{x_1} dx_2 \int_0^{x_3} dx_3 = \int_0^x dx_1 \frac{x_1^2}{2} = \frac{x^3}{3 \cdot 2}

\displaystyle \int_0^x dx_1 \int_0^{x_1} dx_2 \int_0^{x_3} dx_3 \int_0^{x_4} dx_4 = \int_0^x dx_1 \frac{x_1^3}{3 \cdot 2} = \frac{x^4}{4 \cdot 3 \cdot 2}

Observando como opera esta progresión, no es difícil observar (o demostrar por inducción) que

\displaystyle \int_0^x dx_1 \int_0^{x_1} dx_2 \ldots \int_0^{x_{n-1}} dx_n = \frac{x^n}{n!}.

Si aplicamos esto a la expresión anterior de f(x) obtendremos

\displaystyle f(x) = f(0) + f'(0) x + f''(0) \frac{x^2}{2} + \ldots + \int_0^x dx_1 \ldots \int_0^{x_{n-1}} dx_n f^{(n)}(x_n),

donde f^{(n)} representa la derivada n-ésima de f.

Acotando la última integral, podemos ver que

\displaystyle \left| \int_0^{x_{n-1}} dx_n f^{(n)}(x_n) \right| < \int_0^{x_{n-1}} dx_n M = M x_{n-1},

siendo M una cota del valor absoluto de f^{(n)}(x) en el intervalo [0, x_{n-1}] (supongo x > 0 sin pérdida de generalidad). Eso implica que

\displaystyle \left| \int_0^x dx_1 \ldots \int_0^{x_{n-1}} dx_n f^{(n)}(x_n) \right| < M \int_0^x dx_1 \ldots \int_0^{x_{n-1}} dx_n,

donde M es ahora una cota del valor absoluto de f^{(n)}(x) en el intervalo [0, x]. Esta última integral podemos evaluarla explíctamente, dándonos una cota explícita para este último término en función de x y una cota para f^{(n)} en el intervalo [0, x]:

\displaystyle \left| \int_0^x dx_1 \ldots \int_0^{x_{n-1}} dx_n f^{(n)}(x_n) \right| < M \frac{x^n}{n!}.

Combinando todos estos resultados, y usando la nomenclatura f^{(0)} = f por consistencia, podemos decir que, si f es n veces derivable en un entorno de 0,

\displaystyle f(x) = \sum_{i=0}^{n-1} \frac{f^{(i)}(0)}{i!} + Err(x),

estando el término de error Err(x) acotado del siguiente modo:

\displaystyle |Err(x)| = \left| \int_0^x dx_1 \ldots \int_0^{x_{n-1}} dx_n f^{(n)}(x_n) \right| < M \frac{x^n}{n!}.

Esto significa que, si asumimos que la derivada n-ésima toma valores O(1), truncar la serie después del término con la derivada de orden n-1 nos dejará una aproximación O(x^n) a la función.

Próximo post

Con algo de suerte, será sobre la detección de cubos

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s