Embed Size (px)
DESCRIPTION
Fibonacci
Citation preview
La sucesion de Fibonacci
Miguel Estela Bejarano, Jose Chulluncuy Centeno,
Percy Rıos Alan, Brian Salva
Algebra Lineal II - Profesor Vıctor G. Osorio Vidal
1
En 1202, Leonardo Fibonacci 1 plantea en su libro Liber Abaci siguiente problema:
Un par de conejos comienzan a procrear a la edad de un mes, y a partir de esemomento tienen como descendencia una nueva pareja de animalitos cada mes. Sicomenzamos con un par de conejos y ninguno de los conejos nacidos a partir deeste par muere, ¿cuantos pares de conejos tendremos al principio de cada mes?
Analizando el problema, sea P1 nuestra primera pareja de conejos entonces al prin-cipio del mes 0 tenemos al par de conejos P1 recien nacidos, al comenzar el mes 1tenemos nuestro mismo par de conejos P1 que aun no tiene descendientes. Al comen-zar el mes 2 tenemos al primer par P1 y su primeros descendientes P2, Al principiodel mes 3 tenemos el par original P1, su primer par de descendientes P2, nacidosal principio del mes 2, y su segundo par de descendientes, P3. Al inicio del mes 4tenemos a P1, P2, y P3; P4, descendiente de P1; y P5, el par descendiente de P2. Seaun el nmero de pares de conejos al inicio del mes n. Tenemos que:
u0 = 1, u1 = 1, u2 = 2, u3 = 5, u5 = 8, u6 = 13, u7 = 21
1Tambien conocido como Leonardo de Pisa o Leonardo Pisano, acompano a su padre (Quienfue nombrado director de asuntos comerciales en el norte de Africa) en su trabajo, gracias a eso elrecorrio el mediterraneo donde aprendio el metodo indoarabigo de numeracion y calculo, y decidiopromover su uso en Italia.
2
Para obtener una formula para un, procedemos de la siguiente manera. El numerode pares de conejos que estan vivos al incio del mes n es un-1, el numero de paresque estaban vivos el mes anterior, mas el numero de pares de recien nacidos al iniciodel mes n. Este ultimo numero es un-2, pues un par de conejos tiene un par dedescendientes a partir de su segundo mes de vida. En consecuencia.
un = un-1 + un-2 (1)
En pocas palabras cada numero es la suma de sus dos predecesores. La sucesionnumerica resultante es llamada sucesion de Fibonacci, la cual aparece en una ampliagama de aplicaciones2.
Ahora desarrollaremos una formula que nos permita calcular un en forma directa3.Ademas de la ecuacion (1) escribimos:
un−1 = un−1
Ası que ahora tenemos
un = un−1 + un−2
un−1 = un−1
que puede escribirse en forma matricial como
[un
un−1
]=
[1 11 0
] [un−1un−2
](2)
En general, definimos
wk =
[uk
uk+1
]y A =
[1 11 0
](0 ≤ k ≤ n-1)
de modo que
w0 =
[u1
u0
]=
[11
],
w1 =
[u2
u1
]=
[21
], . . . , wn−2 =
[un−1un−2
], y wn−1 =
[un
un−1
]Entonces podemos escribir (2) como
wn−1 = A wn−2
En consecuencia,
2Entre sus aplicaciones tenemos: la distribucion de hojas de algunos arboles, el orden de lassemillas de girasol, en las tecnicas de busqueda en analisis numerico, en la generacion de numerosaleatorios en estadıstica, en las bracteas hexagonales de las pinas, la espiral logartıcmica quepodemos encontrar en los caparazones de algunos animales, la arquitectura, la musica, el cuerpohumano y mas.
3Esta demostracion a sido extraıda del libro Algebra Lineal - Bernard Kolman, David R. Hill.
3
w1 = Aw0
w2 = Aw1 = A(Aw0) = A2w0
w3 = Aw2 = A(A2w0) = A3w0
...
wn−1 = Aw2 = An−1w0
(3)
Por lo tanto, para determinar un, basta calcular An−1, lo cual sigue siendo tediosopara n grande. Para evitar esta dificultad, determinamos una matriz diagonal Bsimilar a A. La ecuacion caracterıstica de A es:
p(λ) =
∣∣∣∣λ− 1 −1−1 λ
∣∣∣∣ = λ2 − λ− 1 = 0
λ =1±√
5
2
Los valores propios de A son:
λ1 = 1+√5
2y λ2 = 1−
√5
2
de modo que:
D =
[1+√5
20
0 1−√5
2
]El vector propio para λ1 [
1+√5
2− 1 −1
−1 1+√5
2
][xy
]=
[00
]x = 1+
√5
2y
x1 = y
[1+√5
2
1
]Analogamente para λ2 tendrıamos:
x2 = y
[1−√5
2
1
]Entonces Los vectores propios correspondientes son:
x1 =
[1+√5
2
1
]y x2 =
[1−√5
2
1
]En consecuencia,
P =
[1+√5
21−√5
2
1 1
], P−1 =
[1√5−1−
√5
2√5
− 1√5
1+√5
2√5
],
y
A = P D P−1
4
A(A) = A2 = PDP−1(PDP−1) = PD(P−1P)DP−1 = PD(I)DP−1 = PD2P−1
A2(A) = A3 = PD2P−1(PDP−1) = PD2(I)DP−1 = PD3P−1
...
Ak−1 = PDk−1P−1
Por lo tanto, para cualquier entero no negativo k,
Ak = P Dk P−1
Como D es diagonal, Dk se calcula facilmente; sus entradas son las entradas de ladiagonal de D, elevadas a la k-esima potencia. La ecuacion (3) implica
wn−1 = An−1 w0 = P Dn−1 P−1 w0
=
[1+√5
21−√5
2
1 1
] (1+√5
2
)n−10
0(
1−√5
2
)n−1 [ 1√
5−1−
√5
2√5
− 1√5
1+√5
2√5
] [11
]
Esto da como resultado la formula
un = 1√5
[(1+√5
2
)n+1
−(
1−√5
2
)n+1]
para calcular un de manera directa.
Ahora se han creado dos funciones en Matlab para hallar los valores de la sucesionde Fibonacci en n = 8, 12, 20.
5
Entonces los resultados en ambos casos son los mismos.
Ahora consideraremos el problema de los conejos, pero se procrean dos pares deconejos a partir del segundo mes de vida, y que continuan de esta forma cada mesposterior.
Analogamente al hallar la relacion recursiva para la sucesion de Fibonacci nota-mos que para nuestro nuevo problema la relacion es:
un = un−1 + 2un−2
Ahora desarrollaremos una formula directa para esta nueva relacion, teniendo encuenta
un−1 = un−1
Ası que ahora tenemos
un = un−1 + 2un−2
un−1 = un−1
que se puede escribir en forma matricial como
[un
un−1
]=
[1 21 0
] [un−1un−2
](4)
En general, definimos
wk =
[uk
uk+1
]y A =
[1 21 0
](0 ≤ k ≤ n-1)
6
de modo que
w0 =
[u1
u0
]=
[11
],
w1 =
[u2
u1
]=
[31
], . . . , wn−2 =
[un−1un−2
], y wn−1 =
[un
un−1
]Entonces podemos escribir (4) como
wn−1 = A wn−2
En consecuencia,
w1 = Aw0
w2 = Aw1 = A(Aw0) = A2w0
w3 = Aw2 = A(A2w0) = A3w0
...
wn−1 = Aw2 = An−1w0
(5)
Por lo tanto, para determinar un, basta calcular An−1, lo cual sigue siendo tediosopara n grande. Para evitar esta dificultad, determinamos una matriz diagonal Bsimilar a A. La ecuacion caracterıstica de A es:
p(λ) =
∣∣∣∣λ− 1 −2−1 λ
∣∣∣∣ = λ2 − λ− 2 = 0
λ =1±√
3
2
Los valores propios de A son:
λ1 =2 y λ2 = -1
de modo que:
D =
[2 00 −1
]El vector propio para λ1 [
1 −1−1 2
] [xy
]=
[00
]x = 2y
x1 = y
[21
]Analogamente para λ2 tendrıamos:
x2 = y
[1−1
]
7
Entonces Los vectores propios correspondientes son:
x1 =
[21
]y x2 =
[1−1
]En consecuencia,
P =
[2 11 −1
], P−1 =
[13
13
13−2
3
],
y
A = P D P−1
Por lo tanto, para cualquier entero no negativo k,
Ak = P Dk P−1
Como D es diagonal, Dk se calcula facilmente; sus entradas son las entradas de ladiagonal de D, elevadas a la k-esima potencia. La ecuacion (5) implica
wn−1 = An−1 w0 = P Dn−1 P−1 w0
=
[2 11 −1
] [(2)n−1 0
0 (−1)n−1
] [13
13
13−2
3
] [11
]Esto da como resultado la formula
un = 13
[(2)n+1 + (−1)n − 2(−1)n−1]
8
