Sequência de Fibonacci

AjustarCompartirImprimirCitar

Números obtidos adicionando os dois anteriores

Um tilingue com quadrados cujos comprimentos laterais são números Fibonacci sucessivos: 1, 1, 2, 3, 5, 8, 13 e 21.

Na matemática, a sequência de Fibonacci é uma sequência na qual cada número é a soma dos dois anteriores. Números individuais na sequência de Fibonacci são conhecidos como números de Fibonacci, comumente denotados $F n$ . A sequência geralmente começa de 0 e 1, embora alguns autores comecem a sequência de 1 e 1 ou às vezes (como Fibonacci) de 1 e 2. Começando de 0 e 1, os primeiros valores na sequência são:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.

Os números de Fibonacci foram descritos pela primeira vez na matemática indiana, já em 200 aC no trabalho de Pingala sobre a enumeração de possíveis padrões de poesia sânscrita formada a partir de sílabas de dois comprimentos. Eles receberam o nome do matemático italiano Leonardo de Pisa, mais tarde conhecido como Fibonacci, que introduziu a sequência na matemática da Europa Ocidental em seu livro de 1202 Liber Abaci.

Os números de Fibonacci aparecem inesperadamente com frequência na matemática, tanto que existe um jornal inteiro dedicado ao 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 pilha de Fibonacci, e gráficos chamados cubos de Fibonacci usados para interconectar sistemas paralelos e distribuídos. Eles também aparecem em ambientes biológicos, como a ramificação das árvores, o arranjo das folhas em um caule, os brotos de um abacaxi, a floração de uma alcachofra, uma samambaia que se desenrola e o arranjo das brácteas de uma pinha..

Os números de Fibonacci também estão fortemente relacionados à proporção áurea: a fórmula de Binet expressa o $n$ ésimo número de Fibonacci em termos de $n$ e a proporção áurea, e implica que a proporção de dois números de Fibonacci consecutivos tende para a proporção áurea como $n$ aumenta. Os números de Fibonacci também estão intimamente relacionados aos números de Lucas, que obedecem à mesma relação de recorrência e com os números de Fibonacci formam um par complementar de sequências de Lucas.

Definição

A espiral de Fibonacci: uma aproximação da espiral dourada criada pelo desenho de arcos circulares que ligam os cantos opostos de praças na camada de Fibonacci; (ver imagem precedente)

Os números de Fibonacci podem ser definidos pela relação de recorrência

{displaystyle F_{0}=0,quad F_{1}=1,}

{displaystyle F_{n}=F_{n-1}+F_{n-2}}

n > 1

Em algumas definições mais antigas, o valor $F_{0}=0$ é omitido, de modo que a sequência começa com ${displaystyle F_{1}=F_{2}=1,}$ e a recorrência ${displaystyle F_{n}=F_{n-1}+F_{n-2}}$ é válido para $n > 2$ .

Os primeiros 20 números de Fibonacci $F n$ são:

F₀	F₁	F₂	F₃	F₄	F₅	F₆	F₇	F₈	F₉	F_10.	F₁₁	F₁₂	F₁₃	F₁₄	F₁₅	F_16.	F_17.	F_18.	F₁₉
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181

História

Índia

Treze (F₇) formas de organizar sílabas longas e curtas em uma cadência de comprimento seis. Oito.F₆) terminar com uma sílaba curta e cinco (F₅) terminar com uma sílaba longa.

A sequência de Fibonacci aparece na matemática indiana, em conexão com a prosódia sânscrita. 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ílabas curtas (S) 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 desde Pingala (c. 450 BC–200 BC). 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 $m$ batidas ( $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 BC–c. 350 AD). No entanto, a exposição mais clara da sequência surge na obra de Virahanka (c. 700 DC), cujo próprio trabalho está perdido, 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 misturados, cinco acontece. [trabalha exemplos 8, 13, 21]... Desta forma, o processo deve ser seguido em tudo 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 penúltimo é o número... do próximo mātrā-vṛtta.& #34;

Europa

Uma página de Fibonacci Liber Abaci da Biblioteca Nazionale di Firenze mostrando (em caixa à direita) 13 entradas da sequência Fibonacci:
os índices de presente a XII (mês) como ordinais latinos e numerais romanos e os números (de pares de coelhos) como numerais hindus-árabes começando com 1, 2, 3, 5 e terminando com 377.

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), assumindo que: um par reprodutor recém-nascido de coelhos é colocado em um campo; cada casal reprodutor acasala com um mês de idade e, ao final do segundo mês, sempre produz outro casal de coelhos; e os coelhos nunca morrem, mas continuam se reproduzindo para sempre. Fibonacci colocou 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, então há 2 pares no campo.
No final do terceiro mês, o par original produz um segundo par, mas o segundo par só mate para gestar por um mês, então há 3 pares em tudo.
No final do quarto mês, o par original produziu mais um novo par, e o par nascido há dois meses também produz seu primeiro par, fazendo 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 vivos no mês passado (mês $n - 1$ ). O número no $n$ º mês é o $n$ º Fibonacci número.

O nome "Sequência de Fibonacci" foi usado pela primeira vez pelo teórico dos números do século XIX Édouard Lucas.

Em uma população crescente idealizada, o número de pares de coelhos formam a sequência de Fibonacci. Em o fim do no mês, o número de pares é igual a F_n.

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 possuem uma expressão de forma fechada. Tornou-se 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:

{displaystyle F_{n}={frac {varphi ^{n}-psi ^{n}}{varphi -psi }}={frac {varphi ^{n}-psi ^{n}}{sqrt {5}}},}

{displaystyle varphi ={frac {1+{sqrt {5}}}{2}}approx 1.61803,39887ldots }

?

{displaystyle psi ={frac {1-{sqrt {5}}}{2}}=1-varphi =-{1 over varphi }approx -0.61803,39887ldots.}

Desde então ${displaystyle psi =-varphi ^{-1}}$ , esta fórmula também pode ser escrita como

{displaystyle F_{n}={frac {varphi ^{n}-(-varphi)^{-n}}{sqrt {5}}}={frac {varphi ^{n}-(-varphi)^{-n}}{2varphi -1}}.}

Para ver a relação entre a sequência e essas constantes, observe que os estilos $φ$ e $ψ$ são ambas as soluções da equação

{displaystyle x^{2}=x+1quad {text{and, thus,}}quad x^{n}=x^{n-1}+x^{n-2},}

φ

?

{displaystyle varphi ^{n}=varphi ^{n-1}+varphi ^{n-2} }

{displaystyle psi ^{n}=psi ^{n-1}+psi ^{n-2}.}

