stringtranslate.com

Secuencia de Fibonacci

En matemáticas, la secuencia de Fibonacci es una secuencia en la que cada número es la suma de los dos anteriores. Los números que forman parte de la secuencia de Fibonacci se conocen como números de Fibonacci , comúnmente denotados F n . Muchos escritores comienzan la secuencia con 0 y 1, aunque algunos autores la comienzan desde 1 y 1 [1] [2] y algunos (como hizo Fibonacci) desde 1 y 2. A partir de 0 y 1, la secuencia comienza [3]

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....
Un mosaico con cuadrados cuyas longitudes de lados son números de Fibonacci sucesivos: 1, 1, 2, 3, 5, 8, 13 y 21

Los números de Fibonacci fueron descritos por primera vez en las matemáticas indias ya en el año 200 a. C. en un trabajo de Pingala sobre la enumeración de posibles patrones de poesía sánscrita formados por sílabas de dos longitudes. [4] [5] [6] Su nombre se debe al matemático italiano Leonardo de Pisa, también conocido como Fibonacci , quien introdujo la secuencia en las matemáticas de Europa occidental en su libro de 1202 Liber Abaci . [7]

Los números de Fibonacci aparecen inesperadamente a menudo en matemáticas, tanto que existe una revista entera dedicada a su estudio, Fibonacci Quarterly . Las aplicaciones de los números de Fibonacci incluyen algoritmos informáticos como la técnica de búsqueda de Fibonacci y la estructura de datos de montículo de Fibonacci , y gráficos llamados cubos de Fibonacci utilizados para interconectar sistemas paralelos y distribuidos. También aparecen en entornos biológicos , como la ramificación de los árboles, la disposición de las hojas en un tallo , los brotes de la fruta de una piña , la floración de una alcachofa y la disposición de las brácteas de una piña , aunque no se dan en todas las especies.

Los números de Fibonacci también están estrechamente relacionados con la proporción áurea : la fórmula de Binet expresa el n- ésimo número de Fibonacci en términos de n y la proporción áurea, e implica que la razón de dos números de Fibonacci consecutivos tiende a la proporción áurea a medida que n aumenta. Los números de Fibonacci también están estrechamente relacionados con los números de Lucas , que obedecen a la misma relación de recurrencia y con los números de Fibonacci forman un par complementario de secuencias de Lucas .

Definición

La espiral de Fibonacci: una aproximación de la espiral áurea creada al dibujar arcos circulares que conectan las esquinas opuestas de los cuadrados en el mosaico de Fibonacci (ver imagen anterior)

Los números de Fibonacci pueden definirse por la relación de recurrencia [8] y para n > 1 .

En algunas definiciones más antiguas, se omite el valor , de modo que la secuencia comienza con y la recurrencia es válida para n > 2. [ 9] [10]

Los primeros 20 números de Fibonacci F n son: [3]

Historia

India

Trece ( F 7 ) maneras de ordenar sílabas largas y cortas en una cadencia de longitud seis. Ocho ( F 6 ) terminan con una sílaba corta y cinco ( F 5 ) terminan con una sílaba larga.

La secuencia de Fibonacci aparece en las matemáticas indias , en conexión con la prosodia sánscrita . [5] [11] [12] En la tradición poética sánscrita, había interés en enumerar todos los patrones de sílabas largas (L) de 2 unidades de duración, yuxtapuestas con sílabas cortas (S) de 1 unidad de duración. Contando los diferentes patrones de L y S sucesivos con una duración total dada se obtienen los números de Fibonacci: el número de patrones de duración m unidades es F m +1 . [6]

El conocimiento de la secuencia de Fibonacci fue expresado ya por Pingala ( c.  450 a. C.–200 a. C.). Singh cita la fórmula críptica de Pingala misrau cha ("los dos están mezclados") y a los eruditos que la interpretan en contexto diciendo que el número de patrones para m pulsos ( F m +1 ) se obtiene añadiendo una [S] a los casos F m y una [L] a los casos F m −1 . [13] Bharata Muni también expresa conocimiento de la secuencia en el Natya Shastra (c. 100 a. C.–c. 350 d. C.). [14] [4] Sin embargo, la exposición más clara de la secuencia surge en la obra de Virahanka (c. 700 d. C.), cuyo propio trabajo se ha perdido, pero está disponible en una cita de Gopala (c. 1135): [12]

Las variaciones de dos metros anteriores [son la variación]... Por ejemplo, para [un metro de longitud] cuatro, al mezclar variaciones de metros de dos [y] tres, sucede cinco. [resuelve los ejemplos 8, 13, 21]... De esta manera, el proceso debe seguirse en todas las mātrā-vṛttas [combinaciones prosódicas]. [a]

A Hemachandra (c. 1150) también se le atribuye el conocimiento de la secuencia, [4] escribiendo que "la suma del último y el anterior al último es el número... del siguiente mātrā-vṛtta". [16] [17]

Europa

Una página del Liber Abaci de Fibonacci de la Biblioteca Nazionale di Firenze que muestra (en el recuadro de la derecha) 13 entradas de la secuencia de Fibonacci: los índices del presente al XII (meses) como ordinales latinos y números romanos y los números (de pares de conejos) como numerales indoarábigos que comienzan con 1, 2, 3, 5 y terminan con 377.

La secuencia de Fibonacci aparece por primera vez en el libro Liber Abaci ( El libro del cálculo , 1202) de Fibonacci [18] [19] donde se utiliza para calcular el crecimiento de las poblaciones de conejos. [20] [21] Fibonacci considera el crecimiento de una población de conejos idealizada ( biológicamente irreal) , asumiendo que: una pareja reproductora de conejos recién nacidos se coloca en un campo; cada pareja reproductora se aparea a la edad de un mes, y al final de su segundo mes siempre producen otra pareja de conejos; y los conejos nunca mueren, sino que continúan reproduciéndose para siempre. Fibonacci planteó el problema matemático del conejo : ¿cuántas parejas habrá en un año?

Al final del mes n , el número de parejas de conejos es igual al número de parejas maduras (es decir, el número de parejas en el mes n – 2 ) más el número de parejas vivas el mes pasado (mes n – 1 ). El número en el mes n es el n -ésimo número de Fibonacci. [22]

El nombre "secuencia de Fibonacci" fue utilizado por primera vez por el teórico de números del siglo XIX Édouard Lucas . [23]

