miércoles, 14 de enero de 2009

Sucesiones recurrentes: funciones generatrices.

Hace no mucho os hablé de las Fracciones de Fibonacci, incluso los microsiervos también lo comentaron poco después.

Bueno, para el que no haya tenido tiempo o ganas de leerse el artículo original de Smoak y Olsen del que procede, os voy a contar el secreto de estas fracciones: Las funciones generatrices de sucesiones definidas por recurrencia.

Comencemos por lo básico. ¿Qué es una sucesión? pues ni más ni menos, que un conjunto infinito numerable de números (vamos a considerarlos reales) ordenados, es decir,
a0, a1,...,an,...


La sucesiones se pueden definir (rigurosamente) de muchas formas, quizás la más corriente se dando el término general enésimo de la sucesión en función de n. Por ejemplo, an=n2 sería la sucesión de todos los cuadrados perfectos. Pero otra de las formas más habituales de definir una sucesión es por recurrencia. ¿En qué consiste? pues en definir el término an en función de los términos anteriores a1,...,an; en principio no tienen porqué ser todos los anteriores, pero por lo general suelen usarse siempre (salvo, a lo más, algunos de los primeros términos de la sucesión) el mismo número de términos.

Mejor lo explicamos con un ejemplo clásico: La Sucesión e Fibonacci. Esta sucesión se define, por recurrencia, de la siguiente forma:
F0=1, F1=1, Fn=Fn-1+Fn-2 (n>2)
Como véis en este ejemplo, la sucesión, a partir del tecer término, se define por recurrencia usando los 2 términos inmediatamente anteriores, mientras que los primeros 2 términos de la sucesión se definen aparte.

Esto no tiene que ser siempre así, es decir, no siempre la recurrencia se basa en los 2 términos inmediatamente anteriores, pero es un caso ejemplar en el sentido que todo funciona igual pero con más sumandos. Así que vamos a estudiar el caso de la sucesión de Fibonacci, pero más generalizado.

A partir de ahora, vamos a considerar la sucesión siguiente:
an=c1an-1+c2an-2 (n>2)
con c1, c2 números reales no nulos
y a0=A, a1=B las condiciones iniciales.


Veamos ahora la segunda parte del título: ¿qué es una función generatriz? Pues dada una sucesión a0, a1,...,an,..., la función generatriz es la función (serie de potencias en realidad)
F(x)=a0+a1x+...+anxn+...


¿Y cómo calculamos la función generatriz de una de nuestras sucesiones por recurrencia? pues es muy sencillo:
F(x)=a0 + a1x + a2x2+...+ anxn +...
-c1xF(x)= -c1a0x-c1a1x2-...-c1an-1xn-...
-c2x2F(x)= -c2a0x2-...-c2an-1xn-...

Ahora basta con sumar todos los miembros y tener en cuenta que an=c1an-1+c2an-2 para escribir:
(1-c1x-c2x2)F(x)=A+(B-c1A)x
de donde basta despejar para obtener que la expresión de F(x).

Y ¿qué ocurre con la Sucesión de Fibonacci? pues basta tener en cuenta que, en este caso, c1=c2=A=B=1 para obtener que la Función Generatriz es
F(x)=1/(1-x-x2)


Pero ¿cómo ayuda esto en el problema de las Fracciones de Fibonacci? Pues basta tomar x=0.1, 0.01, 0.001,... en la función generatriz para obtener (veremos sólo el caso x=0.1):
100/89=1/(1-(.1)-(.1)2)=1 + 1(.1) + 2(.01) + 3(.001) + 5(.0001) + 8(.00001) + 13(.000001)+...
lo que explica que se obtengan los 5 primeros dígitos de la sucesión de Fibonacci en esta fracción.

Bonus Track: Como extra de esta anotación, gracias a que sabemos que la función característica de la Sucesión de Fibonacci es F(x)=1/(1-x-x2), basta calcular las raíces del polinomio del denominador (que son el número de oro φ y su opuesto de su inverso -1/φ ) para obtener que el término general de la sucesión de Fibonacci es
Fn=(φn-(-φ)-n)/√5


Tito Eliatron Dixit.

