Conteúdo verificado

Número de Fibonacci

Assuntos Relacionados: Matemática

Você sabia ...

Esta seleção Wikipedia está offline disponível a partir de Crianças SOS, para distribuição no mundo em desenvolvimento. Antes de decidir sobre o patrocínio de uma criança, por que não aprender sobre as diferentes instituições de caridade de patrocínio primeiro ?

Um azulejos com quadrados cujos comprimentos de lado são números de Fibonacci sucessivos
Uma aproximação do espiral dourada desenho criado por arcos circulares que ligam os cantos opostos de praças da telha Fibonacci; este usa praças de tamanhos 1, 1, 2, 3, 5, 8, 13, 21 e 34.

Em matemática , os números de Fibonacci ou Fibonacci série ou seqüência de Fibonacci são os números na seguinte seqüência de inteiro:

0, \; 1, \; 1, \, 2, \, 3, \; 5, \; 8, \; 13, \; 21, \; 34, \; 55, \; 89, \; 144, \; \ Ldots \; (Sequência A000045 em OEIS )

Por definição, os dois primeiros números da sequência de Fibonacci são 0 e 1, e cada número subsequente é a soma das duas anteriores.

Em termos matemáticos, a sequência de Fn de números de Fibonacci é definida pela relação de recorrência

F_n = F_ {n-1} + F_ {n-2}, \! \,

com valores de semente

F_0 = 0, \; F_1 = 1.

A seqüência de Fibonacci é nomeado após Leonardo de Pisa, que era conhecido como Fibonacci. 1202 O livro de Fibonacci Liber Abaci introduziu a seqüência à matemática da Europa Ocidental, embora a seqüência havia sido descrita anteriormente em matemática indiana . Por convenção moderna, a sequência começa com F ou 0 = 0 ou com F 1 = 1. O Liber Abaci começou a sequência com F 1 = 1, sem um inicial 0.

Números de Fibonacci estão intimamente relacionados com Lucas números em que eles são um par complementar de Sequências de Lucas. Eles estão intimamente ligados com a proporção áurea ; por exemplo, a mais próximas aproximações racionais para o rácio são 2/1, 3/2, 5/3, 8/5, .... As aplicações incluem algoritmos de computador, tais como o Fibonacci técnica de busca e Estrutura de dados heap Fibonacci, e gráficos chamado Cubos de Fibonacci utilizados para interligar sistemas paralelos e distribuídos. Eles também aparecem nas definições biológicos, tais como a ramificação nas árvores, phyllotaxis (o arranjo das folhas em uma haste), os brotos de fruto de um abacaxi, o florescimento de alcachofra, um desenrolar fern e o arranjo de um pinha.

Origins

Uma página de Fibonacci de Liber Abaci do Biblioteca Nazionale di Firenze que mostra (na caixa à direita) a seqüência de Fibonacci com a posição na sequência marcada em latim e algarismos romanos eo valor em algarismos hindu-arábicos.

A seqüência de Fibonacci aparece na matemática indiana , em conexão com Prosódia sânscrito. Na tradição oral sânscrito, houve muita ênfase em quanto tempo (L) sílabas misturar com o curta (S), e contando os diferentes padrões de L e S dentro de um determinado resultado de comprimento fixo nos números de Fibonacci; o número de padrões que são m sílabas curtas tempo é o número de Fibonacci F m + 1.

Susantha Goonatilake escreve que o desenvolvimento da sequência de Fibonacci "é atribuído em parte à Pingala (200 aC), mais tarde a ser associado com Virahanka (c. 700 dC), Gopāla (c. 1135), e Hemachandra (c. 1150) ". Parmanand Singh cita enigmática cha fórmula misrau de Pingala (" os dois são misturados ") e cita estudiosos que interpretam-lo no contexto como dizendo que os casos de m batidas (F m + 1) é obtida pela adição um [S] para F m casos e [L] para os casos M-1 F. Ele lançamento Pingala antes de 450 aC.

No entanto, a mais clara exposição da série surge no trabalho de Virahanka (. C 700 dC), cujo próprio trabalho é perdido, mas está disponível em uma cotação por Gopala (c 1135).:

Variações de dois metros [anteriores é a variação] ... Por exemplo, para [um metro de comprimento do] de quatro, as variações de dois metros de [e] três sendo misturados, cinco acontece. [Funciona exemplos 8, 13, 21] ... Desta forma, o processo deve ser seguido em todos os Matra-vṛttas [combinações prosódicos].

A série também é discutida por Gopala (antes de 1135 dC) e pelo erudito Jain Hemachandra (c. 1150).

No Ocidente, a seqüência de Fibonacci aparece pela primeira vez no livro Liber Abaci (1202) por Leonardo de Pisa, conhecido como Fibonacci. Fibonacci considera o crescimento de uma (biologicamente irreal) idealizada coelho população, assumindo que: um par recém-nascido de coelhos, um macho, uma fêmea, são colocados em um campo; coelhos são capazes de acasalar com a idade de um mês de modo a que no final do segundo mês a uma fêmea pode produzir um outro par de coelhos; coelhos nunca morrem e um par de acoplamento sempre produz um novo par (um macho, uma fêmea) a cada mês a partir do segundo mês por diante. O quebra-cabeça que Fibonacci que se colocava era: quantos pares haverá em um ano?

  • No final do primeiro mês, que se acoplam, mas ainda há apenas um par.
  • No final do segundo mês a fêmea produz um novo par, de modo que agora existem dois pares de coelhos no campo.
  • No final do terceiro mês, a fêmea inicial produz um segundo par, fazendo três pares em todos no domínio.
  • No final do quarto mês, a fêmea inicial produziu outra novo par, a fêmea nascido dois meses produz seu primeiro par também, fazendo com que 5 pares.