Solución al problema del conejo de Fibonacci : en una población idealizada en crecimiento, el número de parejas de conejos forma la secuencia de Fibonacci. Al final del mes n, el número de parejas es igual a F n.

Relación con la proporción áurea

Expresión de forma cerrada

Como toda secuencia definida por una recurrencia lineal homogénea con coeficientes constantes , los números de Fibonacci tienen una expresión en forma cerrada . [24] Se la conoce como fórmula de Binet , llamada así por el matemático francés Jacques Philippe Marie Binet , aunque ya era conocida por Abraham de Moivre y Daniel Bernoulli : [25]

dónde

es la proporción áurea , y ψ es su conjugado : [26]

Dado que , esta fórmula también se puede escribir como

Para ver la relación entre la secuencia y estas constantes, [27] observe que φ y ψ son ambas soluciones de la ecuación y, por lo tanto, las potencias de φ y ψ satisfacen la recursión de Fibonacci. En otras palabras,

De ello se deduce que para cualesquiera valores a y b , la secuencia definida por

satisface la misma recurrencia,

Si se eligen a y b de modo que U 0 = 0 y U 1 = 1 , entonces la secuencia resultante U n debe ser la secuencia de Fibonacci. Esto es lo mismo que exigir que a y b satisfagan el sistema de ecuaciones:

que tiene solucion

produciendo la fórmula requerida.

Tomando los valores iniciales U0 y U1 como constantes arbitrarias, una solución más general es :

dónde

Cálculo por redondeo

Dado que para todo n ≥ 0 , el número F n es el entero más cercano a . Por lo tanto, se puede hallar redondeando , utilizando la función del entero más cercano:

De hecho, el error de redondeo se vuelve rápidamente muy pequeño a medida que n crece, siendo menor que 0,1 para n ≥ 4 y menor que 0,01 para n ≥ 8. Esta fórmula se invierte fácilmente para encontrar un índice de un número de Fibonacci F :

En lugar de utilizar la función floor se obtiene el índice más grande de un número de Fibonacci que no es mayor que F : donde , , [28] y . [29]

Magnitud

Como F n es asintótico a , el número de dígitos en F n es asintótico a . En consecuencia, para cada entero d > 1 hay 4 o 5 números de Fibonacci con d dígitos decimales.

De manera más general, en la representación de base b , el número de dígitos en F n es asintótico a

Límite de cocientes consecutivos

Johannes Kepler observó que la proporción de números consecutivos de Fibonacci converge . Escribió que "como 5 es a 8, así es 8 a 13, prácticamente, y como 8 es a 13, así es 13 a 21 casi", y concluyó que estas proporciones se aproximan a la proporción áurea [30] [31]

Esta convergencia se mantiene independientemente de los valores iniciales y , a menos que . Esto se puede verificar utilizando la fórmula de Binet. Por ejemplo, los valores iniciales 3 y 2 generan la secuencia 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, ... . La proporción de términos consecutivos en esta secuencia muestra la misma convergencia hacia la proporción áurea.

En general, , porque la relación entre números de Fibonacci consecutivos se aproxima a .

Teselación sucesiva del plano y gráfica de aproximaciones a la proporción áurea calculada dividiendo cada número de Fibonacci por el anterior.

Descomposición de potencias

Dado que la proporción áurea satisface la ecuación

Esta expresión se puede utilizar para descomponer potencias superiores como una función lineal de potencias inferiores, que a su vez se pueden descomponer hasta una combinación lineal de y 1. Las relaciones de recurrencia resultantes producen números de Fibonacci como coeficientes lineales : Esta ecuación se puede demostrar por inducción en n ≥ 1 : Para , también es el caso de que y también es el caso de que

Estas expresiones también son verdaderas para n < 1 si la secuencia de Fibonacci F n se extiende a números enteros negativos utilizando la regla de Fibonacci.

Identificación

La fórmula de Binet proporciona una prueba de que un entero positivo x es un número de Fibonacci si y solo si al menos uno de o es un cuadrado perfecto . [32] Esto se debe a que la fórmula de Binet, que se puede escribir como , se puede multiplicar por y resolver como una ecuación cuadrática en mediante la fórmula cuadrática :

Comparando esto con , se deduce que

En particular, el lado izquierdo es un cuadrado perfecto.

Forma matricial

Un sistema bidimensional de ecuaciones diferenciales lineales que describe la secuencia de Fibonacci es

denotado alternativamente

lo que da como resultado . Los valores propios de la matriz A son y correspondientes a los respectivos vectores propios

Como el valor inicial es

de ello se deduce que el término n es

A partir de esto, el n- ésimo elemento de la serie de Fibonacci puede leerse directamente como una expresión de forma cerrada :

De manera equivalente, el mismo cálculo se puede realizar mediante la diagonalización de A mediante el uso de su descomposición propia :

dónde

Por lo tanto, la expresión en forma cerrada para el n- ésimo elemento de la serie de Fibonacci viene dada por

Lo cual nuevamente produce

La matriz A tiene un determinante de −1, y por lo tanto es una matriz unimodular 2 × 2 .

Esta propiedad se puede entender en términos de la representación de fracción continua para la proporción áurea φ :

Los convergentes de la fracción continua para φ son cocientes de números de Fibonacci sucesivos: φ n = F n +1 / F n es el n -ésimo convergente, y el ( n  + 1) -ésimo convergente se puede hallar a partir de la relación de recurrencia φ n +1 = 1 + 1 / φ n . [33] La matriz formada a partir de convergentes sucesivos de cualquier fracción continua tiene un determinante de +1 o −1. La representación matricial da la siguiente expresión en forma cerrada para los números de Fibonacci:

Para un n dado , esta matriz se puede calcular en O (log n ) operaciones aritméticas, utilizando el método de exponenciación por cuadrado .

Tomando el determinante de ambos lados de esta ecuación se obtiene la identidad de Cassini ,

Además, dado que A n A m = A n + m para cualquier matriz cuadrada A , se pueden derivar las siguientes identidades (se obtienen a partir de dos coeficientes diferentes del producto matricial , y se puede deducir fácilmente la segunda a partir de la primera cambiando n por n + 1 ),

En particular, con m = n ,