Segue-se que para quaisquer valores $a$ e $b$ , a sequência definida por

{displaystyle U_{n}=avarphi ^{n}+bpsi ^{n}}

{displaystyle U_{n}=avarphi ^{n}+bpsi ^{n}=a(varphi ^{n-1}+varphi ^{n-2})+b(psi ^{n-1}+psi ^{n-2})=avarphi ^{n-1}+bpsi ^{n-1}+avarphi ^{n-2}+bpsi ^{n-2}=U_{n-1}+U_{n-2}}

Se $a$ e $b$ forem escolhidos para que $U 0 = 0$ e $U 1 = 1$ então a sequência resultante $U n$ deve seja a sequência de Fibonacci. Isso é o mesmo que exigir que $a$ e $b$ satisfaçam o sistema de equações:

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

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

Tomando os valores iniciais $U 0$ e $U 1$ como constantes arbitrárias, uma solução mais geral é:

{displaystyle U_{n}=avarphi ^{n}+bpsi ^{n}}

{displaystyle a={frac {U_{1}-U_{0}psi }{sqrt {5}}}}

{displaystyle b={frac {U_{0}varphi -U_{1}}{sqrt {5}}}.}

Cálculo por arredondamento

Desde

<math alttext="{displaystyle left|{frac {psi ^{n}}{sqrt {5}}}right||? ? n5|<12{displaystyle left|{frac {psi ^{n}}{sqrt {5}}}right|<{frac Não.<img alt="{displaystyle left|{frac {psi ^{n}}{sqrt {5}}}right|

para todos $n \geq 0$ , o número $F n$ é o inteiro mais próximo ${frac {varphi ^{n}}{sqrt {5}}}$ . Portanto, ele pode ser encontrado por arredondamento, usando a função de inteiro mais próxima:

{displaystyle F_{n}=leftlfloor {frac {varphi ^{n}}{sqrt {5}}}rightrceil ngeq 0.}

Na verdade, o erro de arredondamento é muito pequeno, sendo menor que 0,1 para $n \geq 4$ , e menor que 0,01 para $n \geq 8$ .

Os números de Fibonacci também podem ser calculados por truncamento, em termos da função de piso:

{displaystyle F_{n}=leftlfloor {frac {varphi ^{n}}{sqrt {5}}}+{frac {1}{2}}rightrfloor ngeq 0.}

Como a função floor é monotônica, a última fórmula pode ser invertida para encontrar o índice $n (F)$ do menor número de Fibonacci que não seja menor que um inteiro positivo $F$ :

{displaystyle n(F)=leftlceil log _{varphi }left(Fcdot {sqrt {5}}-{frac {1}{2}}right)rightrceil}

{displaystyle log _{varphi }(x)=ln(x)/ln(varphi)=log _{10}(x)/log _{10}(varphi)}

{displaystyle ln(varphi)=0.481211ldots }

{displaystyle log _{10}(varphi)=0.208987ldots }

Magnitude

Desde então F_n é assintótico $varphi ^{n}/{sqrt {5}}$ , o número de dígitos em F_n é assintótico ${displaystyle nlog _{10}varphi approx 0.2090,n}$ . Como consequência, para cada inteiro D > 1 os números de 4 ou 5 Fibonacci com D dígitos decimais.

Mais geralmente, na base b) representação, o número de dígitos em F_n é assintótico ${displaystyle nlog _{b}varphi.}$

Limite de quocientes consecutivos

Johannes Kepler observou que a proporção de números fibonacci consecutivos converge. Ele escreveu que "como 5 é para 8 assim é 8 a 13, praticamente, e como 8 é para 13, assim é 13 a 21 quase", e concluiu que essas razões se aproximam da proporção de ouro ${displaystyle varphi colon }$

{displaystyle lim _{nto infty }{frac {F_{n+1}}{F_{n}}}=varphi.}

Esta convergência mantém independentemente dos valores iniciais $U_{0}$ e $U_{1}$ A menos que ${displaystyle U_{1}=-U_{0}/varphi }$ . 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 relação de ouro.

Em geral, ${displaystyle lim _{nto infty }{frac {F_{n+m}}{F_{n}}}=varphi ^{m}}$ , porque as razões entre números Fibonacci consecutivos aproxima-se $varphi$ .

Tábuas bem sucedidas do avião e um gráfico de aproximações à proporção de ouro calculada dividindo cada número de Fibonacci pelo anterior

Decomposição de potências

Como a proporção áurea satisfaz a equação

{displaystyle varphi ^{2}=varphi +1,}

esta expressão pode ser usada para decompor poderes mais elevados $varphi ^{n}$ como uma função linear de poderes inferiores, que por sua vez pode ser decomposto até uma combinação linear de $varphi$ e 1. As relações de recorrência resultantes produzem números de Fibonacci como coeficientes lineares:

{displaystyle varphi ^{n}=F_{n}varphi +F_{n-1}.}

n ≥ 1

{displaystyle varphi ^{n+1}=(F_{n}varphi +F_{n-1})varphi =F_{n}varphi ^{2}+F_{n-1}varphi =F_{n}(varphi +1)+F_{n-1}varphi =(F_{n}+F_{n-1})varphi +F_{n}=F_{n+1}varphi +F_{n}.}

{displaystyle psi =-1/varphi }

{displaystyle psi ^{2}=psi +1}

{displaystyle psi ^{n}=F_{n}psi +F_{n-1}.}

Estas expressões também são verdadeiras para n < 1 se a sequência de Fibonacci F_n é estendido para inteiros negativos usando a regra Fibonacci ${displaystyle F_{n}=F_{n+2}-F_{n+1}.}$

Identificação

A fórmula de Binet fornece uma prova de que um inteiro positivo x é um número de Fibonacci se e somente se pelo menos um $5x^{2}+4$ ou $5x^{2}-4$ é um quadrado perfeito. Isso porque a fórmula de Binet, que pode ser escrita como ${displaystyle F_{n}=(varphi ^{n}-(-1)^{n}varphi ^{-n})/{sqrt {5}}}$ , pode ser multiplicado por ${displaystyle {sqrt {5}}varphi ^{n}}$ e resolvido como uma equação quadrática em $varphi ^{n}$ através da fórmula quadrática:

{displaystyle varphi ^{n}={frac {F_{n}{sqrt {5}}pm {sqrt {5{F_{n}}^{2}+4(-1)^{n}}}}{2}}.}

Comparar isto com ${displaystyle varphi ^{n}=F_{n}varphi +F_{n-1}=(F_{n}{sqrt {5}}+F_{n}+2F_{n-1})/2}$ , segue-se que