No final do n ° mês, o número de pares de coelhos é igual ao número de novos pares (que é o número de pares em mês n - 2) mais o número de pares vivo última meses (n - 1). Este é o enésimo número Fibonacci.

O nome "seqüência de Fibonacci" foi usado pela primeira vez pelo número teórico do século 19 Édouard Lucas.

Lista de números de Fibonacci

O primeiro 21 números de Fibonacci F n para n = 0, 1, 2, ..., 20 são os seguintes:

F 0 F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8 F 9 F 10 F 11 M 12 F 13 F 14 M 15 F 16 F 17 M 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 estendido para negativo n, usando o índice relação de recorrência re-arranjado

F_ {n-2} = f_n - F_ {n-1},

que produz a sequência de números "negafibonacci" satisfazendo

F _ {- n} = (-1) ^ {n + 1} f_n.

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

Ocorrências em matemática

Os números de Fibonacci são as somas das diagonais "rasas" (mostrado em vermelho) do triângulo de Pascal .

Os números de Fibonacci ocorrer nas somas de diagonais "rasas" no triângulo de Pascal (veja coeficiente binomial ).

F_ {n} = \ sum_ {k = 0} ^ {\ lfloor \ frac {n-1} {2} \ rfloor} \ tbinom {nk-1} k.

Os números de Fibonacci podem ser encontrados em formas diferentes na sequência de binário strings.

  • O número de cadeias binárias de comprimento n, sem 1s consecutivos é o número Fibonacci F n +2. Por exemplo, das 16 cadeias binárias de comprimento 4, existem M 6 = 8 sem 1s consecutivos - são 0000, 0100, 0010, 0001, 0101, 1000, 1010 e 1001. Por simetria, o número de cadeias de comprimento n consecutivos sem 0s também é F N 2.
  • O número de cadeias binárias de comprimento n, sem um número ímpar de 1s consecutivos é o número Fibonacci F n + 1. Por exemplo, das 16 cadeias binárias de comprimento 4, existem F 5 = 5, sem um número ímpar de 1s consecutivos - são 0000, 0011, 0110, 1100, 1111.
  • O número de cadeias binárias de comprimento n, sem um número par de 0s ou 1s consecutivos é de 2 F n. Por exemplo, das 16 cadeias binárias de comprimento 4, existem 2 F 4 = 6, sem um número par de 0s consecutivos ou 1s - são 0001, 1000, 1110, 0111, 0101, 1010.

Relação com a proporção áurea

De forma fechada expressão

Como cada seqüência definida por um recorrência linear com coeficientes constantes, os números de Fibonacci têm um solução de forma fechada. Tornou-se conhecido como Fórmula de Binet, embora já era conhecido pela Abraham de Moivre:

F_n = \ frac {\ varphi ^ n- \ psi ^ n} {\ varphi- psi \} = \ frac {\ varphi ^ n- \ psi ^ n} {\ sqrt 5}

onde

\ Varphi = \ frac {1 + \ sqrt {5}} {2} \ approx 1,61803 \, 39.887 \ \ cdots,

é a proporção áurea (sequência A001622 em OEIS ), e

\ Psi = \ frac {1 - \ sqrt {5}} {2} = 1 - \ varphi = - {1 \ over \ varphi} \ approx -,61803 \, 39.887 \ cdots

Para ver isto, note que φ e ψ são ambas as soluções das equações

x ^ 2 = x + 1, \, x ^ n = x ^ {n-1} + x ^ {n-2}, \,

assim os poderes de φ e ψ satisfazer a recursão Fibonacci. Em outras palavras

\ Varphi ^ n = \ varphi ^ {n-1} + \ varphi ^ {n-2} \,

e

\ Psi ^ n = \ psi ^ {n-1} + \ psi ^ {n-2} \,.

Daqui resulta que para qualquer valores a e b, da sequência definida pela

U_n = a \ varphi ^ n + b \ psi ^ n \,

satisfaz a mesma recorrência

U_n = a \ varphi ^ {n-1} + b \ psi ^ {n-1} + a \ varphi ^ {n-2} + b \ psi ^ {n-2} = U_ {n-1} + U_ {n-2}. \,

Se a 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 a e b satisfazer o sistema de equações:

