Números de Fibonacci

Francisco Javier Pérez González
Departamento de Análisis Matemático
Universidad de Granada

Descripción de la práctica

En esta práctica estudiaremos la sucesión de Fibonacci con distintas técnicas que pueden generalizarse a otras sucesiones recurrentes de tipo lineal. Dicha sucesión aparece en el Liber abacci que el matemático italiano Leonardo de Pisa (1170 - 1250) conocido como Fibonacci, contracción de filius Bonacci, es decir el hijo de Bonacci, publicó en el año 1202; libro que tuvo extraordinaria influencia pues en él se introdujo por primera vez en Europa el sistema de numeración decimal indoarábigo que todavía usamos. En el citado libro aparece el siguiente problema:
"Una pareja de conejos tarda un mes en alcanzar la edad fértil y, a partir de ese momento, al final de cada mes engendra una pareja de conejos, que a su vez, tras ser fértiles, engendrarán al final de cada mes una pareja de conejos. ¿Cuántas parejas de conejos habrá al principio del n-ésimo mes?"
La respuesta a la pregunta anterior es un número que se llama el n-ésimo número de Fibonacci y se representa por (Subscript[F, n]) = F[n].  Dichos números aparecen en situaciones muy diversas (por ejemplo, están escondidos en el conjunto de Mandelbrot y relacionados con la proporción áurea) y son tantos los resultados interesantes relacionados con ellos que hay una revista The Fibonacci Quarterly publicada por la Fibonacci Association que está dedicada exclusivamente a publicarlos. En Internet puedes encontrar muchísima información sobre la sucesión de Fibonacci. Dos sitios interesantes son www-history.mcs.st-and.ac.uk./~history/Mathematicians/Fibonacci.html y www.ee.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html.

Ejercicio 1

Es claro que F[1] = F[2] = 1, F[3] = 2, F[4] = 3... 
a) Establece razonadamente una relación de recurrencia entre F[n],  F[n - 1] y F[n - 2]. Utiliza dicha relación para que Mathematica calcule los números de Fibonacci. Quiero que hagas esto de tres formas:
a1) Definiendo la relación de recurrencia con las condiciones iniciales sin pedirle a Mathematica que recuerde los valores ya calculados.
a2) Definiendo dicha relación de recurrencia con las condiciones iniciales de modo que cuando Mathematica calcule un valor F[n] recuerde los anteriores.
a3) Por medio de un bucle, usando un "For" o un "Do".
a4) Compara, usando el comando "Timing", el tiempo que invierte Mathematica en calcular los primeros 30 números de Fibonacci en el primer caso y los primeros 1000 números de Fibonacci en los otros dos casos. Comenta qué procedimiento te parece mejor. 
b) Calcula la solución de dicha relación de recurrencia y define una función "fib[n]" que sea igual a dicha solución (usa también "Simplify" para simplificarla y quitar raíces). Es decir, fib[n] te proporciona explícitamente como función de n el número F[n]. Calcula con Mathematica los primeros 30 valores de "fib[n]" y comprueba que coinciden con los antes obtenidos.

Sugerencias. Ensaya como solución (x^n) y deduce que x debe ser solución de la ecuación (x^2) - x - 1 = 0. Calcula con Mathematica dichas soluciones. Sean estas a y b. Comprueba con Mathematica que cualquier expresión de la forma α (a^n) + β (b^(n ))donde α y β son números reales cualesquiera es solución de la ecuación de recurrencia. Usa para ello "FullSimplify[expr1==expr2]". En Mathematica 5 puedes usar "FullSimplify[expr1==expr2,Assumptions]" donde "Assumptions" puede ser una información sobre el tipo de variables que aparecen en "expr1" o "expr2", por ejemplo, "n∈Integers". Esto no funciona en Mathematica 3 donde es preciso declarar explícitamente que n es un entero y ampliar la función IntegerQ como sigue:

entero[x_] := IntegerQ[x]entero[x_ y_] := entero[x] && entero[y]entero[x_  +  y_] := entero[x] && entero[y]

n /: IntegerQ[n] = True;

Calcula con Mathematica α y β (y simplifícalas) para que se cumplan las condiciones iniciales. Con algún detalle adicional ya puedes definir la función fib[n].

c) Si tratas de calcular (con Mathematica 3) fib[126] verás que no devuelve de forma explícita un número entero porque no realiza de forma completa la simplificación. Puedes evitar esto de la siguiente forma. Uno de los valores a o b que has calculado antes es menor que 1 en valor absoluto; supongamos que sea b este valor. Entonces b^n converge rápidamente a cero y, como fib[n] debe ser un entero, deducimos que fib[n] es el entero más próximo a α a^n + β b^n . La función Round[x] proporciona el entero más próximo a x. Puedes ahora modificar de forma apropiada la función fib[n] para que su salida sea siempre de forma explícita un entero. Calcula con ella los primeros 130 números de Fibonacci.

Nota. Al calcular fib[n] te habrá aparecido el número ((1 + (Sqrt[5]))/2)que se llama número áureo o razón áurea. Se ha escrito tanto sobre este número que yo no añadiré ni una palabra más. Si tienes curiosidad busca información en Internet. Por supuesto, Mathematica incluye la constante GoldenRatio.

Ejercicio 2

a) Expresa la relación de recurrencia del ejercicio anterior en la forma u[n]=Au[n - 1]   (n ≥ 2) donde u[n] = (({{F[n + 1]}, {F[n]}})) y A es una matriz apropiada. Por tanto  u[n] =(A^(n - 1))u[1], para todo n ≥ 2. En consecuencia, podemos calcular F[n] calculando (A^(n - 1))u[1] . Mathematica dispone de un comando específico para calcular potencias de una matriz. Utiliza dicho comando para definir una función "fibmatrix[n]" que proporcione como respuesta el número F[n] y úsala para calcular los primeros 120 números de Fibonacci.  
b) Es muy fácil calcular (A^(n - 1))u[1] si conocemos los valores propios de la matriz A. Sean λ y μ los valores propios de A con vectores propios (Subscript[x, λ]) y (Subscript[x, μ])  (que debes calcular con Mathematica). Calcula c, d tales que u[1]=c (Subscript[x, λ])+ d (Subscript[x, μ]) y comprueba que la segunda componente del vector (A^(n - 1))u[1] es igual a fib[n].
Sugerencia. Comprueba con Mathematica (usando "FullSimplify[expr1==expr2]") que \(TraditionalForm
      \`\(A\^\(n - 1\)\) u[1] = 
        c\ \(λ\^\(n - 1\)\) x\_λ\  + 
          \(d\ \(μ\^\(n - 1\)\) x\_μ\ \)\).