{displaystyle 5{F_{n}}^{2}+4(-1)^{n}=(F_{n}+2F_{n-1})^{2},.}

Em particular, o lado esquerdo é um quadrado perfeito.

Forma de matriz

Um sistema bidimensional de equações de diferenças lineares que descreve a sequência de Fibonacci é

{displaystyle {F_{k+2} choose F_{k+1}}={begin{pmatrix}1&1\1&0end{pmatrix}}{F_{k+1} choose F_{k}}}

{displaystyle {vec {F}}_{k+1}=mathbf {A} {vec {F}}_{k},}

que produz ${displaystyle {vec {F}}_{n}=mathbf {A} ^{n}{vec {F}}_{0}}$ . Os autovalores da matriz $A$ são ${displaystyle varphi ={frac {1}{2}}(1+{sqrt {5}})}$ e ${displaystyle psi =-varphi ^{-1}={frac {1}{2}}(1-{sqrt {5}})}$ correspondente aos respectivos eigenvectores

{displaystyle {vec {mu }}={varphi choose 1}}

{displaystyle {vec {nu }}={-varphi ^{-1} choose 1}.}

{displaystyle {vec {F}}_{0}={1 choose 0}={frac {1}{sqrt {5}}}{vec {mu }}-{frac {1}{sqrt {5}}}{vec {nu }},}

n

{displaystyle {begin{aligned}{vec {F}}_{n}&={frac {1}{sqrt {5}}}A^{n}{vec {mu }}-{frac {1}{sqrt {5}}}A^{n}{vec {nu }}\&={frac {1}{sqrt {5}}}varphi ^{n}{vec {mu }}-{frac {1}{sqrt {5}}}(-varphi)^{-n}{vec {nu }}~\&={cfrac {1}{sqrt {5}}}left({cfrac {1+{sqrt {5}}}{2}}right)^{n}{varphi choose 1}-{cfrac {1}{sqrt {5}}}left({cfrac {1-{sqrt {5}}}{2}}right)^{n}{-varphi ^{-1} choose 1},end{aligned}}}

n

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

Equivalentemente, o mesmo cálculo pode ser realizado pela diagonalização de $A$ por meio do uso de sua autocomposição:

{displaystyle {begin{aligned}A&=SLambda S^{-1},\A^{n}&=SLambda ^{n}S^{-1},end{aligned}}}

Lambda ={begin{pmatrix}varphi &0\0&-varphi ^{-1}end{pmatrix}}

{displaystyle S={begin{pmatrix}varphi &-varphi ^{-1}\1&1end{pmatrix}}.}

n

{displaystyle {begin{aligned}{F_{n+1} choose F_{n}}&=A^{n}{F_{1} choose F_{0}}\&=SLambda ^{n}S^{-1}{F_{1} choose F_{0}}\&=S{begin{pmatrix}varphi ^{n}&0\0&(-varphi)^{-n}end{pmatrix}}S^{-1}{F_{1} choose F_{0}}\&={begin{pmatrix}varphi &-varphi ^{-1}\1&1end{pmatrix}}{begin{pmatrix}varphi ^{n}&0\0&(-varphi)^{-n}end{pmatrix}}{frac {1}{sqrt {5}}}{begin{pmatrix}1&varphi ^{-1}\-1&varphi end{pmatrix}}{1 choose 0},end{aligned}}}

que novamente produz

{displaystyle F_{n}={cfrac {varphi ^{n}-(-varphi)^{-n}}{sqrt {5}}}.}

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:

{displaystyle varphi =1+{cfrac {1}{1+{cfrac {1}{1+{cfrac {1}{1+ddots }}}}}}.}

Os números de Fibonacci ocorrem como a razão de convergentes sucessivos da fração contínua para $φ$ , e a matriz formada por 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:

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

Para um dado $n$ , essa matriz pode ser calculada em $o (log (n))$ Operações aritméticas, usando a exponenciação pelo método quadrado.

Tomar o determinante de ambos os lados desta equação produz a identidade de Cassini,

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

Além disso, desde $a n a m = a n + m$ para qualquer quadrado Matrix $a$ , as seguintes identidades podem ser derivadas (elas são obtidas de dois coeficientes diferentes do produto da matriz, e pode -se deduzir facilmente o segundo do de o primeiro alterando $n$ em $n + 1$ ),

{displaystyle {begin{aligned}{F_{m}}{F_{n}}+{F_{m-1}}{F_{n-1}}&=F_{m+n-1},\F_{m}F_{n+1}+F_{m-1}F_{n}&=F_{m+n}.end{aligned}}}

Em particular, com $m = n$ ,

{displaystyle {begin{array}{ll}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}\&=(2F_{n+1}-F_{n})F_{n}.end{array}}}

Essas duas últimas identidades fornecem uma maneira de calcular números de Fibonacci recursivamente na aritmética $O (log(n))$ operações 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 de matriz de forma fechada, mas com menos etapas redundantes se evitarmos recalcular um já calculado Número de Fibonacci (recursão com memoização).

Identidades combinatórias

Provas combinatórias

A maioria das identidades envolvendo números de Fibonacci pode ser provada usando argumentos combinatoriais usando o fato de que $F_{n}$ pode ser interpretado como o número de sequências (possivelmente vazias) de 1s e 2s cuja soma é $n-1$ . Isto pode ser tomado como definição de $F_{n}$ com as convenções $F_{0}=0$ , significando que nenhuma sequência existe cuja soma é −1, e $F_{1}=1$ , significando a sequência vazia "adds up" para 0. No seguinte, ${displaystyle |{...}|}$ é a cardinalidade de um conjunto:

{displaystyle F_{0}=0=|{}|}

{displaystyle F_{1}=1=|{{}}|}

{displaystyle F_{2}=1=|{{1}}|}

{displaystyle F_{3}=2=|{{1,1},{2}}|}

{displaystyle F_{4}=3=|{{1,1,1},{1,2},{2,1}}|}

{displaystyle F_{5}=5=|{{1,1,1,1},{1,1,2},{1,2,1},{2,1,1},{2,2}}|}

Desta forma, a relação de recorrência

{displaystyle F_{n}=F_{n-1}+F_{n-2}}

F_{n}

{displaystyle F_{n}=|{{1,...},{1,...},...}|+|{{2,...},{2,...},...}|}

n-2

n-3

{displaystyle F_{n-1}}

{displaystyle F_{n-2}}

{displaystyle F_{n-1}+F_{n-2}}

F_{n}

