Dificultad:

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

Lecciones anteriores:

Ninguna

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 n^k donde a y k son constantes que no conocemos, entonces

ln(g(n))=ln(a n^k)=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*n². Para ver cuanto valdría a calculamos f(n)/n²

  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)/n² tiende sospechosamente a 0,5 así que f(n)~=n²/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.

Así que ahora creemos que f(n)=n²/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)

n²/2+n/2=1²/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)=n²/2+n/2, ¿Es verdad que f(n+1)=(n+1)²/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)=n²/2+n/2 entonces
=(n²/2+n/2)+(n+1)=n²/2+3n/2+1

Por otro lado calculemos

(n+1)²/2+(n+1)/2=(n²+2n+1)/2+(n+1)/2=(n²+3n+2)/2=n²/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 2ⁿ, 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