\ \ Left {\ begin {array} {l} a + b = 0 \\ \ varphi a + \ psi b = 1 \ end {array} \ right.

que tem solução

a = \ frac {1} {\ varphi- \ psi} = \ frac {1} {\ sqrt 5}, \, b = -a

produzindo a fórmula necessária.

Computação arredondando

Desde

\ Frac {| \ psi | ^ n} {\ sqrt 5} <\ frac {1} {2}

para todo n ≥ 0, o número F n é o número inteiro mais próximo

\ Frac {\ varphi ^ n} {\ sqrt 5} \,.

Por conseguinte, pode ser encontrada por arredondamento, ou em termos de função do assoalho:

F_n = \ Bigg \ lfloor \ frac {\ varphi ^ n} {\ sqrt 5} + \ frac {1} {2} \ Bigg \ rfloor, \ n \ geq 0.

Ou a função de número inteiro mais próximo:

F_n = \ bigg [\ frac {\ varphi ^ n} {\ sqrt 5} \ bigg], \ n \ geq 0.

Se já sabemos que o número F> 1 é um número de Fibonacci, podemos determinar seu índice dentro da sequência por

n (F) = \ Bigg \ lfloor \ log_ \ varphi \ left (F \ cdot \ sqrt {5} + \ frac {1} {2} \ right) \ Bigg \ rfloor

Limite de quocientes consecutivos

Johannes Kepler observou-se que a razão entre os números de Fibonacci consecutivos converge. Ele escreveu que "é como 5 a 8, de modo é de 8 a 13, na prática, e como é 8 a 13, de modo que é quase 13 a 21", e concluiu que o limite se aproxima a proporção φ dourado.

\ Lim_ {n \ to \ infty} \ frac {F_ {n + 1}}} {f_n = \ varphi

Esta convergência não depende dos valores de partida escolhidos, excluindo 0, 0. Por exemplo, os valores iniciais 19 e 31 geram a sequência de 19, 31, 50, 81, 131, 212, 343, 555 ... etc. A proporção de mandatos consecutivos nesta seqüência mostra a mesma convergência para a proporção áurea.

Na verdade isso vale para qualquer seqüência que satisfaz a recorrência de Fibonacci que não seja uma sequência de 0 do. Este pode ser derivado de fórmula de Binet .

Outra consequência é que o limite da relação de dois números de Fibonacci compensado por um desvio finito nomeadamente no índice corresponde à razão de ouro levantada pelo que o desvio. Ou, por outras palavras:

\ Lim_ {n \ to \ infty} \ frac {F_ {n + \ alpha}} {f_n} = \ varphi ^ \ alpha

Decomposição de poderes da proporção áurea

Uma vez que a proporção áurea satisfaz a equação

\ Varphi ^ 2 = \ varphi + 1, \,

Esta expressão pode ser utilizada para decompor potências mais elevadas φ n como uma função linear de potências mais baixas, que por sua vez pode ser decomposto todo o caminho para uma combinação linear de φ e 1. O resultante relações de recorrência deu números de Fibonacci como os coeficientes lineares:

\ Varphi ^ n = f_n \ varphi + F_ {n-1}.

Esta equação pode ser provado por indução sobre n.

Esta expressão também é verdadeira para n <1, se a sequência de Fibonacci F n é estendido para inteiros negativos usando a regra de Fibonacci F_n = F_ {n-1} + F_ {n-2}.

Forma matricial

Um sistema de duas dimensões lineares equações de diferenças que descreve a seqüência de Fibonacci é

\ Begin {align} {F_ {k + 2} \ escolher F_ {k + 1}} & = \ begin {} pmatrix 1 & 1 & 1 \\ 0 \ end {pmatrix} {F_ {k + 1} \ escolher F_ {k}} \\ \ vec F_ {k + 1} = & A \ vec F_ {k} \ end {align}

Os valores próprios da matriz A são \ Scriptstyle \ varphi = \ frac12 (1+ \ sqrt5) \, \! e \ Scriptstyle 1- \ varphi = \ frac12 (1- \ sqrt5) , E os elementos de os vectores próprios de A, \ Scriptstyle {\ varphi \ escolher 1} e \ Scriptstyle {1- \ varphi \ escolher 1} , Estão nas φ rácios e 1-φ Usando estes factos, e as propriedades de valores próprios, pode-se derivar uma fórmula directa para o n-ésimo elemento da série de Fibonacci como um função analítica de n:

F_ {n} = \cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1+\sqrt{5}}{2}\right)^n-\cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1-\sqrt{5}}{2}\right)^n

A matriz tem um determinante de -1, e, portanto, é um 2 × 2 unimodular matriz. Esta propriedade pode ser entendido em termos de representação fração continuou durante a relação dourada:

\ Varphi = 1 + \ cfrac {1} {1 + \ cfrac {1} {1 + \ cfrac {1} {1 + \; \; \ ddots \,}}}

Os números de Fibonacci ocorrer como a razão entre convergentes sucessivos da fracção continuou durante φ, e a matriz formada a partir convergentes sucessivas de qualquer fracção contínua tem um determinante de um ou -1.

A representação matriz dá a seguinte expressão fechada para os números de Fibonacci:

\ Begin {} pmatrix 1 & 1 & 1 \\ 0 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n + 1} & f_n \\ f_n & F_ {n-1} \ end {} pmatrix.

Tomando o determinante de ambos os lados desta equação rendimentos A identidade de Cassini

(-1) ^ N = F_ {n + 1} F_ {n-1} - f_n ^ 2 \ ,.

Além disso, uma vez A ^ n A ^ m = A ^ {m + n} para qualquer matriz quadrada A, as seguintes identidades pode ser derivada:

\ Begin {align} {F_m} {f_n} + {F_ {m-1}} {{F_ n-1}} {F_ & = m + n-1} \\ F_ {n + 1} F_ {m} + f_n F_ {m-1} {F_ & = m + n} \ end {align}

Em particular, com m = n,

\ Begin {align} F_ {2n-1} = & f_n ^ 2 + F_ {n-1} ^ 2 \\ F_ {2n} & = (F_ {n-1} + F_ {n + 1}) f_n \ \ & = (2F_ {n-1} + f_n) f_n \ end {align}

Estes dois últimos identidades fornecem uma maneira de calcular os números de Fibonacci de forma recursiva em O (log (n)) operações aritméticas e em tempo O (M (n) log (n)), onde M (n) é o tempo para a multplication de dois números de n dígitos. Combina com o tempo para o cálculo do n º número de Fibonacci a partir da fórmula de matriz de forma fechada, mas com menos etapas redundantes se se evita a recalcular um já computado o número de Fibonacci (recursão com memorização).

Reconhecendo números de Fibonacci

A pergunta pode surgir se um inteiro positivo z é um número de Fibonacci. Uma vez que f (n) é o número inteiro mais próximo de \ Varphi ^ n / \ sqrt {5} , O, teste de força bruta mais simples é a identidade

F \ left (\ Bigg \ lfloor \ log_ \ varphi \ bigg (z \ cdot \ sqrt {5} + \ frac {1} {2} \ bigg) \ Bigg \ rfloor \ right) = z,

o que é verdade Se e apenas se z é um número de Fibonacci. Nesta fórmula, f (n) pode ser calculada rapidamente usando qualquer um dos anteriormente discutidos expressões de forma fechada.

Uma implicação da expressão acima é o seguinte: se sabe-se que um número z é um número de Fibonacci, que pode determinar um n tal que f (n) = z pelo seguinte:

\ Left \ lfloor \ log_ \ varphi \ bigg (z \ cdot \ sqrt {5} + \ frac {1} {2} \ bigg) \ right \ rfloor = n

Alternativamente, um número inteiro positivo z é um número de Fibonacci se e apenas se um dos 5z ^ 2 + 4 ou 5z ^ 2-4 é um quadrado perfeito.

Um teste ligeiramente mais sofisticado utiliza o facto de a convergentes do representação fração continuada de φ são proporções de números de Fibonacci sucessivos. Isto é, a desigualdade

\ Bigg | \ varphi- \ frac {p} {q} \ bigg | <\ frac {1} {q ^ 2}

(Com coprime números inteiros positivos p, q) é verdadeira se e somente se p e q são números de Fibonacci sucessivos. Deste uma deriva o critério que z é um número de Fibonacci se e apenas se o intervalo fechado

\ Bigg [\ varphi z \ frac {1} {z}, \ varphi + z \ frac {1} {z} \ bigg]

contém um número inteiro positivo. Para z ≥ 2, que é fácil demonstrar que este intervalo contém no máximo um número inteiro, e no caso em que z é um número de Fibonacci, o número inteiro contido é igual ao número de Fibonacci próximo sucessivo após z. Um tanto surpreendentemente, este resultado ainda se mantém para o caso z = 1, mas deve ser afirmado com cuidado desde 1 aparece duas vezes na seqüência de Fibonacci, e, portanto, tem dois sucessores distintas.

Identidades combinatórias

A maioria das identidades envolvendo números de Fibonacci pode ser provada usando argumentos combinatórios usando o fato de que a F n pode ser interpretado como o número de seqüências de 1s e 2s que soma para n - 1. Isso pode ser tomado como a definição de F n, com a convenção de que F 0 = 0, que significa que não soma irá adicionar até -1, e que F 1 = 1, ou seja, a soma vazio irá "somar" a 0. Aqui a ordem das questões summand. Por exemplo, 1 + 2 + 1 e 2 são considerados dois montantes diferentes.

Por exemplo, a relação de recorrência

F_ {n} = F_ {n-1} + F_ {n-2}, \,

ou em palavras, o n-ésimo número de Fibonacci é a soma dos dois números de Fibonacci anteriores, pode ser mostrado pela divisão do f (n) somas de 1s 2s e que adicionam ao n -1 em dois grupos não sobrepostos. Um grupo contém esses montantes cujo primeiro termo é uma ea outra dessas somas cujo primeiro termo é 2. No primeiro grupo os termos restantes adicionar ao n - 2, para que ele tenha F (n -1) as quantias, e no segundo grupo os demais termos adicionar ao n -3, por isso há F (n -2) somas. Portanto, há um total de F (n-1) + F n -2) somas por completo, mostrando isto é igual a F (n).

Do mesmo modo, pode ser mostrado que a soma dos primeiros números de Fibonacci até o enésimo é igual ao (n + 2) -ND número de Fibonacci menos 1. Em símbolos:

\ Sum_ {i = 1} ^ n f_i = F_ {n + 2} - 1

Isto é feito dividindo as somas adicionando a n + 1 de uma maneira diferente, neste momento, a localização do primeiro 2. Especificamente, o primeiro grupo consiste nos montantes que começam com 2, o segundo grupo os que começam 1 + 2 , o terceiro 1 + 1 + 2, e assim por diante, até ao último grupo que consiste na soma simples, onde apenas um de são utilizados. O número de somas do primeiro grupo é f (n), F (n - 1), no segundo grupo, e assim por diante, com uma soma no último grupo. Assim, o número total de somas é f (n) + M (n -1) + ... + F (1) 1 e, portanto, esta quantidade é igual a f (n 2)

Um argumento semelhante, agrupando as somas pela posição do primeiro 1 ao invés da primeira 2, dá mais duas identidades:

\ Sum_ {i = 0} ^ {n-1} F_ {2i + 1} = F_ {2n}

e

\ Sum_ {i = 1} ^ {n} F_ {} = 2i F_ {2n + 1} -1.

Em outras palavras, a soma dos primeiros números de Fibonacci com índice ímpar até F 2n-1 é a (2n) th número de Fibonacci, e a soma dos primeiros números de Fibonacci com mesmo índice até F 2 N é a (2n + 1) -ésima número de Fibonacci menos 1.

Um truque diferente pode ser usado para provar

\ Sum_ {i = 1} ^ n {f_i} ^ 2 = F_ {n} F_ {n + 1},

ou em palavras, a soma dos quadrados dos primeiros números de Fibonacci-se a F n é o produto do th n e (n + 1) -ésima números de Fibonacci. Neste caso, nota que Fibonacci rectângulo de tamanho F por F n (n + 1) pode ser decomposto em quadrados de tamanho F F N, N-1, e assim por diante para F = 1 1, a partir da qual a identidade segue por comparação das áreas .

Outras identidades

Existem numerosas outras identidades, que podem ser derivados usando vários métodos. Alguns dos mais notáveis são:

Identidade do catalão:

F_n ^ 2 - F_ {n + r} F_ {n-R} = (-1) ^ {n-r ^ 2} F_r

Identidade da Cassini:

F_n ^ 2 - F_ {n + 1} F_ {n-1} = (-1) ^ {n-1}

A identidade de d'Ocagne:

F_m F_ {n + 1} - F_ {m + 1} f_n = (-1) F_ ^ n {m} n-
F_ {2n} = F_ {n + 1} ^ 2 - F_ {n-1} ^ 2 = f_n \ left (F_ {n + 1} + F_ {n-1} \ right) = F_nL_n

em que L n representa o n 'th Número Lucas. A última é uma identidade para a duplicação n; outras identidades deste tipo são