De maneira semelhante, pode-se mostrar que a soma dos primeiros números de Fibonacci até o nésimo é igual ao (n + 2)º número de Fibonacci menos 1. Em símbolos:

{displaystyle sum _{i=1}^{n}F_{i}=F_{n+2}-1}

Isso pode ser visto dividindo todas as sequências resumindo a $n+1$ com base na localização do primeiro 2. Especificamente, cada conjunto consiste nessas sequências que começam ${displaystyle {2,...},{1,2,...},...,}$ até os dois últimos conjuntos ${displaystyle {{1,1,...,1,2}},{{1,1,...,1}}}$ cada um com cardinalidade 1.

Seguindo a mesma lógica de antes, somando a cardinalidade de cada conjunto vemos que

{displaystyle F_{n+2}=F_{n}+F_{n-1}+...+|{{1,1,...,1,2}}|+|{{1,1,...,1}}|}

... onde os dois últimos termos têm o valor $F_{1}=1$ . Daqui resulta que $sum _{{i=1}}^{n}F_{i}=F_{{n+2}}-1$ .

Um argumento semelhante, agrupar as somas pela posição do primeiro 1 em vez dos primeiros 2 fornece mais duas identidades:

{displaystyle sum _{i=0}^{n-1}F_{2i+1}=F_{2n}}

{displaystyle sum _{i=1}^{n}F_{2i}=F_{2n+1}-1.}

{displaystyle F_{2n-1}}

{displaystyle F_{2n}}

Um truque diferente pode ser usado para provar

{displaystyle sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}}

F_{n}

{displaystyle F_{n}times F_{n+1}}

{displaystyle F_{n},F_{n-1},...,F_{1}}

Método simbólico

A sequência ${displaystyle (F_{n})_{nin mathbb {N} }}$ também é considerado usando o método simbólico. Mais precisamente, esta sequência corresponde a uma classe combinatória especifiável. A especificação desta sequência é ${displaystyle operatorname {Seq} ({mathcal {Z+Z^{2}}})}$ . De facto, como acima indicado, o $n$ -o número de Fibonacci é igual ao número de composições combinatoriais (partições ordenadas) de $n-1$ usando termos 1 e 2.

Segue-se que a função de geração ordinária da sequência de Fibonacci, ou seja. ${displaystyle sum _{i=0}^{infty }F_{i}z^{i}}$ , é a função complexa ${displaystyle {frac {z}{1-z-z^{2}}}.}$

Provas de indução

As identidades de Fibonacci geralmente podem ser facilmente provadas usando indução matemática.

Por exemplo, reconsidere

{displaystyle sum _{i=1}^{n}F_{i}=F_{n+2}-1.}

{displaystyle F_{n+1}}

{displaystyle sum _{i=1}^{n}F_{i}+F_{n+1}=F_{n+1}+F_{n+2}-1}

e assim temos a fórmula para $n+1$

{displaystyle sum _{i=1}^{n+1}F_{i}=F_{n+3}-1}

Da mesma forma, adicionar ${displaystyle {F_{n+1}}^{2}}$ para ambos os lados de

{displaystyle sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}}

{displaystyle sum _{i=1}^{n}F_{i}^{2}+{F_{n+1}}^{2}=F_{n+1}left(F_{n}+F_{n+1}right)}

{displaystyle sum _{i=1}^{n+1}F_{i}^{2}=F_{n+1}F_{n+2}}

Provas de fórmula Binet

A fórmula de Binet é

{displaystyle {sqrt {5}}F_{n}=varphi ^{n}-psi ^{n}.}

Por exemplo, para provar que ${textstyle sum _{i=1}^{n}F_{i}=F_{n+2}-1}$ note que o lado esquerdo multiplicado por ${displaystyle {sqrt {5}}}$ torna-se

{displaystyle {begin{aligned}1+&varphi +varphi ^{2}+dots +varphi ^{n}-left(1+psi +psi ^{2}+dots +psi ^{n}right)\&={frac {varphi ^{n+1}-1}{varphi -1}}-{frac {psi ^{n+1}-1}{psi -1}}\&={frac {varphi ^{n+1}-1}{-psi }}-{frac {psi ^{n+1}-1}{-varphi }}\&={frac {-varphi ^{n+2}+varphi +psi ^{n+2}-psi }{varphi psi }}\&=varphi ^{n+2}-psi ^{n+2}-(varphi -psi)\&={sqrt {5}}(F_{n+2}-1)\end{aligned}}}

{textstyle varphi psi =-1}

{textstyle varphi -psi ={sqrt {5}}}

Outras identidades

Várias outras identidades podem ser derivadas usando vários métodos. Aqui estão alguns deles:

As identidades de Cassini e catalão

A identidade da Cassini afirma que

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

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

Identidade de D''Ocagne N#39;

{displaystyle F_{m}F_{n+1}-F_{m+1}F_{n}=(-1)^{n}F_{m-n}}

{displaystyle F_{2n}={F_{n+1}}^{2}-{F_{n-1}}^{2}=F_{n}left(F_{n+1}+F_{n-1}right)=F_{n}L_{n}}

L_nnn

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

{displaystyle F_{3n+1}={F_{n+1}}^{3}+3F_{n+1}{F_{n}}^{2}-{F_{n}}^{3}}

{displaystyle F_{3n+2}={F_{n+1}}^{3}+3{F_{n+1}}^{2}F_{n}+{F_{n}}^{3}}

{displaystyle F_{4n}=4F_{n}F_{n+1}left({F_{n+1}}^{2}+2{F_{n}}^{2}right)-3{F_{n}}^{2}left({F_{n}}^{2}+2{F_{n+1}}^{2}right)}

Em geral,

{displaystyle F_{kn+c}=sum _{i=0}^{k}{k choose i}F_{c-i}{F_{n}}^{i}{F_{n+1}}^{k-i}.}

ou alternativamente

{displaystyle F_{kn+c}=sum _{i=0}^{k}{k choose i}F_{c+i}{F_{n}}^{i}{F_{n-1}}^{k-i}.}

Colocando $k = 2$ nesta fórmula, obtém-se novamente as fórmulas do final da seção acima Forma de matriz.

Função geradora

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

{displaystyle s(x)=sum _{k=0}^{infty }F_{k}x^{k}=sum _{k=1}^{infty }F_{k}x^{k}=0+x+x^{2}+2x^{3}+3x^{4}+dots.}

Esta série é convergente para $<math alttext="{displaystyle |x||x|<1φ φ ,|x|<{frac {1}{varphi }},}<img alt="|x|$ e sua soma tem uma forma fechada simples:

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