16 comentarios:

  1. Muuuuuuuy bueno, gracias Tito no conocía estas propiedades

    ResponderEliminar
  2. Algo no me cuadra o se me escapa..

    La sucesión de Fibonaci empieza 1,1,2,3,5,8... asi que F(x)=1+x+2x2+3x3+5x4+... es decir, como un polinomio con infinitos términos.

    Entonces F(10)=1+10+200+3000+50000+... (que bonito queda, el n-esimo sumando empieza por el termino n de la sucesion seguido de n ceros si nos olvidamos del primer 1) que tiende a infinito según vamos sumando.

    No me cuadra con que F(x)=1/(1-x-x2) porque F(10)=1/(1-10-100)=-1/109 que no es infinito, claro.

    Tito, ¿en que me equivoco?

    ResponderEliminar
  3. ¿No estaria F(x) definida solo para x que la hagan convergente o algo asi?

    Si, creo que eso es lo que me ha llevado a coger un ejemplo no convergente donde es imposible que se pueda hablar de F(x) con propiedad... creo.

    ResponderEliminar
  4. Efectivamente, Segrio, no es una función, es una serie de potencias (de McLaurin, por estar centrada en el 0) que tendrá su Radio de Convergencia, que ahora mismo no sabría decirte cual es, pero que intuyo que debe ser... 1/φ

    El Radio de Convergencia sería el inverso de
    Lim_{n\to\infty}F_{n+1}/F_n
    y este límite, en el caso de la sucesión de Fibonacci, creo que era el número áureo.

    ResponderEliminar
  5. Estoy bastante oxidado, la verdad, conforme me hablas de series de potencias con radios y del McLaurin este, todo me suena a conocido, pero chico, soy un matemático renegado, uso la calculadora hasta para comprar el pan!

    ResponderEliminar
  6. Una pregunta: puede verse en este ejemplo la propiedad de cualquier funcion caracteristica (generatriz?) de que asigna valores 0 ó 1 a diferentes funciones (o diferentes conjuntos de numeros reales)?
    Muchas Gracias.
    William.

    ResponderEliminar
  7. Me parece que estás confundiendo términos, William

    En este post se habla de "funciones generatrices de sucesiones recurrentes". Tú, creo, hablas de Funciones Características. Éstas últimas son funciones que asignan el valor 1 a un cierto conjunto y el valor 0 al complementario.

    por ejemplo, La función Característica del intervalo [0,1] es:
    .........{1 si 0≤x≤1
    f(x)={
    .........{0 si x<0 ó x>1

    Son conceptos distintos, William.

    ResponderEliminar
  8. Qué rápida fué la respuesta!! Gracias!!!
    Pero no sucede que en ambos casos (funciones generatrices y funciones caracteristicas)se puede hablar del concepto de convexidad?
    Para el caso de la funcion generatriz de este ejemplo, uno podria tal vez hablar de convexidad dentro del Radio de Convergencia (se me ocurre).
    William.

    ResponderEliminar
  9. Por supuesto, el concepto de Concavidad y Convexidad es un concepto de FUNCIONES, independientemente del tipo.

    ResponderEliminar
  10. conoce algun libro pasable sobre funciones generatrices o caracteristicas? yo estoy por ir a ver uno de lucaks...

    ResponderEliminar
  11. Pues específicamente de funciones generatrices no. Sobre Funciones Características, mejor mírate alguno que hable de la Medida y la Integral de Lebesgue.

    ResponderEliminar
  12. Lo poco que he leido sobre estos temas, es un apunte de Beppo Levi en el que trata la integral de Lebesgue, pero independientemente de la teoria de la medida de lebesgue!!!, y en una parte, presenta la relacion entre ambas teorias a modo de sintesis, diciendo que la medida exterior de lebesgue no es sino la integral superior de la funcion caracteristica, y a la inversa para la medida interior, etc. Pero en ningun momento describe ni nada parecido, a las funciones caracteristicas en cuestion.

    Y algo que he visto de teoria de la medida prop. dicha, creo que desarrollaba como a partir de sigma-albebras, algebras de borel, etc., etc., y no estoy seguro pero me parece que tampoco trataba lo de las funciones caracteristicas...

    en parte por eso me preguntaba si un libro sobre funciones caracteristicas no trataria el tema a partir del de convexidad (en su tratamiento sobre la sucecion de Fibonacci, por ejemplo, la formula de la funcion generatriz como serie de potencia, no difiere aparentemente mucho de lo que se llama combinacion convexa (de funciones o conjuntos de numeros reales).

    Gracias!!!

    ResponderEliminar
  13. No entiendo cómo obtienes Fn en el "Bonus Track"

    ResponderEliminar
  14. Anónimo, Descompón en fracciones simples y ten en cuente que 1/(1-t)=1+t+t^2+t^3+....

    ResponderEliminar
  15. Tras darle muchas vueltas, la expresión del "Bonus Track" para Fn corresponde a las condiciones iniciales a0=1, a1=1, que nos dan como función generatriz una expresión como la que aparece en el blog pero con x en el numerador.
    Considerando a0=1, a1=1, tendríamos otros coeficientes en Fn.

    ResponderEliminar
  16. Perdón, he escrito una errata. Escribo el texto de nuevo:
    Tras darle muchas vueltas, la expresión del "Bonus Track" para Fn corresponde a las condiciones iniciales a0=0, a1=1, que nos dan como función generatriz una expresión como la que aparece en el blog pero con x en el numerador.
    Considerando a0=1, a1=1, tendríamos otros coeficientes en Fn.

    ResponderEliminar

Si no comentas, Gauss se comerá una integral.
Y, por favor, respeta a todos con tus opiniones.