F_ {3n} = 2F_n ^ 3 + 3F_n F_ {n + 1} F_ {n-1} = ^ 5F_n 3 + 3 (-1) ^ n f_n

por identidade de Cassini.

\ Begin {align} F_ {3n + 1} = & F_ {n + 1} ^ 3 + 3 F_ {n + 1} f_n ^ 2 - f_n ^ 3 \\ F_ {3n + 2} & = F_ {n + 1} ^ 3 + 3 F_ {n + 1} ^ + 2F_n f_n ^ 3 \\ F_ {} 4n & = 4F_nF_ {n + 1} \ left (F_ {n + 1} ^ 2 + 2F_n ^ 2 \ right) - 3F_n ^ 2 \ left (f_n ^ 2 + 2F_ {n + 1} ^ 2 \ right) \ end {align}

Estes podem ser encontrados experimentalmente usando redução da estrutura, e são úteis na criação da especial peneira campo número para fatorar um número de Fibonacci.

Mais geralmente,

F_ {kn + c} = \ sum_ {i = 0} ^ {k k \ escolher i} F_ {ci} f_n ^ i F_ {n + 1} ^ {} ki.

Colocando k = 2 nesta fórmula, obtém-se novamente as fórmulas do final da secção acima forma Matrix .

Séries de potências

O função geradora da sequência de Fibonacci é a série de potência

s (x) = \ sum_ {k = 0} ^ {\ infty} F_k x ^ k.

Esta série é convergente para | X | <\ frac {1} {\ varphi}, e sua soma tem uma forma fechada simples:

s (x) = \ frac {x} {1-x-x ^ 2}

Isto pode ser comprovada utilizando a recorrência de Fibonacci para expandir cada coeficiente no soma infinita:

\ Begin {align} s (x) & = \ sum_ {k = 0} ^ {\ infty} F_k x ^ k \\ & = F_0 + F_1x + \ sum_ {k = 2} ^ {\ infty} \ left ( F_ {k-1} + F_ {k-2} \ right) x ^ k \\ & = x + \ sum_ {k = 2} ^ {\ infty} F_ {k-1} x ^ k + \ sum_ { k = 2} ^ {\ infty} F_ {k-2} x ^ k \\ & = x + x \ sum_ {k = 0} ^ {\ infty} F_k x ^ k + x ^ 2 \ sum_ {k = 0} ^ {\ infty} F_k x ^ k \\ & = x + xs (x) + x ^ 2 s (x). \ End {align}

Resolvendo a equação

s (x) = x + xs (x) + x ^ 2s (x)

por s (x) resulta no exemplo acima de forma fechada.

Se X é o inverso de um número inteiro, a forma fechada da série torna

\ Sum_ {n = 0} ^ \ infty \, \ frac {f_n} {k ^ {n}} \, = \, \ frac {} {k k ^ {2} k-1}.

Em particular,

\ Sum_ {n = 1} ^ {\ infty} {\ frac {f_n} {{10 ^ (k + 1) (n + 1)}}} = \ frac {1} {10 ^ {2k + 2} - 10 ^ {k + 1} - 1}

para todos os inteiros não negativos de k.

Alguns matemática quebra-livros como presente curioso o valor particular \ frac {s (\ frac {1} {10})} {10} = \ frac {1} {89} .

Somas recíprocas

Somas infinitas sobre números de Fibonacci recíprocas às vezes pode ser avaliado em termos de funções teta. Por exemplo, podemos escrever a soma de todos os números de Fibonacci recíproca odd-indexado como

\ Sum_ {k = 0} ^ \ infty \ frac {1} {F_ {2k + 1}} = \ frac {\ sqrt {5}} {4} \ vartheta_2 ^ 2 \ esquerdo (0, \ frac {3- \ sqrt 5} {2} \ right),

ea soma dos números de Fibonacci recíprocas quadrados como

\ Sum_ {k = 1} ^ \ infty \ frac {1} {2} F_k ^ = \ frac {5} {24} \ left (\ vartheta_2 ^ 4 \ esquerdo (0, \ frac {3- \ sqrt 5} {2} \ right) - \ vartheta_4 ^ 4 \ esquerdo (0, \ frac {3- \ sqrt 5} {2} \ right) + 1 \ right).

Se se adicionar 1 a cada número de Fibonacci na primeira soma, há também a forma fechada

\ Sum_ {k = 0} ^ \ infty \ frac {1} {1 + F_ {2k + 1}} = \ frac {\ sqrt {5}} {2},

e existe uma soma aninhada agradável de números de Fibonacci quadrados dando o recíproco da relação dourada ,

\ Sum_ {k = 1} ^ \ infty \ frac {(- 1) ^ {k + 1}} {\ sum_ {j = 1} ^ {k F_ {j}} ^ 2} = \ frac {\ sqrt { 5} -1} {2}.

Resultados como estes tornam plausível que uma fórmula fechada para a soma simples dos números de Fibonacci recíprocas poderia ser encontrado, mas nenhum é ainda conhecida. Apesar disso, o constante Fibonacci recíproco

\ Psi = \ sum_ {k = 1} ^ {\ infty} \ frac {1} {F_k} = 3,359885666243 \ dots

Ficou provado irracional por Richard André-Jeannin.

Série Millin dá uma identidade notável:

\ Sum_ {n = 0} ^ {\ infty} \ frac {1} {F_ {2 ^ n}} = \ frac {7 - \ sqrt {5}} {2}

que decorre da forma fechada para suas somas parciais como N tende para o infinito:

\ Sum_ {n = 0} ^ N \ frac {1} {F_ {2}} ^ n = 3 - \ frac {F_ {2 ^ N-1}} {{F_ 2 ^ N}}.

Primes e divisibilidade

Propriedades divisibilidade