Isso pode ser provado usando a recorrência de Fibonacci para expandir cada coeficiente na soma infinita:

{displaystyle {begin{aligned}s(x)&=sum _{k=0}^{infty }F_{k}x^{k}\&=F_{0}+F_{1}x+sum _{k=2}^{infty }F_{k}x^{k}\&=0+1x+sum _{k=2}^{infty }F_{k}x^{k}\&=x+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+xsum _{k=2}^{infty }F_{k-1}x^{k-1}+x^{2}sum _{k=2}^{infty }F_{k-2}x^{k-2}\&=x+xsum _{k=1}^{infty }F_{k}x^{k}+x^{2}sum _{k=0}^{infty }F_{k}x^{k}\&=x+xs(x)+x^{2}s(x).end{aligned}}}

Resolvendo a equação

{displaystyle s(x)=x+xs(x)+x^{2}s(x)}

s(x)

A decomposição da fração parcial é dada por

{displaystyle s(x)={frac {1}{sqrt {5}}}left({frac {1}{1-varphi x}}-{frac {1}{1-psi x}}right)}

varphi ={frac {1+{sqrt {5}}}{2}}

{displaystyle psi ={frac {1-{sqrt {5}}}{2}}}

${displaystyle -s!left(-{frac {1}{x}}right)}$ dá a função geradora para os números negafibonacci, e $s(x)$ satisfaz a equação funcional

{displaystyle s(x)=s!left(-{frac {1}{x}}right).}

Somas recíprocas

Somas infinitas sobre números de Fibonacci recíprocos às vezes podem ser avaliadas em termos de funções theta. Por exemplo, a soma de cada número de Fibonacci recíproco indexado ímpar pode ser escrita como

{displaystyle sum _{k=1}^{infty }{frac {1}{F_{2k-1}}}={frac {sqrt {5}}{4}};vartheta _{2}!left(0,{frac {3-{sqrt {5}}}{2}}right)^{2},}

e a soma dos números quadrados recíprocos de Fibonacci como

{displaystyle sum _{k=1}^{infty }{frac {1}{{F_{k}}^{2}}}={frac {5}{24}}!left(vartheta _{2}!left(0,{frac {3-{sqrt {5}}}{2}}right)^{4}-vartheta _{4}!left(0,{frac {3-{sqrt {5}}}{2}}right)^{4}+1right).}

Se somarmos 1 a cada número de Fibonacci na primeira soma, também temos a forma fechada

{displaystyle sum _{k=1}^{infty }{frac {1}{1+F_{2k-1}}}={frac {sqrt {5}}{2}},}

e há uma soma aninhada de números quadrados de Fibonacci dando o recíproco da proporção áurea,

{displaystyle sum _{k=1}^{infty }{frac {(-1)^{k+1}}{sum _{j=1}^{k}{F_{j}}^{2}}}={frac {{sqrt {5}}-1}{2}}.}

A soma de todos os números Fibonacci recíprocos indexados pares é

{displaystyle sum _{k=1}^{infty }{frac {1}{F_{2k}}}={sqrt {5}}left(L(psi ^{2})-L(psi ^{4})right)}

{displaystyle textstyle L(q):=sum _{k=1}^{infty }{frac {q^{k}}{1-q^{k}}},}

{displaystyle textstyle {frac {1}{F_{2k}}}={sqrt {5}}left({frac {psi ^{2k}}{1-psi ^{2k}}}-{frac {psi ^{4k}}{1-psi ^{4k}}}right)!.}

Portanto, a constante recíproca de Fibonacci é

{displaystyle sum _{k=1}^{infty }{frac {1}{F_{k}}}=sum _{k=1}^{infty }{frac {1}{F_{2k-1}}}+sum _{k=1}^{infty }{frac {1}{F_{2k}}}=3.359885666243dots }

Além disso, este número foi provado irracional por Richard André-Jeannin.

série de Millin dá a identidade

{displaystyle sum _{k=0}^{infty }{frac {1}{F_{2^{k}}}}={frac {7-{sqrt {5}}}{2}},}

{displaystyle sum _{k=0}^{N}{frac {1}{F_{2^{k}}}}=3-{frac {F_{2^{N}-1}}{F_{2^{N}}}}.}

Primos e divisibilidade

Propriedades de divisibilidade

Cada terceiro número da sequência é mesmo (um múltiplo de ${displaystyle F_{3}=2}$ ) e, mais geralmente, cada ko número da sequência é um múltiplo de F_k. Assim, a sequência de Fibonacci é um exemplo de uma sequência de divisibilidade. Na verdade, a sequência Fibonacci satisfaz a propriedade de divisibilidade mais forte

{displaystyle gcd(F_{a},F_{b},F_{c},ldots)=F_{gcd(a,b,c,ldots)},}

Gcd

Em particular, quaisquer três números Fibonacci consecutivos são coprime em pares porque ambos $F_{1}=1$ e ${displaystyle F_{2}=1}$ . Isso é,

{displaystyle gcd(F_{n},F_{n+1})=gcd(F_{n},F_{n+2})=gcd(F_{n+1},F_{n+2})=1}

para cada n.

Todo número primo p divide um número de Fibonacci que pode ser determinado pelo valor de p módulo 5. Se p for congruente a 1 ou 4 módulo 5, então p divide F_p−1, e se p é congruente a 2 ou 3 módulo 5, então, p divide F_p+1. O caso restante é que p = 5 e, neste caso, p divide F_p.

{displaystyle {begin{cases}p=5&Rightarrow pmid F_{p},\pequiv pm 1{pmod {5}}&Rightarrow pmid F_{p-1},\pequiv pm 2{pmod {5}}&Rightarrow pmid F_{p+1}.end{cases}}}

Esses casos podem ser combinados em uma única fórmula sem partes, usando o símbolo Legendre:

{displaystyle pmid F_{p;-,left({frac {5}{p}}right)}.}

Teste de primalidade

A fórmula acima pode ser usada como um teste de primalidade no sentido de que se

{displaystyle nmid F_{n;-,left({frac {5}{n}}right)},}

nnnnFibonacci pseudoprimemF_mn

{displaystyle {begin{pmatrix}F_{m+1}&F_{m}\F_{m}&F_{m-1}end{pmatrix}}equiv {begin{pmatrix}1&1\1&0end{pmatrix}}^{m}{pmod {n}}.}

A^m

Primos de Fibonacci

Um Primo de Fibonacci é um número de Fibonacci que é primo. Os primeiros são:

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

Foram encontrados primos de Fibonacci com milhares de dígitos, mas não se sabe se são infinitos.

