CyM98 << Adivinando sucesiones >>

 

Dificultad: Computación Matemática Matemática

Sólo se necesitan conocimientos elementales de computación. Los contenidos matemáticos pueden ser un poco más dificiles.

Lecciones anteriores:

Ninguna

 
Google
Web www.oma.org.ar

Resumen:

A veces uno tiene una lista de números y quiere encontrar la fórmula cerrada que los genera. Vamos a ver algunos trucos para encontrarla a ojo y después demostrarla por inducción.

Introducción:

Una de las mejores cosas que hace la computadora es hacer muchas cuentas sin distraerse, aburrirse, equivocarse (bueno, casi siempre) ni las otras cosas que le pasan a una persona cuando tiene que hacer 1000000 de veces una misma cuenta.

Por ejemplo si queremos calcular cual es la primera cifra de 100! (100!= 1*2*3*4*...*99*100) en una computadora es relativamente fácil, pero es muy difícil que al calcularlo una persona con calculadora no se saltee un número, multiplique alguno dos veces o cometa otro error (ni hablar si lo calcula a mano).

Esta habilidad de la computadora nos permite calcular los valores de una sucesión y luego tratar de ver a ojito cuál es su formula cerrada.

El problema de la suma

Por ejemplo si definimos

f(n)=1+2+3+...+(n-1)+n

o sea

f(1)=1 f(2)=1+2=3 f(10)=1+2+3+4+5+6+7+8+9+10=55

y hacemos una tabla obtenemos las dos primeras columnas de la siguiente tabla

  n|  f(n)|| ln(f(n))| ln(f(n))/ln(n)
---+------++---------+---------------
  1|     1||     0,00|          Error
  2|     3||     1,10|           1,58
  3|     6||     1,79|           1,63
  4|    10||     2,30|           1,66
  5|    15||     2,71|           1,68
...|   ...||      ...|            ...
 10|    55||     4,01|           1,74
 30|   465||     6,14|           1,80
100|  5050||     8,53|           1,85
300| 45150||    10,71|           1,87

Al calcular el logaritmo de f se observa que empieza creciendo rápido y luego más despacio, pero continua creciendo. Esta propiedad también la tiene el logaritmo de n así que probamos cuanto vale la relación entre ellas. Al ir creciendo se acerca cada ves más a 2, pero nunca lo cruza, lo que es bastante sospechoso.

Propiedades del logaritmo

Supongamos que tenemos una sucesión auxiliar g(n)=a nk donde a y k son constantes que no conocemos, entonces

ln(g(n))=ln(a nk)=ln(a)+k*ln(n)

de esta manera

ln(g(n))/ln(n)=ln(a)/ln(n)+k

Cuando n crece, ln(n) crece y por lo tanto

ln(g(n))/ln(n)~=k

Así que nuestra sucesión f se parece a a*n2. Para ver cuanto valdría a calculamos f(n)/n2

  n| f(n)|| f(n)/n^2| f(n)-n^2/2
---+-----++---------+---------------
  1|    1||     1,00|       0,50
  2|    3||     0,75|       1,00
  3|    6||     0,67|       1,50
  4|   10||     0,62|       2,00
  5|   15||     0,60|       2,50
...|  ...||      ...|        ...
 10|   55||     0,55|       5,00
 30|  465||     0,52|      15,00
100| 5050||     0,51|      50,00
300|45150||     0,50|     150,00

De vuelta f(n)/n2 tiende sospechosamente a 0,5 así que f(n)~=n2/2. Entonces calculamos la diferencia y vemos directamente que es n/2. Podría haber dado algo más complicado y deberíamos haber repetido el procedimiento anterior, todas las veces que fuera necesario, hasta obtener la función exacta.

 

  

Demostración por inducción

Así que ahora creemos que f(n)=n2/2+n/2. El problema es que todavía no demostramos nada, aunque el hecho de que ambas sucesiones coincidan en los primeros 1000 o 10000 términos es algo alentador. Para demostrarla vamos a utilizar el principio de inducción. Para ello debemos probar dos cosas

1)¿Nuestra formula vale cuando n=1?

Calculemos

f(n)=f(1) = 1 (la suma de los números desde 1 hasta 1)

n2/2+n/2=12/2+1/2=1/2+1/2=1

Como en ambos casos dio lo mismo, vale nuestra formula cuando n=1

2) ¿Si nuestra fórmula vale para algún n, entonces valdría para n+1?