Cada terceiro número da sequência é ainda e de forma mais geral, todos os k-ésimo número da sequência é um múltiplo de F k. Assim, a sequência de Fibonacci é um exemplo de um seqüência divisibilidade. De fato, a seqüência de Fibonacci satisfaz a propriedade divisibilidade mais forte

\ Mdc (F_m, f_n) = F _ {\ mdc (m, n)} \,.

Primes de Fibonacci

A principal Fibonacci é um número de Fibonacci que é nobre . Os primeiros são:

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, ... (sequência A005478 em OEIS ).

Fibonacci primos com milhares de dígitos têm sido encontrados, mas não se sabe se existem infinitas.

F kn é divisível por F n, então, F 4 = 3 para além de, qualquer injeção Fibonacci deve ter um índice principal. Como existem arbitrariamente longas de números compostos, há, portanto, também arbitrariamente longas de números de Fibonacci compostas.

Com as exceções de 1, 8 e 144 (F 1 = F 2, F 6 e F 12) a cada número de Fibonacci tem um fator primordial que não é um fator de qualquer número menor Fibonacci ( Teorema de Carmichael).

O único não-trivial quadrado de números de Fibonacci é 144. Attila Pethő provou em 2001 que existe apenas um número finito de números de Fibonacci poder perfeitos. Em 2006, Y. Bugeaud, M. Mignotte, e S. Siksek provou que 8 e 144 são os únicos tais poderes perfeitos não-triviais.

Sem número de Fibonacci maior do que F 6 = 8 é um maior ou um menor que um número primo.

Quaisquer três números de Fibonacci consecutivos, tomados dois de cada vez, são relativamente primos: isto é,

mdc (F n, F n +1) = mdc (F n, F n 2) = 1.

Mais geralmente,

mdc (F n, F m) = F mdc (n, m).

Divisores primos de números de Fibonacci

A divisibilidade de números de Fibonacci por um primo p está relacionada com a Legendre símbolo \ Left (\ tfrac {p} {5} \ right) que é avaliada como se segue:

\ Left (\ frac {p} {5} \ right) = \ begin {cases} 0 & \ textrm {if} \; p = 1 & 5 \\ \ textrm {if} \; p \ equiv \ pm1 \ pmod 5 \\ -1 & \ textrm {if} \; p \ equiv \ pm2 \ pmod 5. \ end {cases}

Se p é um número primo, em seguida,

F_p \ equiv \ left (\ frac {p} {5} \ right) \ pmod p \ quad \ text {e} \ quad F_ {p \ left (\ frac {p} {5} \ right)} \ equiv 0 \ pmod p.

Por exemplo,

\ Begin {align} (\ tfrac {2} {5}) & = -1, e F_3 & = 2, e f_2 & = 1, \\ (\ tfrac {3} {5}) & = -1, e F_4 & = 3 , & F_3 & = 2, \\ (\ tfrac {5} {5}) & = 0, e F_5 & = 5, \\ (\ tfrac {7} {5}) & = -1, e F_8 & = 21, e F_7 & = 13, \\ (\ tfrac {11} {5}) & = 1, e F_ {10} e = 55, e F_ {11} e = 89. \ End {align}

Desconhece-se se existe um número primo tal que p

F_ {p \ left (\ frac {p} {5} \ right)} \ equiv 0 \ pmod {p ^ 2}.

Tais números primos (se houver algum) seriam chamados Wall-Sun-Sun primos.

Além disso, se p ≠ 5 é um número primo ímpar então:

5F ^ 2 _ {\ frac {p \ pm 1} {2}} \ equiv \ begin {cases} \ tfrac {1} {2} \ left (5 \ left (\ frac {p} {5} \ right) \ 5 pm \ right) \ pmod p & \ textrm {if} \; p \ equiv 1 \ 4 pmod \\ \ tfrac {1} {2} \ left (5 \ left (\ frac {p} {5} \ right ) \ mp 3 \ right) \ pmod p & \ textrm {if} \; p \ equiv 3 \ pmod 4. \ end {cases}

Exemplo 1. P = 7, neste caso, p ≡ 3 (mod 4) e tem-se:

(\ Tfrac {7} {5}) = -1: \ qquad \ tfrac {1} {2} \ left (5 (\ tfrac {7} {5}) + 3 \ right) = -1, \ quad \ tfrac {1} {2} \ left (5 (\ tfrac {7} {5}) - 3 \ right) = - 4.
F_3 = 2 \ text {} e F_4 = 3.
5F_3 ^ 2 = 20 \ equiv -1 \ pmod {7} \; \; \ text {e} \; \; 5F_4 ^ 2 = 45 \ equiv -4 \ pmod {7}

Exemplo 2. p = 11, neste caso, p ≡ 3 (mod 4) e tem-se:

(\ Tfrac {11} {5}) = +1: \ qquad \ tfrac {1} {2} \ left (5 (\ tfrac {11} {5}) + 3 \ right) = 4, \ quad \ tfrac {1} {2} \ left (5 (\ tfrac {11} {5}) - 3 \ right) = 1.
F_5 = 5 \ text {} e F_6 = 8.
5F_5 ^ 2 = 125 \ equiv 4 \ pmod {11} \; \; \ text {e} \; \; 5F_6 ^ 2 = 320 \ equiv 1 \ pmod {11}

Exemplo 3. p = 13, neste caso, p ≡ 1 (mod 4) e tem-se:

(\ Tfrac {13} {5}) = -1: \ qquad \ tfrac {1} {2} \ left (5 (\ tfrac {13} {5}) - 5 \ right) = -5, \ quad \ tfrac {1} {2} \ left (5 (\ tfrac {13} {5}) + 5 \ right) = 0.
F_6 = 8 \ text {} e F_7 = 13.
5F_6 ^ 2 = 320 \ equiv -5 \ pmod {13} \; \; \ text {e} \; \; 5F_7 ^ 2 = 845 \ equiv 0 \ {13} pmod

