Número Fibonacci - Fibonacci number
Em matemática, os números de Fibonacci , comumente denotados por F n , formam uma sequência , chamada de sequência de Fibonacci , de modo que cada número é a soma dos dois precedentes, começando em 0 e 1. Ou seja,
A sequência começa:
- 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Em algumas definições mais antigas, o valor é omitido, de modo que a sequência começa com e a recorrência é válida para n > 2 . Em sua definição original, Fibonacci iniciou a sequência com
Números de Fibonacci estão fortemente relacionadas com a razão de ouro : fórmula de Binet expressa o n th número de Fibonacci em termos de n e a proporção de ouro, e implica que a proporção de dois números de Fibonacci consecutivas tende à proporção de ouro como n aumenta.
Os números de Fibonacci são nomeados em homenagem ao matemático italiano Leonardo de Pisa, mais tarde conhecido como Fibonacci . Em seu livro Liber Abaci de 1202 , Fibonacci introduziu a sequência na matemática da Europa Ocidental, embora a sequência tenha sido descrita anteriormente na matemática indiana , já em 200 aC no trabalho de Pingala sobre enumerar possíveis padrões de poesia sânscrita formados a partir de sílabas de dois comprimentos.
Os números de Fibonacci aparecem com frequência inesperada na matemática, tanto que existe um jornal inteiro dedicado a seu estudo, o Fibonacci Quarterly . As aplicações dos números de Fibonacci incluem algoritmos de computador, como a técnica de pesquisa de Fibonacci e a estrutura de dados de heap de Fibonacci , e gráficos chamados cubos de Fibonacci usados para interconectar sistemas paralelos e distribuídos.
Eles também aparecem em configurações biológicas , como ramificações nas árvores, o arranjo das folhas em um caule , os brotos de fruto de um abacaxi , a floração de uma alcachofra , uma samambaia que cresça e o arranjo de brácteas de uma pinha .
Os números de Fibonacci também estão intimamente relacionados aos números de Lucas , em que os números de Fibonacci e Lucas formam um par complementar de sequências de Lucas : e .
História
A sequência de Fibonacci aparece na matemática indiana em conexão com a prosódia sânscrita , conforme apontado por Parmanand Singh em 1986. Na tradição poética sânscrita, havia interesse em enumerar todos os padrões de sílabas longas (L) de 2 unidades de duração, justapostas com ( S) sílabas de 1 unidade de duração. A contagem dos diferentes padrões de L e S sucessivos com uma determinada duração total resulta nos números de Fibonacci: o número de padrões de duração m unidades é F m + 1 .
O conhecimento da sequência de Fibonacci foi expresso já em Pingala ( c. 450 aC-200 aC). Singh cita a fórmula enigmática de Pingala misrau cha ("os dois são misturados") e estudiosos que a interpretam no contexto como dizendo que o número de padrões para batimentos m ( F m +1 ) é obtido adicionando um [S] ao F m casos e um [L] para os casos F m −1 . Bharata Muni também expressa conhecimento da sequência no Natya Shastra (c. 100 aC - c. 350 dC). No entanto, a exposição mais clara da sequência surge na obra de Virahanka (c. 700 DC), cuja própria obra está perdida, mas está disponível em uma citação de Gopala (c. 1135):
Variações de dois metros anteriores [é a variação] ... Por exemplo, para [um metro de comprimento] quatro, variações de metros de dois [e] três sendo misturadas, ocorrem cinco. [trabalha os exemplos 8, 13, 21] ... Desse modo, o processo deve ser seguido em todos os mātrā-vṛttas [combinações prosódicas].
Hemachandra (c. 1150) também é creditado com o conhecimento da sequência, escrevendo que "a soma do último e do anterior é o número ... do próximo mātrā-vṛtta."
Fora da Índia, a sequência de Fibonacci aparece pela primeira vez no livro Liber Abaci ( The Book of Calculation , 1202) de Fibonacci, onde é usada para calcular o crescimento das populações de coelhos. Fibonacci considera o crescimento de uma população de coelhos idealizada (biologicamente irrealista) , supondo que: um casal reprodutor recém-nascido de coelhos é colocado no campo; cada casal reprodutor acasala com a idade de um mês e, ao final do segundo mês, sempre produz outro par de coelhos; e os coelhos nunca morrem, mas continuam a procriar para sempre. Fibonacci propôs o quebra-cabeça: quantos pares haverá em um ano?
- No final do primeiro mês, eles acasalam, mas ainda há apenas 1 par.
- No final do segundo mês, eles produzem um novo par, portanto, há 2 pares no campo.
- No final do terceiro mês, o par original produz um segundo par, mas o segundo par apenas acasala sem procriar, portanto, são 3 pares ao todo.
- No final do quarto mês, o par original produziu mais um novo par, e o par nascido há dois meses também produz o primeiro par, perfazendo 5 pares.
No final do n ° mês, o número de pares de coelhos é igual ao número de pares maduros (ou seja, o número de pares no mês n - 2 ) mais o número de pares vivo no mês passado (mês n - 1 ) O número no n ° mês é o n º número de Fibonacci.
O nome "sequência de Fibonacci" foi usado pela primeira vez pelo teórico dos números do século 19, Édouard Lucas .
Propriedades de sequência
Os primeiros 21 números de Fibonacci F n são:
F 0 F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8 F 9 F 10 F 11 F 12 F 13 F 14 F 15 F 16 F 17 F 18 F 19 F 20 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
A sequência também pode ser estendida para o índice negativo n usando a relação de recorrência reorganizada
que produz a sequência de números "negafibonacci" que satisfazem
Assim, a sequência bidirecional é
F -8 F -7 F -6 F −5 F −4 F -3 F -2 F -1 F 0 F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8 21 13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13 21
Relação com a proporção áurea
Expressão de forma fechada
Como toda sequência definida por uma recorrência linear com coeficientes constantes , os números de Fibonacci têm uma expressão de forma fechada . Ficou conhecida como fórmula de Binet , em homenagem ao matemático francês Jacques Philippe Marie Binet , embora já fosse conhecida por Abraham de Moivre e Daniel Bernoulli :
Uma vez que , esta fórmula também pode ser escrita como
Segue-se que, para quaisquer valores a e b , a sequência definida por
Se um e b serem escolhidos de modo a que L 0 = 0 e L 1 = 1 , em seguida, a sequência resultante L n deve ser a sequência de Fibonacci. Esta é a mesma como requerendo um e b satisfazer o sistema de equações:
Tomando os valores iniciais U 0 e U 1 como constantes arbitrárias, uma solução mais geral é:
Cálculo por arredondamento
Desde a
para todo n ≥ 0 , o número F n é o inteiro mais próximo de . Portanto, ele pode ser encontrado por arredondamento , usando a função de número inteiro mais próximo:
Na verdade, o erro de arredondamento é muito pequeno, sendo menor que 0,1 para n ≥ 4 e menor que 0,01 para n ≥ 8 .
Os números de Fibonacci também podem ser calculados por truncamento , em termos da função de chão :
Como a função de base é monotônica , a última fórmula pode ser invertida para encontrar o índice n ( F ) do maior número de Fibonacci que não seja maior que um número real F > 1 :
Limite de quocientes consecutivos
Johannes Kepler observou que a proporção de números de Fibonacci consecutivos converge. Ele escreveu que "como 5 está para 8, então é 8 para 13, praticamente, e como 8 está para 13, então é 13 para 21 quase", e concluiu que essas razões se aproximam da razão áurea
Esta convergência se mantém independentemente dos valores iniciais, excluindo 0 e 0, ou qualquer par na proporção áurea conjugada. Isso pode ser verificado usando a fórmula de Binet . Por exemplo, os valores iniciais 3 e 2 geram a sequência 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, ... A proporção de termos consecutivos nesta sequência mostra a mesma convergência para a razão áurea.
Decomposição de poderes
Uma vez que a proporção áurea satisfaz a equação
esta expressão pode ser usada para decompor potências superiores como uma função linear de potências inferiores, que por sua vez podem ser decompostas em uma combinação linear de e 1. As relações de recorrência resultantes produzem números de Fibonacci como os coeficientes lineares:
Esta expressão também é verdadeira para n <1 se a sequência de Fibonacci F n for estendida para inteiros negativos usando a regra de Fibonacci
Forma de matriz
Um sistema bidimensional de equações de diferença linear que descreve a sequência de Fibonacci é
que produz . Os autovalores da matriz A são e correspondentes aos respectivos autovetores
De forma equivalente, o mesmo cálculo pode ser realizado por diagonalização de A por meio do uso de sua composição automática :
que novamente produz
A matriz A tem um determinante de -1 e, portanto, é uma matriz unimodular 2 × 2 .
Esta propriedade pode ser entendida em termos da representação da fração contínua para a proporção áurea:
Os números de Fibonacci ocorrem como a razão de convergentes sucessivos da fração contínua para φ , e a matriz formada a partir de convergentes sucessivos de qualquer fração contínua tem um determinante de +1 ou -1. A representação da matriz fornece a seguinte expressão de forma fechada para os números de Fibonacci:
Tomando o determinante de ambos os lados desta equação produz a identidade da Cassini ,
Além disso, uma vez que
A n A m = A n + m para qualquer matriz quadrada A , as seguintes identidades podem ser derivadas (elas são obtidas a partir de dois coeficientes diferentes do produto da matriz, e pode-se facilmente deduzir o segundo do primeiro por transformando n em n + 1 ),Em particular, com m = n ,
Essas duas últimas identidades fornecem uma maneira de calcular números de Fibonacci recursivamente em O (log ( n )) operações aritméticas e no tempo O ( M ( n ) log ( n )) , onde M ( n ) é o tempo para a multiplicação de dois números de n dígitos. Isso corresponde ao tempo para calcular o n- ésimo número de Fibonacci da fórmula da matriz de forma fechada, mas com menos etapas redundantes se evitarmos recomputar um número de Fibonacci já calculado (recursão com memoização ).
Identificação
Pode surgir a questão de saber se um inteiro positivo x é um número de Fibonacci. Isso é verdade se e somente se pelo menos um de ou for um
quadrado perfeito . Isso ocorre porque a fórmula de Binet acima pode ser reorganizada para darque permite encontrar a posição na sequência de um determinado número de Fibonacci.
Esta fórmula deve retornar um inteiro para todos os n , então a expressão radical deve ser um inteiro (caso contrário, o logaritmo nem mesmo retorna um número racional).
Identidades combinatórias
Provas Combinatórias
A maioria das identidades envolvendo números de Fibonacci pode ser provada usando argumentos combinatórios usando o fato de que pode ser interpretado como o número de sequências [possivelmente vazias] de 1s e 2s cuja soma é . Isso pode ser tomado como a definição de com as convenções , significando que não existe tal sequência cuja soma seja -1 e , significando que a sequência vazia "soma" a 0. No seguinte, é a
cardinalidade de um conjunto:Desta forma, a relação de recorrência
De um modo semelhante, pode ser mostrado que a soma dos primeiros números de Fibonacci até o n ° é igual a ( n + 2) -nd Fibonacci número menos 1. Em símbolos:
Isso pode ser visto dividindo todas as sequências somadas com base na localização do primeiro 2. Especificamente, cada conjunto consiste nas sequências que começam até os últimos dois conjuntos, cada um com cardinalidade 1.
Seguindo a mesma lógica de antes, ao somar a cardinalidade de cada conjunto vemos que
... onde os dois últimos termos têm o valor . Disto segue isso .
Um argumento semelhante, agrupar as somas pela posição do primeiro 1 em vez dos primeiros 2 dá mais duas identidades:
Um truque diferente pode ser usado para provar
Método simbólico
A sequência também é considerada usando o
método simbólico . Mais precisamente, esta sequência corresponde a uma classe combinatória especificável . A especificação desta sequência é . De fato, como afirmado acima, o -ésimo número de Fibonacci é igual ao número de composições combinatórias ( partições ordenadas ) usando os termos 1 e 2.Segue-se que a função geradora comum da sequência de Fibonacci, ou seja , é a função complexa .
Provas de indução
As identidades de Fibonacci muitas vezes podem ser facilmente comprovadas por indução matemática .
Por exemplo, reconsidere
e então temos a fórmula para
Da mesma forma, adicione a ambos os lados de
Provas de fórmulas Binet
A fórmula de Binet é
Por exemplo, para provar que nota que o lado esquerdo multiplicado por torna-se
Outras identidades
Numerosas outras identidades podem ser derivadas usando vários métodos. Aqui estão alguns deles:
Identidades da Cassini e do Catalão
A identidade da Cassini afirma que
a identidade de d'Ocagne
De forma geral,
ou alternativamente
Colocando k = 2 nesta fórmula, obtém-se novamente as fórmulas do final da seção anterior Formulário de matriz .
Função geradora
A função geradora da sequência de Fibonacci é a série de potências
Esta série é convergente para e sua soma possui forma fechada simples:
Isso pode ser provado usando a recorrência de Fibonacci para expandir cada coeficiente na soma infinita:
Resolvendo a equação
fornece a função geradora para os números de negafibonacci e satisfaz a
equação funcionalA decomposição da fração parcial é dada por
Somas recíprocas
As somas infinitas sobre os números de Fibonacci recíprocos às vezes podem ser avaliados em termos de funções teta . Por exemplo, podemos escrever a soma de cada número de Fibonacci recíproco indexado ímpar como
e a soma dos números quadrados de Fibonacci recíprocos como
Se adicionarmos 1 a cada número de Fibonacci na primeira soma, também terá a forma fechada
e há uma soma aninhada de números de Fibonacci ao quadrado dando o recíproco da proporção áurea ,
A soma de todos os números de Fibonacci recíprocos pares indexados é
Portanto, a constante recíproca de Fibonacci é
Além disso, esse número foi provado irracional por Richard André-Jeannin .
A série Millin dá a identidade
Primos e divisibilidade
Propriedades de divisibilidade
Cada terceiro número da sequência é par e, mais geralmente, todo k- ésimo número da sequência é um múltiplo de F k . Assim, a sequência de Fibonacci é um exemplo de sequência de divisibilidade . Na verdade, a sequência de Fibonacci satisfaz a propriedade de divisibilidade mais forte
Quaisquer três números de Fibonacci consecutivos são coprimes de pares , o que significa que, para cada n ,
- GCD ( M n , M n 1 ) = GCD ( M n , M n 2 ) = GCD ( F n 1 , F N 2 ) = 1.
Cada número primo p divide um número de Fibonacci que pode ser determinado pelo valor de p módulo 5. Se p é congruente a 1 ou 4 (mod 5), então p divide F p - 1 , e se p é congruente a 2 ou 3 (mod 5), então, p divide F p + 1 . O caso restante é que p = 5 e, neste caso, p divide F p .
Esses casos podem ser combinados em uma única fórmula sem partes , usando o símbolo de Legendre :
Teste de Primalidade
A fórmula acima pode ser usada como um teste de primalidade no sentido de que se
Primos de Fibonacci
Um número primo de Fibonacci é um número de Fibonacci primo . Os primeiros são:
Os primos de Fibonacci com milhares de dígitos foram encontrados, mas não se sabe se há infinitos.
F kn é divisível por F n , portanto, além de F 4 = 3, qualquer número primo de Fibonacci deve ter um índice primo. Como existem séries arbitrariamente longas de números compostos , há, portanto, também séries arbitrariamente longas de números de Fibonacci compostos.
Nenhum número de Fibonacci maior que F 6 = 8 é um maior ou menor que um número primo.
O único número de Fibonacci quadrado não trivial é 144. Attila Pethő provou em 2001 que existe apenas um número finito de números de Fibonacci de potência perfeita. Em 2006, Y. Bugeaud, M. Mignotte e S. Siksek provaram que 8 e 144 são os únicos poderes perfeitos não triviais.
1, 3, 21, 55 são os únicos números triangulares de Fibonacci, o que foi conjecturado por Vern Hoggatt e provado por Luo Ming.
Nenhum número de Fibonacci pode ser um número perfeito . De modo mais geral, nenhum número de Fibonacci diferente de 1 pode ser multiplamente perfeito e nenhuma proporção de dois números de Fibonacci pode ser perfeita.
Divisores principais
Com as exceções de 1, 8 e 144 ( F 1 = F 2 , F 6 e F 12 ) todo número de Fibonacci tem um fator primo que não é um fator de nenhum número de Fibonacci menor ( teorema de Carmichael ). Como resultado, 8 e 144 ( F 6 e F 12 ) são os únicos números de Fibonacci que são produto de outros números de Fibonacci OEIS : A235383 .
A divisibilidade dos números de Fibonacci por um p primo está relacionada ao símbolo de Legendre, que é avaliado da seguinte forma:
Se p é um número primo, então
Por exemplo,
Não se sabe se existe um primo p tal que
Esses primos (se houver) seriam chamados de primos Parede-Sol-Sol .
Além disso, se p ≠ 5 for um número primo ímpar, então:
Exemplo 1. p = 7, neste caso p ≡ 3 (mod 4) e temos:
Exemplo 2. p = 11, neste caso p ≡ 3 (mod 4) e temos:
Exemplo 3. p = 13, neste caso p ≡ 1 (mod 4) e temos:
Exemplo 4. p = 29, neste caso p ≡ 1 (mod 4) e temos:
Para n ímpar , todos os divisores primos ímpares de F n são congruentes a 1 módulo 4, o que implica que todos os divisores ímpares de F n (como os produtos dos divisores primos ímpares) são congruentes a 1 módulo 4.
Por exemplo,
Todos os fatores conhecidos dos números de Fibonacci F ( i ) para todos os i <50000 são coletados nos repositórios relevantes.
Módulo de periodicidade n
Se os membros da sequência de Fibonacci são considerados mod n , a sequência resultante é periódica com período de no máximo 6n . Os comprimentos dos períodos para vários n formam os chamados períodos Pisano OEIS : A001175 . Determinar uma fórmula geral para os períodos Pisano é um problema aberto, que inclui como subproblema uma instância especial do problema de encontrar a ordem multiplicativa de um inteiro modular ou de um elemento em um corpo finito . No entanto, para qualquer n particular , o período Pisano pode ser encontrado como um exemplo de detecção de ciclo .
Magnitude
Uma vez que F n é assintótico a , o número de dígitos em F n é assintótico a . Como consequência, para cada inteiro d > 1, existem 4 ou 5 números de Fibonacci com d dígitos decimais.
Mais geralmente, na representação de base b , o número de dígitos em F n é assintótico a
Generalizações
A sequência de Fibonacci é uma das sequências mais simples e mais antigas conhecidas, definida por uma relação de recorrência e, especificamente, por uma equação de diferença linear . Todas essas sequências podem ser vistas como generalizações da sequência de Fibonacci. Em particular, a fórmula de Binet pode ser generalizada para qualquer sequência que seja uma solução de uma equação de diferença linear homogênea com coeficientes constantes.
Alguns exemplos específicos que estão próximos, em certo sentido, da sequência de Fibonacci incluem:
- Generalizando o índice para inteiros negativos para produzir os números negafibonacci .
- Generalizar o índice para números reais usando uma modificação da fórmula de Binet.
- Começando com outros inteiros. Os números de Lucas têm L 1 = 1, L 2 = 3 e L n = L n −1 + L n −2 . As sequências Primefree usam a recursão de Fibonacci com outros pontos de partida para gerar sequências nas quais todos os números são compostos .
- Supondo que um número seja uma função linear (diferente da soma) dos 2 números anteriores. Os números Pell têm P n = 2 P n - 1 + P n - 2 . Se o coeficiente do valor anterior for atribuído a um valor variável x , o resultado é a sequência de polinômios de Fibonacci .
- Não adicionar os números imediatamente anteriores. A sequência de Padovan e os números de Perrin têm P ( n ) = P ( n - 2) + P ( n - 3).
- Gerar o próximo número adicionando 3 números (números tribonacci), 4 números (números tetranacci) ou mais. As sequências resultantes são conhecidas como números de Fibonacci n-Step .
Formulários
Matemática
Os números de Fibonacci ocorrem na soma das diagonais "rasas" no triângulo de Pascal (ver coeficiente binomial ):
A função de geração pode ser expandida para
Para ver como a fórmula é usada, podemos organizar as somas pelo número de termos presentes:
5 = 1 + 1 + 1 + 1 + 1 = 2 + 1 + 1 + 1 = 1 + 2 + 1 + 1 = 1 + 1 + 2 + 1 = 1 + 1 + 1 + 2 = 2 + 2 + 1 = 2 + 1 + 2 = 1 + 2 + 2
isto é , onde estamos escolhendo as posições de k dois a partir de nk-1 termos.
Esses números também fornecem a solução para certos problemas enumerativos, o mais comum dos quais é o de contar o número de maneiras de escrever um dado número n como uma soma ordenada de 1s e 2s (chamadas composições ); existem maneiras F n +1 de fazer isso (equivalentemente, é também o número de peças de dominó do retângulo). Por exemplo, existem F 5 + 1 = F 6 = 8 maneiras de subir uma escada de 5 degraus, dando um ou dois degraus de cada vez:
5 = 1 + 1 + 1 + 1 + 1 = 2 + 1 + 1 + 1 = 1 + 2 + 1 + 1 = 1 + 1 + 2 + 1 = 2 + 2 + 1 = 1 + 1 + 1 + 2 = 2 + 1 + 2 = 1 + 2 + 2
A figura mostra que 8 pode ser decomposto em 5 (o número de maneiras de subir 4 degraus, seguido de uma única etapa) mais 3 (o número de maneiras de subir 3 degraus, seguido de uma etapa dupla). O mesmo raciocínio é aplicado recursivamente até uma única etapa, da qual só há uma forma de subir.
Os números de Fibonacci podem ser encontrados de diferentes maneiras entre o conjunto de strings binárias ou, de forma equivalente, entre os subconjuntos de um determinado conjunto.
- O número de cadeias binárias de comprimento n sem 1 s consecutivo é o número de Fibonacci F n +2 . Por exemplo, das 16 sequências binárias de comprimento 4, há F 6 = 8 sem 1 s consecutivo - são 0000, 0001, 0010, 0100, 0101, 1000, 1001 e 1010. Equivalentemente, F n +2 é o número de subconjuntos Sde {1, ..., n } sem inteiros consecutivos, ou seja, aqueles S para os quais { i , i + 1} ⊈ S para cada i . Uma bijeção com as somas n + 1 é substituir 1 por 0 e 2 por 10 , e eliminar o último zero.
- O número de cadeias binárias de comprimento n sem um número ímpar de 1 s consecutivos é o número de Fibonacci F n + 1 . Por exemplo, das 16 cadeias binárias de comprimento 4, há F 5 = 5 sem um número ímpar de 1 s consecutivos - são 0000, 0011, 0110, 1100, 1111. Equivalentemente, o número de subconjuntos S de {1 , ..., n } sem um número ímpar de inteiros consecutivos é F n +1 . Uma bijeção com as somas para n deve substituir 1 por 0 e 2 por 11 .
- O número de cadeias binárias de comprimento n sem um número par de 0 s ou 1 s consecutivos é 2 F n . Por exemplo, das 16 sequências binárias de comprimento 4, há 2 F 4 = 6 sem um número par de 0 s ou 1 s consecutivos - são 0001, 0111, 0101, 1000, 1010, 1110. Há um equivalente declaração sobre subconjuntos.
- Yuri Matiyasevich foi capaz de mostrar que os números de Fibonacci podem ser definidos por uma equação Diofantina , que o levou a resolver o décimo problema de Hilbert .
- Os números de Fibonacci também são um exemplo de uma seqüência completa . Isso significa que todo número inteiro positivo pode ser escrito como uma soma de números de Fibonacci, onde qualquer número é usado uma vez no máximo.
- Além disso, todo número inteiro positivo pode ser escrito de uma maneira única como a soma de um ou mais números de Fibonacci distintos, de forma que a soma não inclua dois números de Fibonacci consecutivos. Isso é conhecido como teorema de Zeckendorf , e uma soma dos números de Fibonacci que satisfaz essas condições é chamada de representação de Zeckendorf. A representação Zeckendorf de um número pode ser usada para derivar sua codificação Fibonacci .
- A partir de 5, cada segundo número de Fibonacci é o comprimento da hipotenusa de um triângulo retângulo com lados inteiros, ou seja, o maior número em um triplo pitagórico , obtido a partir da fórmula
- O cubo Fibonacci é um grafo não direcionado com um número Fibonacci de nós que foi proposto como uma topologia de rede para computação paralela .
- Os números de Fibonacci aparecem no lema do anel , usado para provar as conexões entre o teorema de empacotamento do círculo e os mapas conformes .
Ciência da Computação
- Os números de Fibonacci são importantes na análise de tempo de execução computacional do algoritmo de Euclides para determinar o maior divisor comum de dois inteiros: a entrada de pior caso para este algoritmo é um par de números de Fibonacci consecutivos.
- Os números de Fibonacci são usados em uma versão polifásica do algoritmo de classificação por mesclagem em que uma lista não classificada é dividida em duas listas cujos comprimentos correspondem a números de Fibonacci sequenciais - dividindo a lista de forma que as duas partes tenham comprimentos na proporção aproximada φ . Uma implementação de unidade de fita do tipo de mesclagem polifásica foi descrita em The Art of Computer Programming .
- Uma árvore Fibonacci é uma árvore binária cujas árvores filhas (recursivamente) diferem em altura por exatamente 1. Portanto, é uma árvore AVL , e uma com o menor número de nós para uma determinada altura - a árvore AVL "mais fina". Essas árvores possuem um número de vértices que é um número de Fibonacci menos um, um fato importante na análise de árvores AVL.
- Os números de Fibonacci são usados por alguns geradores de números pseudo-aleatórios .
- Os números de Fibonacci surgem na análise da estrutura de dados do heap de Fibonacci .
- Um método de otimização unidimensional, chamado de técnica de pesquisa de Fibonacci , usa números de Fibonacci.
- A série de números de Fibonacci é usada para compactação opcional com perdas no formato de arquivo de áudio IFF 8SVX usado em computadores Amiga . A série numérica compara a onda de áudio original de maneira semelhante aos métodos logarítmicos, como a lei μ .
- Eles também são usados no planejamento de pôquer , que é uma etapa da estimativa em projetos de desenvolvimento de software que usam a metodologia Scrum .
Natureza
As sequências de Fibonacci aparecem em configurações biológicas, como ramificação em árvores, arranjo de folhas em um caule , os frutos de um abacaxi , o florescimento de alcachofra , uma samambaia que se desenvolve e o arranjo de uma pinha e a árvore genealógica das abelhas. Kepler apontou a presença da sequência de Fibonacci na natureza, usando-a para explicar a forma pentagonal ( relacionada à razão áurea ) de algumas flores. As margaridas do campo geralmente têm pétalas na contagem do número de Fibonacci. Em 1754, Charles Bonnet descobriu que a filotaxia espiral das plantas era freqüentemente expressa em séries de números de Fibonacci.
Przemysław Prusinkiewicz propôs a ideia de que instâncias reais podem em parte ser entendidas como a expressão de certas restrições algébricas em grupos livres , especificamente como certas gramáticas de Lindenmayer .
Um modelo para o padrão de florzinhas na cabeça de um girassol foi proposto por Helmut Vogel em 1979. Tem a forma
onde n é o número índice da florzinha ec é um fator de escala constante; as florzinhas ficam, portanto, na espiral de Fermat . O ângulo de divergência, aproximadamente 137,51 °, é o ângulo dourado , dividindo o círculo na proporção áurea. Como essa proporção é irracional, nenhuma florzinha tem um vizinho exatamente no mesmo ângulo do centro, portanto, as florzinhas se compactam com eficiência. Como as aproximações racionais da razão áurea são da forma F ( j ): F ( j + 1) , os vizinhos mais próximos do número florete n são aqueles em n ± F ( j ) para algum índice j , que depende de r , a distância do centro. Os girassóis e flores semelhantes mais comumente têm espirais de florzinhas nas direções horária e anti-horária na quantidade de números de Fibonacci adjacentes, normalmente contados pela faixa mais externa de raios.
Os números de Fibonacci também aparecem nos pedigrees das abelhas idealizadas, de acordo com as seguintes regras:
- Se um ovo é posto por uma fêmea não acasalada, ele choca um macho ou uma abelha zangão .
- Se, no entanto, um ovo foi fertilizado por um macho, chocou uma fêmea.
Assim, uma abelha macho sempre tem um progenitor e uma abelha fêmea dois. Se rastrearmos o pedigree de qualquer abelha macho (1 abelha), ela terá 1 pai (1 abelha), 2 avós, 3 bisavós, 5 tataravós e assim por diante. Essa sequência de números de pais é a sequência de Fibonacci. O número de ancestrais em cada nível, F n , é o número de ancestrais femininos, que é F n −1 , mais o número de ancestrais masculinos, que é F n −2 . Isso se baseia na suposição irreal de que os ancestrais em cada nível não são relacionados de outra forma.
Foi notado que o número de possíveis ancestrais na linha de herança do cromossomo X humano em uma determinada geração ancestral também segue a sequência de Fibonacci. Um indivíduo do sexo masculino tem um cromossomo X, que recebeu de sua mãe, e um cromossomo Y , que recebeu de seu pai. O homem conta como a "origem" de seu próprio cromossomo X ( ), e na geração de seus pais, seu cromossomo X veio de um único progenitor ( ). A mãe do homem recebeu um cromossomo X de sua mãe (a avó materna do filho) e um de seu pai (o avô materno do filho), então dois avós contribuíram para o cromossomo X do descendente masculino ( ). O avô materno recebeu seu cromossomo X de sua mãe, e a avó materna recebeu cromossomos X de ambos os pais, então três bisavós contribuíram para o cromossomo X do descendente masculino ( ). Cinco tataravós contribuíram para o cromossomo X do descendente masculino ( ), etc. (Isso pressupõe que todos os ancestrais de um determinado descendente sejam independentes, mas se qualquer genealogia for rastreada suficientemente no tempo, os ancestrais começarão a aparecer em várias linhas da genealogia, até que eventualmente um fundador da população apareça em todas as linhas da genealogia.)
As vias das tubulinas nos microtúbulos intracelulares se organizam em padrões de 3, 5, 8 e 13.
De outros
- Em óptica , quando um feixe de luz brilha em um ângulo através de duas placas transparentes empilhadas de diferentes materiais de diferentes índices de refração , ele pode refletir em três superfícies: as superfícies superior, intermediária e inferior das duas placas. O número de caminhos de feixe diferentes que têm k reflexões, para k > 1 , é o ésimo número de Fibonacci. (No entanto, quando k = 1 , existem três caminhos de reflexão, não dois, um para cada uma das três superfícies.)
- Os níveis de retração de Fibonacci são amplamente utilizados em análises técnicas para negociação no mercado financeiro.
- Como o fator de conversão 1,609344 para milhas em quilômetros está próximo da razão áurea, a decomposição da distância em milhas em uma soma de números de Fibonacci torna-se quase a soma de quilômetros quando os números de Fibonacci são substituídos por seus sucessores. Este método equivale a um registro de número raiz 2 na base de razão áurea φ sendo deslocado. Para converter de quilômetros em milhas, desloque o registro para baixo na sequência de Fibonacci.
- Brasch e col. 2012 mostram como uma sequência generalizada de Fibonacci também pode ser conectada ao campo da economia. Em particular, é mostrado como uma sequência generalizada de Fibonacci entra na função de controle de problemas de otimização dinâmica de horizonte finito com um estado e uma variável de controle. O procedimento é ilustrado em um exemplo frequentemente conhecido como modelo de crescimento econômico Brock-Mirman.
- Mario Merz incluiu a sequência de Fibonacci em algumas de suas obras a partir de 1970.
- Joseph Schillinger (1895–1943) desenvolveu um sistema de composição que usa intervalos de Fibonacci em algumas de suas melodias; ele os via como a contrapartida musical da elaborada harmonia evidente na natureza. Veja também Proporção áurea § Música .
Veja também
Referências
Notas de rodapé
Citações
Trabalhos citados
- Ball, Keith M (2003), "8: Fibonacci's Rabbits Revisited", Strange Curves, Counting Rabbits, and Other Mathematical Explorations , Princeton, NJ: Princeton University Press , ISBN 978-0-691-11321-0.
- Beck, Matthias; Geoghegan, Ross (2010), The Art of Proof: Basic Training for Deeper Mathematics , Nova York: Springer, ISBN 978-1-4419-7022-0.
- Bóna, Miklós (2011), A Walk Through Combinatorics (3ª ed.), New Jersey: World Scientific, ISBN 978-981-4335-23-2.
- Bóna, Miklós (2016), A Walk Through Combinatorics (4ª edição revisada), New Jersey: World Scientific, ISBN 978-981-3148-84-0.
- Borwein, Jonathan M .; Borwein, Peter B. (julho de 1998), Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity , Wiley, pp. 91-101, ISBN 978-0-471-31515-5
- Lemmermeyer, Franz (2000), Reciprocity Laws: From Euler to Eisenstein , Springer Monographs in Mathematics, Nova York: Springer, ISBN 978-3-540-66957-9.
- Livio, Mario (2003) [2002]. A Proporção Áurea: A História de Phi, o Número Mais Surpreendente do Mundo (Primeira edição de brochura comercial). Nova York: Broadway Books . ISBN 0-7679-0816-3.
- Lucas, Édouard (1891), Théorie des nombres (em francês), 1 , Paris: Gauthier-Villars, https://books.google.com/books?id=_hsPAAAAIAAJ.
- Pisano, Leonardo (2002), Liber Abaci de Fibonacci: A Translation to Modern English of the Book of Calculation , Sources and Studies in the History of Mathematics and Physical Sciences, Sigler, Laurence E, trans, Springer, ISBN 978-0-387-95419-6
links externos
- Módulo de Períodos de Sequências de Fibonacci em MathPages
- Os cientistas encontram pistas para a formação de espirais de Fibonacci na natureza
- Sequência de Fibonacci em In Our Time na BBC
- "Números de Fibonacci" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
- Sequência OEIS A000045 (números de Fibonacci)