O sea si para algún n valiera f(n)=n2/2+n/2, ¿Es verdad que f(n+1)=(n+1)2/2+(n+1)/2?

Calculemos f(n+1)=suma de los números desde 1 hasta n+1=
la separo en dos pedazos, los primeros n números y el último que es n+1
=(suma de los números desde 1 hasta n) + (n+1) = f(n) + (n+1)=
pero sabemos que f(n)=n2/2+n/2 entonces
=(n2/2+n/2)+(n+1)=n2/2+3n/2+1

Por otro lado calculemos

(n+1)2/2+(n+1)/2=(n2+2n+1)/2+(n+1)/2=(n2+3n+2)/2=n2/2+3n/2+1

Como en ambos casos nos dio lo mismo entonces Si nuestra fórmula vale para algún n, vale para n+1

Con esto queda probada la formula para todos los números enteros positivos.

(La idea del principio de inducción es que por el ítem 1 la formula vale para n=1, como ya sabemos que vale para n=1 usamos n=1 en el ítem 2 y demostramos que vale para n=2, como ya sabemos que vale para n=2 usamos n=2 en el ítem 2 y demostramos que vale para n=3, como ya sabemos que vale para n=3 usamos n=3 en el ítem 2 y demostramos que vale para n=4, como ya sabemos que vale para n=4 usamos n=4 en el ítem 2 y demostramos que vale para n=5, se entiende o hace falta que sigamos)

Comentarios

En general es un poco más complicado obtener la formula exacta, y a veces requiere varios pasos. En otros casos no existe una formula cerrada como la que aparece en este ejemplo. Por eso es importante demostrar que la formula que uno obtuvo realmente es la buscada. Por ejemplo si uno ve 2,4,8,... tiende a pensar en seguida en 2n, pero podes leer un ejemplo en donde esto falla en el cuento La rana saltarina del libro "Cuentos con cuentas" de Miguel de Guzmán.

También hay que reconocer que hay formas más directas de llegar a esta formula que pusimos como ejemplo, pero en casos más complicados es posible que uno no encuentre el camino correcto. También puede ser útil si uno sólo necesita una aproximación, aunque se debería luego demostrar que la aproximación es buena.


Ejercicios:

  1. Encontrar la formula de la suma de los primeros n cuadrados, de los primeros n impares y de los primeros n cubos. Demostrarlas. (Comparar la suma de los primeros n cubos con la suma de los primeros n números)

  2. Encontrar la formula cerrada de la sucesión de Fibonacci. Demostrarla (difícil).
    f(1)=1
    f(2)=2
    f(n+2)=f(n+1)+f(n) si n>1

  3. Encontrar una aproximación para n!. (Si necesitas una constante pensá en pi.)

  4. Llamamos p(n) al primo número n. Por ejemplo
    p(1)=2; p(2)=3; p(3)=5; p(4)=7; p(5)=11
    Encontrar una aproximación de p(n).


Lecciones siguientes:

Por ahora ninguna

 


La idea es que hagan los ejercicios y piensen que otras cosas interesantes se pueden hacer relacionadas con estos temas. Cuéntennos lo que consiguieron y pregunten lo que no les salió. Envíen sus preguntas, dudas, sugerencias, experiencias y propuestas. Nuestra dirección es cym98@oma.org.ar .

También nos gustaría saber tu opinión sobre esta clase. Les pedimos que se tomen unos instantes y contesten estas preguntas. Con tu ayuda podremos hacer un curso cada vez mejor.

¿Cuál es tu calificación general de esta clase?

No entendí nada   Mala   Regular   Buena   Muy buena

El contenido de esta clase te resultó:

Nuevo   Conocido en parte   Conocido

El contenido de esta clase te pareció:

Difícil   Regular   Fácil

Los ejercicios de esta clase te parecieron:

Difíciles   Regulares   Fáciles

Comentarios, preguntas, sugerencias:

Agregar más información o una nueva lección sobre:

Logaritmos (Log, Ln, ...)

Principio de Inducción

Nombre y apellido (opcional):

E-mail (opcional):

    


OmaNet   Curso CyM98 OmaNet - Educación Interactiva
   
www.oma.org.ar/omanet | omanet@oma.org.ar
mensajes: webmaster@oma.org.ar
duty free alcohol prices duty free cigarettes rules buy cigars online cosmetics duty free duty free fragrances duty free tobacco buy