F_kn é divisível por F_n, portanto, além de F₄ = 3, qualquer primo de Fibonacci deve ter um índice de primos. Como existem execuções arbitrariamente longas de números compostos, também existem execuções arbitrariamente longas de números compostos de Fibonacci.

Nenhum número de Fibonacci maior que F₆ = 8 é um maior ou um 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 as únicas potências perfeitas não triviais.

1, 3, 21 e 55 são os únicos números triangulares de Fibonacci, que foram conjecturados por Vern Hoggatt e provados 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 multiplicado perfeito e nenhuma razão entre dois números de Fibonacci pode ser perfeita.

Divisores primos

Com exceção de 1, 8 e 144 (F₁ = F₂, F₆ e F₁₂) todo número de Fibonacci tem um fator primo que não é fator de nenhum número de Fibonacci menor (Carmichael& #39;teorema). Como resultado, 8 e 144 (F₆ e F₁₂) são os únicos números de Fibonacci que são os produto de outros números de Fibonacci.

A divisibilidade dos números de Fibonacci por um primo p está relacionado com o símbolo Legendre $left({tfrac {p}{5}}right)$ que é avaliado da seguinte forma:

{displaystyle left({frac {p}{5}}right)={begin{cases}0&{text{if }}p=5\1&{text{if }}pequiv pm 1{pmod {5}}\-1&{text{if }}pequiv pm 2{pmod {5}}.end{cases}}}

Se p é um número primo, então

{displaystyle F_{p}equiv left({frac {p}{5}}right){pmod {p}}quad {text{and}}quad F_{p-left({frac {p}{5}}right)}equiv 0{pmod {p}}.}

Por exemplo,

{displaystyle {begin{aligned}({tfrac {2}{5}})&=-1,&F_{3}&=2,&F_{2}&=1,\({tfrac {3}{5}})&=-1,&F_{4}&=3,&F_{3}&=2,\({tfrac {5}{5}})&=0,&F_{5}&=5,\({tfrac {7}{5}})&=-1,&F_{8}&=21,&F_{7}&=13,\({tfrac {11}{5}})&=+1,&F_{10}&=55,&F_{11}&=89.end{aligned}}}

Não se sabe se existe um primo p tal que

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

Tais primos (se houver algum) seriam chamados de primos Wall-Sun-Sun.

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

{displaystyle 5{F_{frac {ppm 1}{2}}}^{2}equiv {begin{cases}{tfrac {1}{2}}left(5left({frac {p}{5}}right)pm 5right){pmod {p}}&{text{if }}pequiv 1{pmod {4}}\{tfrac {1}{2}}left(5left({frac {p}{5}}right)mp 3right){pmod {p}}&{text{if }}pequiv 3{pmod {4}}.end{cases}}}

Exemplo 1. p = 7, neste caso p ≡ 3 (mod 4) e temos:

{displaystyle ({tfrac {7}{5}})=-1:qquad {tfrac {1}{2}}left(5({tfrac {7}{5}})+3right)=-1,quad {tfrac {1}{2}}left(5({tfrac {7}{5}})-3right)=-4.}

{displaystyle F_{3}=2{text{ and }}F_{4}=3.}

{displaystyle 5{F_{3}}^{2}=20equiv -1{pmod {7}};;{text{ and }};;5{F_{4}}^{2}=45equiv -4{pmod {7}}}

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

{displaystyle ({tfrac {11}{5}})=+1:qquad {tfrac {1}{2}}left(5({tfrac {11}{5}})+3right)=4,quad {tfrac {1}{2}}left(5({tfrac {11}{5}})-3right)=1.}

{displaystyle F_{5}=5{text{ and }}F_{6}=8.}

{displaystyle 5{F_{5}}^{2}=125equiv 4{pmod {11}};;{text{ and }};;5{F_{6}}^{2}=320equiv 1{pmod {11}}}

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

{displaystyle ({tfrac {13}{5}})=-1:qquad {tfrac {1}{2}}left(5({tfrac {13}{5}})-5right)=-5,quad {tfrac {1}{2}}left(5({tfrac {13}{5}})+5right)=0.}

{displaystyle F_{6}=8{text{ and }}F_{7}=13.}

{displaystyle 5{F_{6}}^{2}=320equiv -5{pmod {13}};;{text{ and }};;5{F_{7}}^{2}=845equiv 0{pmod {13}}}

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

{displaystyle ({tfrac {29}{5}})=+1:qquad {tfrac {1}{2}}left(5({tfrac {29}{5}})-5right)=0,quad {tfrac {1}{2}}left(5({tfrac {29}{5}})+5right)=5.}

{displaystyle F_{14}=377{text{ and }}F_{15}=610.}

{displaystyle 5{F_{14}}^{2}=710645equiv 0{pmod {29}};;{text{ and }};;5{F_{15}}^{2}=1860500equiv 5{pmod {29}}}

Para n ímpar, todos os divisores primos ímpares de F_n são congruentes a 1 módulo 4, implicando que todos os divisores ímpares de F_n (como produtos de divisores primos ímpares) são congruentes a 1 módulo 4.

Por exemplo,

{displaystyle F_{1}=1, F_{3}=2, F_{5}=5, F_{7}=13, F_{9}=34=2cdot 17, F_{11}=89, F_{13}=233, F_{15}=610=2cdot 5cdot 61.}

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

Periodicidade módulo n

Se os membros da sequência de Fibonacci forem modificados n, a sequência resultante será periódica com período de no máximo 6n. As durações dos períodos para vários n formam os chamados períodos de Pisano. A determinação de uma fórmula geral para os períodos de Pisano é um problema em 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 em particular, o período de Pisano pode ser encontrado como uma instância de detecção de ciclo.

Generalizações

A sequência de Fibonacci é uma das sequências conhecidas mais simples e antigas definidas 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 de negafibonacci.
Generalizando o índice para números reais usando uma modificação da fórmula de Binet.
Começando com outros inteiros. Números de Lucas têm L₁ - 1, L₂ = 3, e L_n = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = L_{n- Sim.} + L_n-2. As sequências Primefree usam a recursão Fibonacci com outros pontos iniciais para gerar sequências em que todos os números são compostos.
Deixar um número ser uma função linear (excepto a soma) dos 2 números anteriores. Os números da Pell têm P_n = 2P_{n- Sim.} + P_n-2. Se o coeficiente do valor precedente for atribuído um valor variável x, o resultado é a sequência de polinômios Fibonacci.
Não adicionar os números imediatamente anteriores. A sequência Padovan e números Perrin têm P(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 sequências resultantes são conhecidas como N-Step Fibonacci números.

Aplicativos

Matemática

Os números de Fibonacci são as somas das diagonais "shallow" (shown in red) do triângulo de Pascal.

Os números de Fibonacci ocorrem nas somas de "raso" diagonais no triângulo de Pascal (ver Coeficiente binomial):

A função geradora pode ser expandida para

{displaystyle {frac {x}{1-x-x^{2}}}=x+x^{2}(1+x)+x^{3}(1+x)^{2}+dots +x^{k+1}(1+x)^{k}+dots =sum limits _{n=0}^{infty }F_{n}x^{n}}

x^{n}

{displaystyle F_{n}=sum _{k=0}^{leftlfloor {frac {n-1}{2}}rightrfloor }{binom {n-k-1}{k}}.}

Para ver como a fórmula é usada, podemos organizar as somas pelo número de termos presentes:

$5$	$= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 1+1+1+1$
	$= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 2+1+1+1$	$= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 1+2+1$	$= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 1+2+1$	$= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 1+1+2$
	$= 2+2+1$	$= 2 + 2$	$= 1+2+2$

que ${displaystyle {binom {5}{0}}+{binom {4}{1}}+{binom {3}{2}}}$ , onde estamos escolhendo as posições de k dois de n- Sim.k-1 termos.

Uso da sequência de Fibonacci para contar {1, 2}-restricted composições

Estes números também dão a solução a certos problemas enumerativos, os mais comuns dos quais é a de contar o número de maneiras de escrever um determinado número $n$ como uma soma ordenada de 1s e 2s (chamadas composições); há $F n + 1$ maneiras de fazer isso (equivalentemente, é também o número de tilings dominó dos $2times n$ retângulo). Por exemplo, há $F 5+1 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = F 6 = 8$ formas de subir uma escadaria de 5 passos, tomando um ou dois passos de cada vez:

$5$	$= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 1+1+1+1$	$= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 2+1+1+1$	$= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 1+2+1$	$= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 1+2+1$	$= 2+2+1$
	$= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 1+1+2$	$= 2 + 2$	$= 1+2+2$

A figura mostra que 8 pode ser decomposto em 5 (o número de maneiras de subir 4 degraus, seguidos de um degrau simples) mais 3 (o número de maneiras de subir 3 degraus, seguidos de um degrau duplo). O mesmo raciocínio é aplicado recursivamente até um único degrau, do qual só há uma maneira de subir.

Os números de Fibonacci podem ser encontrados de diferentes maneiras entre o conjunto de cadeias binárias, ou de forma equivalente, entre os subconjuntos de um determinado conjunto.

O número de cadeias binárias de comprimento $n$ sem consecução $1$ s é o número Fibonacci $F n +$ . Por exemplo, das 16 cadeias binárias de comprimento 4, há $F 6 = 8$ sem consecução $1$ s – eles são 0000, 0001, 0010, 0100, 0101, 1000, 1001, e 1010. Tais strings são as representações binárias de números Fibbinary. Equivalentemente, $F n +$ é o número de subconjuntos $S$ de $(1,... n ?$ sem inteiros consecutivos, isto é, aqueles $S$ para os quais $(Eu..., Eu... + 1} S$ para todos $Eu...$ . Uma bijeção com as somas para n+1 é substituir 1 com 0 e 2 com 10, e soltar o último zero.
O número de cadeias binárias de comprimento $n$ sem um número estranho de consecutivos $1$ s é o número Fibonacci $F n + 1$ . Por exemplo, das 16 cadeias binárias de comprimento 4, há $F 5 = 5$ sem um número estranho de consecutivos $1$ s – eles 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 é substituir 1 com 0 e 2 com 11.
O número de cadeias binárias de comprimento $n$ sem um número par de consecutivos $0$ ou $1$ " $2 F n$ . Por exemplo, das 16 cadeias binárias de comprimento 4, há $2 F 4 = 6$ sem um número par de consecutivos $0$ ou $1$ s – eles são 0001, 0111, 0101, 1000, 1010, 1110. Há uma declaração equivalente sobre subconjuntos.
Yuri Matiyasevich foi capaz de mostrar que os números de Fibonacci podem ser definidos por uma equação Diofantina, o que levou à sua resolução do décimo problema de Hilbert.
Os números de Fibonacci também são um exemplo de uma sequência completa. Isso significa que cada inteiro positivo pode ser escrito como uma soma de números Fibonacci, onde qualquer número é usado uma vez no máximo.
Além disso, cada inteiro positivo pode ser escrito 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 dois números Fibonacci consecutivos. Isso é conhecido como teorema de Zeckendorf, e uma soma de números de Fibonacci que satisfaz essas condições é chamada de representação 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 direito com lados inteiros, ou em outras palavras, o maior número de um triplo pitagórico, obtido a partir da fórmula ${displaystyle (F_{n}F_{n+3})^{2}+(2F_{n+1}F_{n+2})^{2}={F_{2n+3}}^{2}.}$ A sequência de triângulos pitagóricos obtidos a partir desta fórmula tem lados de comprimentos (3,4,5), (5,12,13), (16,30,34), (39,80,89),.... O lado médio de cada um desses triângulos é a soma dos três lados do triângulo precedente.
O cubo de Fibonacci é um grafo não direcionado com um número de nós de Fibonacci que foi proposto como topologia de rede para computação paralela.
Os números de Fibonacci aparecem no lemma do anel, usado para provar conexões entre o teorema da embalagem do círculo e mapas conformais.

Ciência da computação

Árvore de Fibonacci de altura 6. Equilíbrio fatores verdes; alturas vermelhas.
As chaves na coluna esquerda são números de Fibonacci.

Os números de Fibonacci são importantes na análise de tempo de execução computacional do algoritmo de Euclid para determinar o maior divisor comum de dois inteiros: a pior entrada de caso para este algoritmo é um par de números Fibonacci consecutivos.
Os números de Fibonacci são usados em uma versão polifase do algoritmo de tipo de mesclagem em que uma lista não autorizada é dividida em duas listas cujos comprimentos correspondem a números de Fibonacci sequenciais – dividindo a lista de modo que as duas partes tenham comprimentos na proporção aproximada φ. Uma implementação de fita-drive do tipo de mescla de polifase foi descrita em A arte da programação de computador.
Uma árvore de Fibonacci é uma árvore binária cujas árvores de criança (recursivamente) diferem na altura exatamente 1. Então é uma árvore AVL, e uma com os mais poucos nós para uma dada altura — a árvore AVL "thinnest". Estas árvores têm um número de vértices que é um Fibonacci número 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 pseudoaleatórios.
Os números de Fibonacci surgem na análise da estrutura de dados do heap Fibonacci.
Um método de otimização unidimensional, chamado de técnica de pesquisa Fibonacci, usa números Fibonacci.
A série de números Fibonacci é usada para compressão com perda opcional no formato de arquivo de áudio IFF 8SVX usado em computadores Amiga. A série de números acompanha a onda de áudio original semelhante a métodos logarítmicos como μ-law.
Algumas equipes ágeis usam uma série modificada chamada "Modified Fibonacci Series" no planejamento do poker, como uma ferramenta de estimativa. Planning Poker é uma parte formal do Scaled Agile Framework.
Codificação de Fibonacci
Codificação de Negafibonacci

Natureza

Cabeça de camomila amarela mostrando o arranjo em 21 (azul) e 13 (aqua) espirais. Tais arranjos envolvendo números Fibonacci consecutivos aparecem em uma grande variedade de plantas.

Sequências de Fibonacci aparecem em cenários biológicos, como ramificação em árvores, arranjo de folhas em um caule, os frutos de um abacaxi, a floração de uma alcachofra, uma samambaia que se desenrola e o arranjo de uma pinha, e a árvore genealógica de abelhas. Kepler apontou a presença da sequência de Fibonacci na natureza, usando-a para explicar a forma pentagonal (relacionada à proporção áurea) de algumas flores. As margaridas do campo geralmente têm pétalas em contagens de números de Fibonacci. Em 1830, K. F. Schimper e A. Braun descobriram que as parasticias (filotaxia espiral) de plantas eram freqüentemente expressas como frações envolvendo números de Fibonacci.

Przemysław Prusinkiewicz avançou 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.

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 Helmut Vogel [de] em 1979. Tem a forma

{displaystyle theta ={frac {2pi }{varphi ^{2}}}n, r=c{sqrt {n}}}

onde $n$ é o número de índice da florzinha e $c$ é um fator de escala constante; as florzinhas ficam assim na espiral de Fermat. O ângulo de divergência, aproximadamente 137,51°, é o ângulo áureo, dividindo o círculo na proporção áurea. Como essa proporção é irracional, nenhuma florzinha tem um vizinho exatamente no mesmo ângulo do centro, de modo que as florzinhas são compactadas com eficiência. Como as aproximações racionais da proporção áurea são da forma $F (j): F (j + 1)$ , os vizinhos mais próximos do florete número $n$ são aqueles em $n \pm F (j)$ para algum índice $j$ , que depende de $r$ , a distância do centro. Girassóis e flores semelhantes geralmente têm espirais de floretes no sentido horário e anti-horário 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 é colocado por uma fêmea não tratada, ele cria uma abelha macho ou drone.
Se, no entanto, um ovo foi fertilizado por um macho, ele incuba uma fêmea.

Assim, uma abelha macho sempre tem um pai e uma abelha fêmea tem dois. Se alguém traçar o pedigree de qualquer abelha macho (1 abelha), ele tem 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 do sexo feminino, que é $F n -1$ , mais o número de ancestrais masculinos, que é $F n -2$ . Isso está sob a suposição irreal de que os ancestrais em cada nível não são relacionados.

O número de possíveis ancestrais na linha de herança do cromossomo X em uma dada geração ancestral segue a sequência de Fibonacci. (Após Hutchison, L. "Growing the Family Tree: The Power of DNA in Reconstructing Family Relations" (em inglês).

Tem sido notado que o número de possíveis antepassados na linha de herança cromossoma humano X em uma dada geração ancestral também segue a sequência de Fibonacci. Um indivíduo masculino tem um cromossomo X, que recebeu de sua mãe, e um cromossomo Y, que recebeu de seu pai. O macho conta como a "origem" de seu próprio cromossomo X ( $F_{1}=1$ ), e na geração de seus pais, seu cromossomo X veio de um único pai ( $F_{2}=1$ ). A mãe do macho 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. ( ${displaystyle F_{3}=2}$ ). O avô materno recebeu seu cromossomo X de sua mãe, e a avó materna recebeu cromossomas X de ambos os pais, então três avós grandes contribuíram para o cromossomo X do descendente masculino. ( ${displaystyle F_{4}=3}$ ). Cinco grandes avós contribuíram para o cromossomo X do descendente masculino ( ${displaystyle F_{5}=5}$ ), etc. (Isso pressupõe que todos os antepassados de um dado descendente são independentes, mas se alguma genealogia for rastreada muito tempo atrás, os ancestrais começam a aparecer em várias linhas da genealogia, até que eventualmente um fundador da população aparece em todas as linhas da genealogia.)

Outro

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, pode refletir fora de três superfícies: as superfícies superiores, médias e inferiores das duas placas. O número de caminhos de feixe diferentes que têm $k$ reflexões, para $k > 1$ , é o $k$ O número Fibonacci. (No entanto, quando $k = 1$ , há 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 na análise técnica para a negociação de mercado financeiro.
Uma vez que o fator de conversão 1.609344 para milhas a quilômetros é perto da proporção de ouro, a decomposição de distância em milhas em uma soma de números de Fibonacci torna-se quase o quilômetro soma quando os números de Fibonacci são substituídos por seus sucessores. Este método equivale a um número de radix 2 registrado na base de relação dourada φ ser deslocado. Para converter de quilômetros para milhas, mude o registro para baixo a sequência Fibonacci em vez.
Os valores medidos de tensões e correntes no circuito de cadeia resistor infinito (também chamado de escada resistor ou circuito de série infinita-paralelo) seguem a sequência Fibonacci. Os resultados intermediários da adição de séries alternadas e resistências paralelas produzem frações compostas de números Fibonacci consecutivos. A resistência equivalente de todo o circuito é igual à proporção de ouro.
Brasch et al. 2012 mostram como uma sequência de Fibonacci generalizada também pode ser conectada ao campo da economia. Em particular, é mostrado como uma sequência de Fibonacci generalizada entra na função de controle de problemas de otimização dinâmicos de caracteres finitos com uma variável de controle e um estado. O procedimento é ilustrado em um exemplo frequentemente referido como o modelo de crescimento econômico Brock-Mirman.
Mario Merz incluiu a sequência de Fibonacci em algumas de suas obras de arte começando em 1970.
Joseph Schillinger (1895–1943) desenvolveu um sistema de composição que usa intervalos de Fibonacci em algumas de suas melodias; ele viu estes como o contraparte musical da harmonia elaborada evidente dentro da natureza. Veja também Golden ratio § Music.

Contenido relacionado

Más resultados...