Estas dos últimas identidades proporcionan una manera de calcular los números de Fibonacci recursivamente en O (log n ) operaciones aritméticas. Esto coincide con el tiempo necesario para calcular el n -ésimo número de Fibonacci a partir de la fórmula matricial de forma cerrada, pero con menos pasos redundantes si se evita volver a calcular un número de Fibonacci ya calculado (recursión con memorización ). [34]

Identidades combinatorias

Pruebas combinatorias

La mayoría de las identidades que involucran números de Fibonacci se pueden demostrar usando argumentos combinatorios utilizando el hecho de que se puede interpretar como el número de secuencias (posiblemente vacías) de 1 y 2 cuya suma es . Esto se puede tomar como la definición de con las convenciones , lo que significa que no existe tal secuencia cuya suma sea −1, y , lo que significa que la secuencia vacía "suma" 0. A continuación, es la cardinalidad de un conjunto :

De esta manera, la relación de recurrencia puede entenderse dividiendo las secuencias en dos conjuntos no superpuestos donde todas las secuencias comienzan con 1 o 2: Excluyendo el primer elemento, los términos restantes en cada secuencia suman o y la cardinalidad de cada conjunto es o dando un total de secuencias, mostrando que esto es igual a .

De manera similar se puede demostrar que la suma de los primeros números de Fibonacci hasta el n -ésimo es igual al ( n + 2) -ésimo número de Fibonacci menos 1. [35] En símbolos:

Esto se puede ver dividiendo todas las secuencias que suman en función de la ubicación de los primeros 2. Específicamente, cada conjunto consta de aquellas secuencias que comienzan hasta los dos últimos conjuntos, cada uno con cardinalidad 1.

Siguiendo la misma lógica que antes, sumando la cardinalidad de cada conjunto vemos que

...donde los dos últimos términos tienen el valor . De esto se deduce que .

Un argumento similar, agrupando las sumas por la posición del primer 1 en lugar de los primeros 2, da dos identidades más: y En palabras, la suma de los primeros números de Fibonacci con índice impar hasta es el (2 n ) -ésimo número de Fibonacci, y la suma de los primeros números de Fibonacci con índice par hasta es el (2 n + 1) -ésimo número de Fibonacci menos 1. [36]

Se puede utilizar un truco diferente para demostrar o, en palabras, que la suma de los cuadrados de los primeros números de Fibonacci hasta es el producto de los números de Fibonacci n -ésimo y ( n + 1) -ésimo. Para comprobarlo, se parte de un rectángulo de Fibonacci de tamaño y se descompone en cuadrados de tamaño ; de ahí se deduce la identidad comparando las áreas :

Método simbólico

La secuencia también se considera utilizando el método simbólico . [37] Más precisamente, esta secuencia corresponde a una clase combinatoria especificable . La especificación de esta secuencia es . De hecho, como se indicó anteriormente, el -ésimo número de Fibonacci es igual al número de composiciones combinatorias ( particiones ordenadas ) de utilizando los términos 1 y 2.

De ello se deduce que la función generadora ordinaria de la secuencia de Fibonacci, , es la función racional

Pruebas de inducción

Las identidades de Fibonacci a menudo se pueden demostrar fácilmente mediante inducción matemática .

Por ejemplo, reconsidere Sumar a ambos lados da

y entonces tenemos la fórmula para

De manera similar, agregue a ambos lados de para obtener

Pruebas de la fórmula de Binet

La fórmula de Binet es Esta se puede utilizar para demostrar identidades de Fibonacci.

Por ejemplo, para demostrar que la nota que el lado izquierdo se multiplica por se convierte en como se requiere, se utilizan los hechos y se simplifican las ecuaciones.

Otras identidades

Se pueden derivar muchas otras identidades utilizando diversos métodos. A continuación se presentan algunas de ellas: [38]

Las identidades de Cassini y Catalan

La identidad de Cassini afirma que la identidad de Catalan es una generalización:

La identidad de d'Ocagne

donde L n es el n - ésimo número de Lucas . El último es una identidad para duplicar n ; otras identidades de este tipo se obtienen mediante la identidad de Cassini.

Estos se pueden encontrar experimentalmente usando reducción de red , y son útiles para configurar el tamiz de campo numérico especial para factorizar un número de Fibonacci.

De manera más general, [38]

o alternativamente

Poniendo k = 2 en esta fórmula, se obtienen nuevamente las fórmulas del final de la sección anterior Forma matricial.

Función generadora

La función generadora de la secuencia de Fibonacci es la serie de potencias

Esta serie es convergente para cualquier número complejo que satisfaga y su suma tenga una forma cerrada simple: [39]

Esto se puede demostrar multiplicando por :

donde todos los términos que involucran se cancelan debido a la relación de recurrencia de Fibonacci definitoria.

La descomposición en fracciones parciales está dada por donde es la proporción áurea y es su conjugado .

La función relacionada es la función generadora de los números de negafibonacci y satisface la ecuación funcional

Si se utiliza el valor igual a 0,01, 0,001, 0,0001, etc., se muestran los primeros números de Fibonacci en la expansión decimal de . Por ejemplo,

Sumas recíprocas

Las sumas infinitas sobre números de Fibonacci recíprocos a veces se pueden evaluar en términos de funciones theta . Por ejemplo, la suma de cada número de Fibonacci recíproco de índice impar se puede escribir como

y la suma de los números recíprocos de Fibonacci al cuadrado como

Si sumamos 1 a cada número de Fibonacci en la primera suma, también existe la forma cerrada

y hay una suma anidada de números de Fibonacci al cuadrado que da el recíproco de la proporción áurea ,

La suma de todos los números de Fibonacci recíprocos de índice par es [40] con la serie de Lambert ya que

Por lo tanto, la constante recíproca de Fibonacci es [41]

Además, Richard André-Jeannin ha demostrado que este número es irracional . [42]

La serie de Millin da la identidad [43] que se sigue de la forma cerrada para sus sumas parciales cuando N tiende a infinito:

Números primos y divisibilidad

Propiedades de divisibilidad

Cada tercer número de la secuencia es par (un múltiplo de ) y, de manera más general, cada k -ésimo número de la secuencia es un múltiplo de F k . Por lo tanto, la secuencia de Fibonacci es un ejemplo de una secuencia de divisibilidad . De hecho, la secuencia de Fibonacci satisface la propiedad de divisibilidad más fuerte [44] [45] donde mcd es la función máximo común divisor .

En particular, tres números de Fibonacci consecutivos son coprimos entre sí porque tanto y . Es decir,

