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)/√5Tito Eliatron Dixit.