Exemplo 4. p = 29, neste caso, p ≡ 1 (mod 4) e tem-se:

(\ Tfrac {29} {5}) = +1: \ qquad \ tfrac {1} {2} \ left (5 (\ tfrac {29} {5}) - 5 \ right) = 0, \ quad \ tfrac {1} {2} \ left (5 (\ tfrac {29} {5}) + 5 \ right) = 5.
F_ {14} = 377 \ text {e} F_ {15} = 610.
5F_ {14} ^ 2 = 710.645 \ equiv 0 \ pmod {29} \; \; \ text {e} \; \; 5F_ {15} ^ 2 = 1.860.500 \ equiv 5 \ pmod {29}

Para ímpar n, todos os divisores primos ímpares de F n são congruentes para um módulo 4, o que implica que todos os divisores impares de F n (como os produtos de divisores primos ímpares) são congruentes para um módulo 4.

Por exemplo,

F_1 = 1, F_3 = 2, F_5 = 5, F_7 = 13, F_9 = 34 = 2 \ cdot 17, F_ {11} = 89, F_ {13} = 233, F_ {15} = 610 = 2 \ cdot 5 \ cdot 61.

Todos os fatores conhecidos de Fibonacci números F (i) para todo i <50000 são coletados nas repositórios relevantes.

Periodicidade módulo n

Pode ser visto que, se os membros da sequência de Fibonacci são tomadas mod n, a sequência resultante tem de ser periódica com período de, no máximo, 2 n-1. Os comprimentos dos períodos de várias N formam a chamada Períodos Pisano (sequência A001175 em OEIS ). Determinação dos períodos Pisano em geral é um problema em aberto, embora para qualquer n especial que pode ser resolvido como uma instância de detecção ciclo.

Triângulos retângulos

Começando com 5, cada segundo número de Fibonacci é o comprimento da hipotenusa de um triângulo com lados inteiros, ou em outras palavras, o maior número de Tripla de Pitágoras. O comprimento da perna mais comprida deste triângulo é igual à soma dos três lados do triângulo anterior nesta série de triângulos, e a perna mais curta é igual à diferença entre o número anterior de Fibonacci ignorada e a perna mais curta do que precede triângulo.

O primeiro triângulo nesta série tem lados de comprimento 5, 4, e 3. Skipping 8, o próximo triângulo tem lados de comprimento 13, 12 (5 + 4 + 3), e 5 (8-3). Ignorando 21, a próxima triângulo tem lados de comprimento 34, 30 (13 + 12 + 5), e 16 (21 - 5). Esta série continua indefinidamente. Os lados do triângulo a, b, c podem ser calculados directamente:

\ Displaystyle a_n = F_ {2n-1}
\ Displaystyle b_n = 2 f_n F_ {n-1}
\ Displaystyle c_n = f_n ^ 2 - F_ {n-1} ^ 2.

Estas fórmulas satisfazer a_n ^ 2 = b_n ^ 2 + c_n ^ 2 para todo n, mas representam apenas os lados do triângulo quando n> 2.

Qualquer quatro números consecutivos de Fibonacci F n, n F 1, F 2 e F n n 3 também pode ser utilizado para gerar um triplo Pitágoras de um modo diferente:

a = f_n F_ {n + 3} \,; \, B = 2 F_ {n + 1} F_ {n + 2} \,; \, C = F_ {n + 1} ^ 2 + F_ {n + 2} ^ 2 \,; \, A ^ 2 + b = c ^ 2 ^ 2 \ ,.

Exemplo 1: deixe que os números de Fibonacci ser 1, 2, 3 e 5. Em seguida:

\ Displaystyle a = 1 \ times 5 = 5
\ Displaystyle b = 2 \ times 2 \ times 3 = 12
\ Displaystyle c = 2 ^ 2 + 3 ^ 2 = 13 \,
\ Displaystyle 5 ^ 2 + 2 = 12 ^ 13 ^ 2 \ ,.

Magnitude

Uma vez que F n seja assintótica para \ Varphi ^ n / \ sqrt5 , O número de dígitos em F n é assintótica para n \, \ log_ {10} \ varphi \ approx0.2090 \, n . Como consequência, para cada inteiro d> 1 há 4 ou 5 números de Fibonacci com dígitos decimais d.

Em termos mais gerais, na representação base b, o número de dígitos F n é assintOticas n \, \ log_b \ varphi .

Aplicações

Os números de Fibonacci são importantes na análise computacional de tempo de execução de O algoritmo de Euclides para determinar o maior divisor comum dos dois inteiros: o pior caso de entrada para este algoritmo é um par de números consecutivos de Fibonacci.

Yuri Matiyasevich foi capaz de mostrar que os números de Fibonacci pode ser definido por um Diophantine equação, o que levou a sua solução original de Décimo problema de Hilbert.

Os números de Fibonacci também são um exemplo de um sequência completa. Isto significa que cada número inteiro positivo pode ser escrito como uma soma de números de Fibonacci, onde qualquer um número é usada uma vez, no máximo. Especificamente, cada número inteiro positivo pode ser escrita de uma forma única como a soma de um ou mais números de Fibonacci distintos, de tal forma que a soma não inclui quaisquer dois números consecutivos de Fibonacci. Isto é conhecido como Teorema de Zeckendorf, e uma soma de números de Fibonacci que satisfaça essas condições é chamado de representação Zeckendorf. A representação Zeckendorf de um número pode ser utilizado para derivar a sua Fibonacci codificação.

Números de Fibonacci são usados por alguns geradores de números pseudo-aleatórios.

Números de Fibonacci são usados em uma versão polifásico da merge algoritmo de classificação em que uma lista não ordenada é dividido em duas listas cujos comprimentos correspondem a seqüenciais números de Fibonacci - dividindo a lista para que as duas partes têm comprimentos na φ proporção aproximada. A implementação de fita-drive do polyphase merge sort foi descrito em The Art of Computer Programming.