para cada n .

Todo número primo p divide a un número de Fibonacci que puede determinarse por el valor de p módulo  5. Si p es congruente con 1 o 4 módulo 5, entonces p divide a F p −1 , y si p es congruente con 2 o 3 módulo 5, entonces p divide a F p +1 . El caso restante es que p = 5 , y en este caso p divide a F p .

Estos casos se pueden combinar en una única fórmula no por partes , utilizando el símbolo de Legendre : [46]

Prueba de primalidad

La fórmula anterior se puede utilizar como una prueba de primalidad en el sentido de que si el símbolo de Legendre ha sido reemplazado por el símbolo de Jacobi , entonces esto es evidencia de que n es un primo, y si no se cumple, entonces n definitivamente no es un primo. Si n es compuesto y satisface la fórmula, entonces n es un pseudoprimo de Fibonacci . Cuando m es grande –digamos un número de 500 bits– entonces podemos calcular F m (mod n ) eficientemente usando la forma matricial. Por lo tanto

Aquí la potencia matricial A m se calcula utilizando exponenciación modular , que se puede adaptar a matrices . [47]

Primos de Fibonacci

Un primo de Fibonacci es un número de Fibonacci que es primo . Los primeros son: [48]

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, ...

Se han encontrado números primos de Fibonacci con miles de dígitos, pero no se sabe si hay infinitos. [49]

F kn es divisible por F n , por lo que, además de F 4 = 3 , cualquier primo de Fibonacci debe tener un índice primo. Como hayseries arbitrariamente largas de números compuestos , también hay series arbitrariamente largas de números compuestos de Fibonacci.

Ningún número de Fibonacci mayor que F 6 = 8 es uno mayor o uno menor que un número primo. [50]

El único número cuadrado de Fibonacci no trivial es 144. [51] Attila Pethő demostró en 2001 que solo existe un número finito de números de Fibonacci de potencias perfectas . [52] En 2006, Y. Bugeaud, M. Mignotte y S. Siksek demostraron que 8 y 144 son las únicas potencias perfectas no triviales. [53]

1, 3, 21 y 55 son los únicos números de Fibonacci triangulares , lo cual fue conjeturado por Vern Hoggatt y demostrado por Luo Ming. [54]

Ningún número de Fibonacci puede ser un número perfecto . [55] De manera más general, ningún número de Fibonacci distinto de 1 puede ser multiplicado por uno perfecto , [56] y ninguna relación de dos números de Fibonacci puede ser perfecta. [57]

Divisores primos

Con las excepciones de 1, 8 y 144 ( F 1 = F 2 , F 6 y F 12 ) cada número de Fibonacci tiene un factor primo que no es factor de ningún número de Fibonacci más pequeño ( teorema de Carmichael ). [58] Como resultado, 8 y 144 ( F 6 y F 12 ) son los únicos números de Fibonacci que son el producto de otros números de Fibonacci. [59]

La divisibilidad de los números de Fibonacci por un primo p está relacionada con el símbolo de Legendre, que se evalúa de la siguiente manera:

Si p es un número primo entonces [60] [61]

Por ejemplo,

No se sabe si existe un primo p tal que

Estos números primos (si los hay) se llamarían números primos Wall–Sol–Sol .

Además, si p ≠ 5 es un número primo impar entonces: [62]

Ejemplo 1. p = 7 , en este caso p ≡ 3 (mod 4) y tenemos:

Ejemplo 2. p = 11 , en este caso p ≡ 3 (mod 4) y tenemos:

Ejemplo 3. p = 13 , en este caso p ≡ 1 (mod 4) y tenemos:

Ejemplo 4. p = 29 , en este caso p ≡ 1 (mod 4) y tenemos:

Para n impar , todos los divisores primos impares de F n son congruentes con 1 módulo 4, lo que implica que todos los divisores impares de F n (como los productos de los divisores primos impares) son congruentes con 1 módulo 4. [63]

Por ejemplo,

Todos los factores conocidos de los números de Fibonacci F ( i ) para todos los i < 50000 se recopilan en los repositorios pertinentes. [64] [65]

Módulo de periodicidadnorte

Si los miembros de la secuencia de Fibonacci se toman módulo  n , la secuencia resultante es periódica con período como máximo  6 n . [66] Las longitudes de los períodos para varios n forman los llamados períodos de Pisano . [67] Determinar una fórmula general para los períodos de Pisano es un problema abierto , que incluye como subproblema una instancia especial del problema de encontrar el orden multiplicativo de un entero modular o de un elemento en un cuerpo finito . Sin embargo, para cualquier n particular , el período de Pisano puede encontrarse como una instancia de detección de ciclos .

Generalizaciones

La sucesión de Fibonacci es una de las sucesiones más simples y antiguas conocidas definidas por una relación de recurrencia y, específicamente, por una ecuación diferencial lineal . Todas estas sucesiones pueden considerarse como generalizaciones de la sucesión de Fibonacci. En particular, la fórmula de Binet puede generalizarse a cualquier sucesión que sea una solución de una ecuación diferencial lineal homogénea con coeficientes constantes .

Algunos ejemplos específicos que se acercan, en cierto sentido, a la secuencia de Fibonacci incluyen:

Aplicaciones

Matemáticas

Los números de Fibonacci son las sumas de las diagonales (mostradas en rojo) de un triángulo de Pascal justificado a la izquierda .

Los números de Fibonacci aparecen como sumas de coeficientes binomiales en las diagonales "superficiales" del triángulo de Pascal : [69] Esto se puede demostrar expandiendo la función generadora y recopilando términos similares de .

Para ver cómo se utiliza la fórmula, podemos ordenar las sumas por el número de términos presentes:

que es , donde estamos eligiendo las posiciones de k dos de nk −1 términos.

Uso de la secuencia de Fibonacci para contar composiciones restringidas por {1, 2}

Estos números también dan la solución a ciertos problemas enumerativos, [70] el más común de los cuales es el de contar el número de maneras de escribir un número dado n como una suma ordenada de 1 y 2 (llamadas composiciones ); hay F n +1 maneras de hacer esto (equivalentemente, también es el número de teselaciones de dominó del rectángulo). Por ejemplo, hay F 5+1 = F 6 = 8 maneras de subir una escalera de 5 escalones, dando uno o dos escalones a la vez:

La figura muestra que 8 se puede descomponer en 5 (el número de maneras de subir 4 escalones, seguido de un solo escalón) más 3 (el número de maneras de subir 3 escalones, seguido de un doble escalón). El mismo razonamiento se aplica recursivamente hasta llegar a un solo escalón, del cual solo hay una manera de subir.

Los números de Fibonacci se pueden encontrar de diferentes maneras entre el conjunto de cadenas binarias , o equivalentemente, entre los subconjuntos de un conjunto dado.

Ciencias de la Computación

Árbol de Fibonacci de altura 6. Factores de equilibrio en verde; alturas en rojo.
Las claves en la columna izquierda son números de Fibonacci.

Naturaleza

Cabeza de manzanilla amarilla que muestra la disposición en 21 espirales (azules) y 13 (cian). Este tipo de disposiciones que implican números consecutivos de Fibonacci aparecen en una amplia variedad de plantas.

Las secuencias de Fibonacci aparecen en entornos biológicos, [80] como la ramificación de los árboles, la disposición de las hojas en un tallo , los frutos de una piña , [81] la floración de la alcachofa , la disposición de una piña , [82] y el árbol genealógico de las abejas . [83] [84] Kepler señaló la presencia de la secuencia de Fibonacci en la naturaleza, utilizándola para explicar la forma pentagonal (relacionada con la proporción áurea ) de algunas flores. [85] Las margaritas de campo suelen tener pétalos en recuentos de números de Fibonacci. [86] En 1830, Karl Friedrich Schimper y Alexander Braun descubrieron que las parastiquias ( filotaxis espiral ) de las plantas se expresaban con frecuencia como fracciones que involucraban números de Fibonacci. [87]

Przemysław Prusinkiewicz propuso la idea de que las instancias reales pueden entenderse en parte como la expresión de ciertas restricciones algebraicas sobre grupos libres , específicamente como ciertas gramáticas de Lindenmayer . [88]

Ilustración del modelo de Vogel para n = 1 ... 500

 Helmut Vogel [de] propuso en 1979 un modelo para el patrón de florecillas en la cabeza de un girasol. [89] Este tiene la forma

donde n es el número de índice del flósculo y c es un factor de escala constante; los flósculos se encuentran, por tanto, en la espiral de Fermat . El ángulo de divergencia , aproximadamente 137,51°, es el ángulo áureo , que divide el círculo en la proporción áurea. Debido a que esta proporción es irracional, ningún flósculo tiene un vecino exactamente en el mismo ángulo desde el centro, por lo que los flósculos se empaquetan de manera eficiente. Debido a que las aproximaciones racionales a la proporción áurea son de la forma F (  j ): F (  j + 1) , los vecinos más cercanos del flósculo número n son aquellos en n ± F (  j ) para algún índice j , que depende de r , la distancia desde el centro. Los girasoles y flores similares tienen más comúnmente espirales de flósculos en sentido horario y antihorario en la cantidad de números de Fibonacci adyacentes, [90] típicamente contados por el rango más externo de radios. [91]

Los números de Fibonacci también aparecen en los pedigríes ancestrales de las abejas (que son haplodiploides ), según las siguientes reglas:

Por lo tanto, una abeja macho siempre tiene un progenitor, y una abeja hembra tiene dos. Si uno rastrea el pedigrí de cualquier abeja macho (1 abeja), tiene 1 progenitor (1 abeja), 2 abuelos, 3 bisabuelos, 5 tatarabuelos, y así sucesivamente. Esta secuencia de números de progenitores es la secuencia de Fibonacci. El número de ancestros en cada nivel, F n , es el número de ancestros femeninos, que es F n −1 , más el número de ancestros masculinos, que es F n −2 . [92] [93] Esto se hace bajo la suposición poco realista de que los ancestros en cada nivel no están relacionados de ninguna otra manera.

El número de posibles ancestros en la línea de herencia del cromosoma X en una generación ancestral dada sigue la secuencia de Fibonacci. (Según Hutchison, L. "Growing the Family Tree: The Power of DNA in Reconstructing Family Relationships". [94] )

De manera similar, se ha observado que el número de posibles ancestros en la línea de herencia del cromosoma X humano en una generación ancestral dada también sigue la secuencia de Fibonacci. [94] Un individuo masculino tiene un cromosoma X, que recibió de su madre, y un cromosoma Y , que recibió de su padre. El hombre cuenta como el "origen" de su propio cromosoma X ( ), y en la generación de sus padres, su cromosoma X provenía de un solo progenitor ( ) . La madre del hombre recibió un cromosoma X de su madre (la abuela materna del hijo) y uno de su padre (el abuelo materno del hijo), por lo que dos abuelos contribuyeron al cromosoma X del descendiente masculino ( ) . El abuelo materno recibió su cromosoma X de su madre, y la abuela materna recibió cromosomas X de ambos padres, por lo que tres bisabuelos contribuyeron al cromosoma X del descendiente masculino ( ) . Cinco tatarabuelos contribuyeron al cromosoma X del descendiente masculino ( ) , etc. (Esto supone que todos los antepasados ​​de un descendiente dado son independientes, pero si se rastrea alguna genealogía lo suficientemente atrás en el tiempo, los antepasados ​​comienzan a aparecer en múltiples líneas de la genealogía, hasta que finalmente un fundador de la población aparece en todas las líneas de la genealogía).

Otro

Véase también

Referencias

Notas explicativas

  1. ^ "Para cuatro, las variaciones de los metros dos [y] tres que se mezclan, se obtienen cinco. Para cinco, las variaciones de dos anteriores, tres [y] cuatro, que se mezclan, se obtienen ocho. De esta manera, para seis, [las variaciones] de cuatro [y] de cinco que se mezclan, se obtienen trece. Y de la misma manera, las variaciones de dos metros anteriores que se mezclan, siete morae [son] veintiuno. De esta manera, el proceso debe seguirse en todos los mātrā-vṛttas" [15]