Números de Fibonacci surgem na análise do Estrutura de dados heap Fibonacci.

O Cubo de Fibonacci é uma grafo não-dirigido com um número de nós de Fibonacci que tem sido proposto como um topologia da rede para computação paralela.

Um método de optimização unidimensional, a chamada Fibonacci técnica de pesquisa, utiliza números de Fibonacci.

A série de números de Fibonacci é usado para opcional compressão com perdas na IFF Formato de arquivo de áudio usado em 8SVX Computadores Amiga. O número de série compands a onda de áudio original semelhante aos métodos tais como logarítmicas μ-law.

Uma vez que o fator de conversão para 1.609344 milhas para quilômetros fica perto da proporção áurea (φ denotado), a decomposição da distância em milhas em uma soma de números de Fibonacci torna-se quase a soma km quando os números de Fibonacci são substituídos por seus sucessores. Este método constitui uma radix número 2 inscrever-se dourado φ base de relação a ser deslocado. Para converter de quilómetros para milhas, deslocar o registro para baixo a seqüência de Fibonacci em vez disso.

Natural

Cabeça camomila amarela que mostra a disposição em 21 (azul) e 13 (aqua) espirais. Tais disposições que envolvam números de Fibonacci consecutivos aparecem numa grande variedade de plantas.

Sequências de Fibonacci aparecem nas definições biológicos, em dois números de Fibonacci consecutivos, tais como ramificação em árvores, arranjo das folhas em uma haste, de um dos frutilhos abacaxi, o florescimento de alcachofra, um fern desenrolar e o arranjo de um pinha. Além disso, inúmeras reivindicações mal fundamentadas de números de Fibonacci ou seções de ouro na natureza são encontrados em fontes populares, por exemplo, relativas à criação de coelhos em próprio exemplo irrealista de Fibonacci, as sementes em um girassol, as espirais dos escudos, e a curva de ondas. Os números de Fibonacci também são encontradas na árvore de família de abelhas.

Przemysław Prusinkiewicz avançou a ideia de que os casos reais podem em parte ser entendida como a expressão de certas restrições algébricas no grupos livres, especificamente como certa Gramáticas Lindenmayer.

Ilustração do modelo de Vogel para n = 1 ... 500

Um modelo para o padrão de florzinhas na cabeça de um girassol foi proposto por H. Vogel em 1979. Isto tem a forma

\ Theta = \ frac {2 \ pi} {\ phi ^ 2} n, \ r = c \ sqrt {n}

onde n é o número de índice do flósculo e c é um factor de escalonamento constante; as florzinhas mentir assim em espiral de Fermat. O ângulo de divergência, de aproximadamente 137,51 °, é o ângulo de ouro, dividindo o círculo na razão de ouro. Porque este rácio é irracional, não tem floret um vizinho, exatamente no mesmo ângulo a partir do centro, para as florzinhas embalar de forma eficiente. Porque as aproximações racionais para a proporção áurea são da forma F ( j ): F ( j + 1), os vizinhos mais próximos do número floret n são aqueles em n ± F ( j ) por algum índice j que depende de r , o distância a partir do centro. Costuma-se dizer que girassóis e em acordos semelhantes têm 55 espirais em uma direção e 89 na outra (ou algum outro par de números de Fibonacci adjacentes), mas isso é verdade apenas de uma gama de raios, tipicamente o mais externo e, portanto, mais conspícua.

O código de abelha ascendência

Números de Fibonacci também aparecem na descrição da reprodução de uma população de abelhas idealizadas, de acordo com as seguintes regras:

  • Se um ovo é colocado por uma fêmea unmated, ele escotilhas um macho ouzangão da abelha.
  • Se, no entanto, um ovo fertilizado de um macho, uma fêmea de chocar.

Assim, uma abelha macho sempre vai ter um pai e uma abelha fêmea terá dois.

Se uma traça a ascendência de qualquer abelha macho (1 abelha), ele tem um pai (1 abelha), 2 avós, bisavós 3, 5 tatara-tatara-avós, e assim por diante. Esta seqüência de números de pais é a seqüência de Fibonacci. O número de ancestrais em cada nível, F n , é o número de ancestrais fêmea, que é F n-1 , mais o número de ancestrais do sexo masculino, que é F n-2 . Este é sob a suposição irrealista de que os antepassados ​​de cada nível são de outra maneira não relacionado.

Cultura popular

Generalizações

A seqüência de Fibonacci foi generalizada em muitas maneiras. Estes incluem:

  • Generalizando o índice de números inteiros negativos para produzir osNegafibonaccinúmeros.
  • Generalizando o índice de números reais, utilizando uma modificação da fórmula de Binet.
  • Começando com outros números inteiros.Lucas têm númerosG 1= 1,G 2= 3, eLn=L n-1+L n-2.Primefree sequências usar a recursividade de Fibonacci com outros pontos de partida, a fim de gerar sequências nas quais todos os números sãocompósito.
  • Deixando um número ser uma função linear (excepto a soma) dos dois números anteriores. O Pell têm númerosPn= 2P n- 1+P n- 2.
  • Não se adicionam os números imediatamente anteriores. O sequência Padovan etêm números de PerrinP(n) =P(n- 2) +P(n- 3).
  • Gerando o próximo número, adicionando 3 números (números tribonacci), 4 números (números tetranacci), ou mais. As seqüências resultantes são conhecidos como números de Fibonacci n-Step .
  • Adicionando outros objetos de números inteiros, por exemplo, funções ou exemplo essencial cordas-One estápolinômios de Fibonacci.
Retirado de " http://en.wikipedia.org/w/index.php?title=Fibonacci_number&oldid=549637248 "