Citas

  1. ^ Richard A. Brualdi, Introductory Combinatorics , quinta edición, Pearson, 2005
  2. ^ Peter Cameron, Combinatoria: temas, técnicas, algoritmos , Cambridge University Press, 1994
  3. ^ ab Sloane, N. J. A. (ed.), "Secuencia A000045 (números de Fibonacci: F(n) = F(n-1) + F(n-2) con F(0) = 0 y F(1) = 1)", La enciclopedia en línea de secuencias de números enteros , OEIS Foundation
  4. ^ abc Goonatilake, Susantha (1998), Hacia una ciencia global, Indiana University Press, pág. 126, ISBN 978-0-253-33388-9
  5. ^ ab Singh, Parmanand (1985), "Los llamados números de Fibonacci en la India antigua y medieval", Historia Mathematica , 12 (3): 229–44, doi : 10.1016/0315-0860(85)90021-7
  6. ^ ab Knuth, Donald (2006), El arte de la programación informática, vol. 4. Generación de todos los árboles: historia de la generación combinatoria, Addison–Wesley, pág. 50, ISBN 978-0-321-33570-8, era natural considerar el conjunto de todas las secuencias de [L] y [S] que tienen exactamente m pulsos. ... hay exactamente Fm+1 de ellas. Por ejemplo, las 21 secuencias cuando m = 7 son: [da la lista]. De esta manera, los prosodistas indios fueron llevados a descubrir la secuencia de Fibonacci, como hemos observado en la Sección 1.2.8 (de la v.1)
  7. ^ Sigler 2002, págs. 404-405.
  8. ^ Lucas 1891, pág. 3.
  9. ^ Beck y Geoghegan 2010.
  10. ^ Bóna 2011, pág. 180.
  11. ^ Knuth, Donald (1968), El arte de la programación informática, vol. 1, Addison Wesley, pág. 100, ISBN 978-81-7758-754-8, Antes de que Fibonacci escribiera su obra, la secuencia Fn ya había sido discutida por los eruditos indios, quienes desde hacía mucho tiempo estaban interesados ​​en los patrones rítmicos... tanto Gopala (antes de 1135 d. C.) como Hemachandra (c. 1150) mencionaron los números 1, 2, 3, 5, 8, 13, 21 explícitamente [ver P. Singh Historia Math 12 (1985) 229–44]" p. 100 (3.ª ed.) ...
  12. ^ desde Livio 2003, pág. 197.
  13. ^ Agrawala, V. S. (1969),Pāṇinikālīna Bhāratavarṣa (Hn.). Varanasi-I: El Chowkhamba Vidyabhawan , Sadgurushi Shya escribe que Pingala era un hermano menor de Pāṇini [Agrawala 1969, lb]. Existe una opinión alternativa de que era un tío materno de Pāṇini [Vinayasagar 1965, Prefacio, 121]. ... Agrawala [1969, 463–76], después de una cuidadosa investigación, en la que consideró las opiniones de eruditos anteriores, ha concluido que Pāṇini vivió entre 480 y 410 a. C.
  14. ^ Singh, Parmanand (1985), "Los llamados números de Fibonacci en la India antigua y medieval", Historia Mathematica , 12 (3), Academic Press : 232, doi : 10.1016/0315-0860(85)90021-7
  15. ^ Velankar, HD (1962),'Vṛttajātisamuccaya' de kavi Virahanka , Jodhpur: Instituto de Investigaciones Orientales de Rajasthan, p. 101
  16. ^ Livio 2003, pág. 197–198.
  17. ^ Shah, Jayant (1991), A History of Piṅgala's Combinatorics (PDF) , Northeastern University , p. 41 , consultado el 4 de enero de 2019
  18. ^ Sigler 2002, págs. 404–405.
  19. ^ "Liber Abaci (Libro de cálculo) de Fibonacci", The University of Utah , 13 de diciembre de 2009 , consultado el 28 de noviembre de 2018
  20. ^ Hemenway, Priya (2005), Proporción divina: Phi en el arte, la naturaleza y la ciencia , Nueva York: Sterling, págs. 20-21, ISBN 1-4027-3522-7
  21. ^ Knott, Ron (25 de septiembre de 2016), "Los números de Fibonacci y la sección áurea en la naturaleza – 1", Universidad de Surrey , consultado el 27 de noviembre de 2018
  22. ^ Knott, Ron, Los conejos de Fibonacci, Facultad de Ingeniería y Ciencias Físicas de la Universidad de Surrey
  23. ^ Gardner, Martin (1996), Circo matemático , Asociación Matemática de América, pág. 153, ISBN 978-0-88385-506-5Es irónico que Leonardo, que hizo valiosas contribuciones a las matemáticas, sea recordado hoy principalmente porque un teórico de números francés del siglo XIX, Édouard Lucas... adjuntó el nombre Fibonacci a una secuencia numérica que aparece en un problema trivial en el Liber abaci .
  24. ^ Sarah-Marie Belcastro (2018). Matemática discreta con patos (2.ª edición ilustrada). CRC Press. pág. 260. ISBN 978-1-351-68369-2.Extracto de la página 260
  25. ^ Beutelspacher, Albrecht; Petri, Bernhard (1996), "Fibonacci-Zahlen", Der Goldene Schnitt , Einblick in die Wissenschaft, Vieweg+Teubner Verlag, págs. 87–98, doi :10.1007/978-3-322-85165-9_6, ISBN 978-3-8154-2511-4
  26. ^ Bola 2003, pág. 156.
  27. ^ Ball 2003, págs. 155-156.
  28. ^ Sloane, N. J. A. (ed.), "Secuencia A002390 (Expansión decimal del logaritmo natural de la proporción áurea)", La enciclopedia en línea de secuencias de números enteros , OEIS Foundation
  29. ^ Sloane, N. J. A. (ed.), "Secuencia A097348 (Expansión decimal de arccsch(2)/log(10))", La enciclopedia en línea de secuencias de números enteros , OEIS Foundation
  30. ^ Kepler, Johannes (1966), Un regalo de Año Nuevo: sobre nieve hexagonal , Oxford University Press, pág. 92, ISBN 978-0-19-858120-8
  31. Strena seu de Nive Sexangula , 1611
  32. ^ Gessel, Ira (octubre de 1972), "Fibonacci es un cuadrado" (PDF) , The Fibonacci Quarterly , 10 (4): 417–19 , consultado el 11 de abril de 2012
  33. ^ "La proporción áurea, los números de Fibonacci y las fracciones continuas". nrich.maths.org . Consultado el 22 de marzo de 2024 .
  34. ^ Dijkstra, Edsger W. (1978), En honor a Fibonacci (PDF)
  35. ^ Lucas 1891, pág. 4.
  36. ^ Vorobiev, Nikolaĭ Nikolaevich; Martin, Mircea (2002), "Capítulo 1", Números de Fibonacci , Birkhäuser, págs. 5–6, ISBN 978-3-7643-6135-8
  37. ^ Flajolet, Philippe; Sedgewick, Robert (2009), Combinatoria analítica , Cambridge University Press, pág. 42, ISBN 978-0521898065
  38. ^ abc Weisstein, Eric W. , "Número de Fibonacci", MathWorld
  39. ^ Glaister, P (1995), "Serie de potencias de Fibonacci", The Mathematical Gazette , 79 (486): 521–25, doi :10.2307/3618079, JSTOR  3618079, S2CID  116536130
  40. ^ Landau (1899) citado según Borwein, página 95, ejercicio 3b.
  41. ^ Sloane, N. J. A. (ed.), "Secuencia A079586 (Expansión decimal de Sum_{k>=1} 1/F(k) donde F(k) es el k-ésimo número de Fibonacci)", La enciclopedia en línea de secuencias de números enteros , OEIS Foundation
  42. ^ André-Jeannin, Richard (1989), "Irrationalité de la somme des inverses de sures suites récurrentes", Comptes Rendus de l'Académie des Sciences, Série I , 308 (19): 539–41, SEÑOR  0999451
  43. ^ Honsberger, Ross (1985), "Serie de Millin", Gemas matemáticas III , Dolciani Mathematical Expositions, vol. 9, American Mathematical Society, págs. 135-136, ISBN 9781470457181
  44. ^ Ribenboim, Paulo (2000), Mis números, mis amigos , Springer-Verlag
  45. ^ Su, Francis E (2000), "Fibonacci MCD's, please", Mudd Math Fun Facts, et al, HMC, archivado desde el original el 2009-12-14 , consultado el 2007-02-23
  46. ^ Williams, HC (1982), "Una nota sobre el cociente de Fibonacci ", Canadian Mathematical Bulletin , 25 (3): 366–70, doi : 10.4153/CMB-1982-053-0 , hdl : 10338.dmlcz/137492 , MR  0668957Williams llama a esta propiedad "bien conocida".
  47. ^ Números primos , Richard Crandall, Carl Pomerance, Springer, segunda edición, 2005, pág. 142.
  48. ^ Sloane, N. J. A. (ed.), "Secuencia A005478 (números primos de Fibonacci)", La enciclopedia en línea de secuencias de números enteros , OEIS Foundation
  49. ^ Diaconis, Persi (2018), "Probabilizing Fibonacci numbers" (PDF) , en Butler, Steve ; Cooper, Joshua; Hurlbert, Glenn (eds.), Connections in Discrete Mathematics: A Celebration of the Work of Ron Graham , Cambridge University Press, págs. 1–12, ISBN 978-0-852-2-3 978-1-107-15398-1, MR  3821829, archivado desde el original (PDF) el 18 de noviembre de 2023 , consultado el 23 de noviembre de 2022
  50. ^ Honsberger, Ross (1985), "Joyas matemáticas III", Exposiciones matemáticas AMS Dolciani (9): 133, ISBN 978-0-88385-318-4
  51. ^ Cohn, JHE (1964), "Sobre los números cuadrados de Fibonacci", The Journal of the London Mathematical Society , 39 : 537–540, doi :10.1112/jlms/s1-39.1.537, MR  0163867
  52. ^ Pethő, Attila (2001), "Propiedades diofánticas de secuencias recursivas lineales II", Acta Mathematica Academiae Paedagogicae Nyíregyháziensis , 17 : 81–96
  53. ^ Bugeaud, Y; Mignotte, M; Siksek, S (2006), "Enfoques clásicos y modulares para ecuaciones diofánticas exponenciales. I. Potencias perfectas de Fibonacci y Lucas", Ann. Math. , 2 (163): 969–1018, arXiv : math/0403046 , Bibcode :2004math......3046B, doi :10.4007/annals.2006.163.969, S2CID  10266596
  54. ^ Luo, Ming (1989), "Sobre los números triangulares de Fibonacci" (PDF) , Fibonacci Quart. , 27 (2): 98–108, doi :10.1080/00150517.1989.12429576
  55. ^ Luca, Florian (2000), "Números perfectos de Fibonacci y Lucas", Rediconti del Circolo Matematico di Palermo , 49 (2): 313–18, doi :10.1007/BF02904236, ISSN  1973-4409, MR  1765401, S2CID  121789033
  56. ^ Broughan, Kevin A.; González, Marcos J.; Lewis, Ryan H.; Luca, Florian; Mejía Huguet, V. Janitzio; Togbé, Alain (2011), "No existen números de Fibonacci que sean multiplicativamente perfectos", Integers , 11a : A7, MR  2988067
  57. ^ Luca, Florian; Mejía Huguet, V. Janitzio (2010), "Sobre los números perfectos que son cocientes de dos números de Fibonacci", Annales Mathematicae at Informaticae , 37 : 107–24, ISSN  1787-6117, MR  2753031
  58. ^ Knott, Ron, Los números de Fibonacci, Reino Unido: Surrey
  59. ^ Sloane, N. J. A. (ed.), "Secuencia A235383 (números de Fibonacci que son el producto de otros números de Fibonacci)", The On-Line Encyclopedia of Integer Sequences , OEIS Foundation
  60. ^ Ribenboim, Paulo (1996), El nuevo libro de registros de números primos , Nueva York: Springer, pág. 64, ISBN 978-0-387-94457-9
  61. ^ Lemmermeyer 2000, págs. 73–74, ej. 2.25–28.
  62. ^ Lemmermeyer 2000, págs. 73–74, ej. 2.28.
  63. ^ Lemmermeyer 2000, pág. 73, ej. 2.27.
  64. ^ Factorizaciones de Fibonacci y Lucas, Mersennusrecoge todos los factores conocidos de F ( i ) con i < 10000 .
  65. ^ Factores de los números de Fibonacci y Lucas, Red golperecoge todos los factores conocidos de F ( i ) con 10000 < i < 50000 .
  66. ^ Freyd, Peter; Brown, Kevin S. (1993), "Problemas y soluciones: Soluciones: E3410", The American Mathematical Monthly , 99 (3): 278–79, doi :10.2307/2325076, JSTOR  2325076
  67. ^ Sloane, N. J. A. (ed.), "Secuencia A001175 (Períodos de Pisano (o números de Pisano): período de los números de Fibonacci mod n)", La enciclopedia en línea de secuencias de números enteros , OEIS Foundation
  68. ^ Lü, Kebo; Wang, Jun (2006), "Secuencia de Fibonacci de k pasos módulo m", Utilitas Mathematica , 71 : 169–177, MR  2278830
  69. ^ Lucas 1891, pág. 7.
  70. ^ Stanley, Richard (2011), Combinatoria enumerativa I (2.ª ed.) , Cambridge Univ. Press, pág. 121, Ex 1.35, ISBN 978-1-107-60262-5
  71. ^ Harizanov, Valentina (1995), "Revisión de Yuri V. Matiyasevich, El décimo problema de Hibert", Modern Logic , 5 (3): 345–55
  72. ^ Pagni, David (septiembre de 2001), "Fibonacci se encuentra con Pitágoras", Matemáticas en la escuela , 30 (4): 39–40, JSTOR  30215477
  73. ^ Stephenson, Kenneth (2005), Introducción al empaquetamiento circular: la teoría de funciones analíticas discretas , Cambridge University Press, ISBN 978-0-521-82356-2, Sr.  2131318; véase especialmente el Lema 8.2 (El Lema del Anillo), págs. 73-74, y el Apéndice B, El Lema del Anillo, págs. 318-321.
  74. ^ Knuth, Donald E (1997), El arte de la programación informática , vol. 1: Algoritmos fundamentales (3.ª ed.), Addison–Wesley, pág. 343, ISBN 978-0-201-89683-1
  75. ^ Adelson-Velsky, Georgy; Landis, Evgenii (1962), "Un algoritmo para la organización de la información", Actas de la Academia de Ciencias de la URSS (en ruso), 146 : 263–266Traducción al inglés de Myron J. Ricci en Soviet Mathematics - Doklady , 3:1259–1263, 1962.
  76. ^ Avriel, M; Wilde, DJ (1966), "Optimalidad de la técnica de búsqueda simétrica de Fibonacci", Fibonacci Quarterly (3): 265–69, doi :10.1080/00150517.1966.12431364
  77. ^ Manual de referencia del núcleo ROM de Amiga , Addison–Wesley, 1991
  78. ^ "IFF", Wiki multimedia
  79. ^ Dean Leffingwell (1 de julio de 2021), Historia, Scaled Agile Framework , consultado el 15 de agosto de 2022
  80. ^ Douady, S; Couder, Y (1996), "La filotaxis como un proceso dinámico de autoorganización" (PDF) , Journal of Theoretical Biology , 178 (3): 255–74, doi :10.1006/jtbi.1996.0026, archivado desde el original (PDF) el 26 de mayo de 2006
  81. ^ Jones, Judy; Wilson, William (2006), "Ciencia", Una educación incompleta , Ballantine Books, pág. 544, ISBN 978-0-7394-7582-9
  82. ^ Brousseau, A (1969), "Estadísticas de Fibonacci en coníferas", Fibonacci Quarterly (7): 525–32
  83. ^ "Calificaciones para El código Da Vinci: B-", Matemáticas , Informática para divertirse: CS4FN
  84. ^ Scott, TC; Marketos, P. (marzo de 2014), Sobre el origen de la secuencia de Fibonacci (PDF) , Archivo de Historia de las Matemáticas de MacTutor , Universidad de St Andrews
  85. ^ Livio 2003, pág. 110.
  86. ^ Livio 2003, págs. 112-13.
  87. ^ Varenne, Franck (2010), Formaliser le vivant - Lois, Théories, Modèles (en francés), Hermann, p. 28, ISBN 9782705678128, consultado el 30 de octubre de 2022 , en 1830, KF Schimper et A. Braun [...]. Ils montraient que si l'on représente cet ángulo de divergencia par una fracción reflétant le nombre de tours par feuille ([...]), on tombe régulièrement sur un des nombres de la suite de Fibonacci pour le numerador [...] .
  88. ^ Prusinkiewicz, Przemyslaw; Hanan, James (1989), Sistemas Lindenmayer, fractales y plantas (Apuntes de clases de biomatemáticas) , Springer-Verlag , ISBN 978-0-387-97092-9
  89. ^ Vogel, Helmut (1979), "Una mejor manera de construir la cabeza del girasol", Mathematical Biosciences , 44 (3–4): 179–89, doi :10.1016/0025-5564(79)90080-4
  90. ^ Livio 2003, pág. 112.
  91. ^ Prusinkiewicz, Przemyslaw ; Lindenmayer, Aristid (1990), "4", La belleza algorítmica de las plantas, Springer-Verlag, págs. 101-107, ISBN 978-0-387-97297-8
  92. ^ Basin, SL (1963), "La secuencia de Fibonacci tal como aparece en la naturaleza" (PDF) , The Fibonacci Quarterly , 1 (1): 53–56, doi :10.1080/00150517.1963.12431602
  93. ^ Yanega, D. 1996. Proporción sexual y asignación de sexos en abejas sudoríparas (Hymenoptera: Halictidae). J. Kans. Ent. Soc. 69 Suppl.: 98-115.
  94. ^ ab Hutchison, Luke (septiembre de 2004), "Growing the Family Tree: The Power of DNA in Reconstructing Family Relationships" (PDF) , Actas del Primer Simposio sobre Bioinformática y Biotecnología (BIOT-04) , archivado desde el original (PDF) el 2020-09-25 , consultado el 2016-09-03
  95. ^ Livio 2003, págs. 98–99.
  96. ^ "Representación de Zeckendorf", Enciclopedia de Matemáticas
  97. ^ Patranabis, D.; Dana, SK (diciembre de 1985), "Diagnóstico de fallas de una sola derivación a través de la medición de atenuación terminal y utilizando números de Fibonacci", IEEE Transactions on Instrumentation and Measurement , IM-34 (4): 650–653, Bibcode :1985ITIM...34..650P, doi :10.1109/tim.1985.4315428, S2CID  35413237
  98. ^ Brasch, T. von; Byström, J.; Lystad, LP (2012), "Control óptimo y la secuencia de Fibonacci", Journal of Optimization Theory and Applications , 154 (3): 857–78, doi :10.1007/s10957-012-0061-2, hdl : 11250/180781 , S2CID  : 8550726
  99. ^ Livio 2003, pág. 176.
  100. ^ Livio 2003, pág. 193.

Obras citadas

Enlaces externos