Mostrar código-fonte de Sequência de Fibonacci

{{Mais notas|data=março de 2011|ciência=maremática|1=Este artigo ou secção}}
[[Imagem:Yupana 1.png|thumb|350px|direita|''Yupana'' (em [[Língua quíchua|quíchua]], "instrumento de contagem"): calculadora usada pelos  [[incas]], possivelmente baseada nos números de Fibonacci.<ref>[http://www.quipus.it/english/Andean%20Calculators.pdf Andean Calculators]</ref>]]

Na [[matemática]], a '''Sucessão de Fibonacci''' (também '''Sequência de Fibonacci'''), é uma [[Sequência de inteiros|sequência de números inteiros]], começando normalmente por 0 e 1, na qual, cada termo subsequente  corresponde à [[Soma (aritmética)|soma]] dos dois anteriores. A sequência recebeu o nome do matemático italiano [[Leonardo de Pisa]], mais conhecido por Fibonacci, que descreveu, no ano de 1202, o crescimento de uma população de coelhos, a partir desta. Esta sequência já era, no entanto, conhecida na antiguidade.

Os '''números de Fibonacci'''  são, portanto, os números que compõem a seguinte [[sequência (matemática)|sequência]] {{OEIS|A000045}}:
:0,1, '''1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, ...''' .<ref group="nota">Pela convenção moderna a sequência inicial começa por ''F''<sub>0</sub>&nbsp;=&nbsp;0. No livro ''Liber Abaci'' (veja [[#Origens|Seção Origens]]) esta começava com ''F''<sub>1</sub>&nbsp;=&nbsp;1, omitindo-se o zero inicial.</ref><ref>Lista com os 2000 primeiros números da sequência de Fibonacci. <https://oeis.org/A000045/b000045.txt>. Consultado em 09 de maio de 2016</ref>.

Em termos [[matemática|matemáticos]], a sequência é definida [[recursão|recursivamente]] pela fórmula abaixo, sendo o primeiro termo ''F''<sub>1</sub>= 1:

<math display="block">F_n = F_{n-1} + F_{n-2},</math>

e valores iniciais
<math display="block">F_1 = 1,\; F_2 = 1.</math><ref group="nota">Ou, de acordo com a nota: <math>F_0 = 0,\; F_1 = 1.</math> </ref><ref group="nota">Pode ser representada também pela fórmula matemática: <math>
  F(n) =
  \left\{
   \begin{matrix}
    0\,,\qquad\qquad\qquad\quad\,\ \ \,&&\mbox{se }n=0\,;\ \ \\
    1,\qquad\qquad\qquad\qquad\,&&\mbox{se }n=1;\ \ \,\\
    F(n-1)+F(n-2)&&\mbox{outros casos.}
   \end{matrix}
  \right.
 .</math> </ref>

A sequência de Fibonacci tem aplicações na análise de [[mercado financeiro|mercados financeiros]], na [[ciência da computação]] e  na [[teoria dos jogos]]. Também aparece em configurações [[Biologia|biológicas]], como, por exemplo, na disposição dos galhos das árvores ou das [[filotaxia|folhas em uma haste]],<ref name="S. Douady and Y. Couder 1996 255–274">{{citar periódico |autor=S. Douady and Y. Couder |título=Phyllotaxis as a Dynamical Self Organizing Process |periódico=Journal of Theoretical Biology |ano=1996 |número=178 |páginas=255–274 |url=http://www.math.ntnu.no/~jarlet/Douady96.pdf |doi=10.1006/jtbi.1996.0026 |volume=178 |formato=PDF |acessodata=2011-01-20 |arquivourl=https://web.archive.org/web/20060526054108/http://www.math.ntnu.no/~jarlet/Douady96.pdf |arquivodata=2006-05-26 |urlmorta=yes }}</ref> no arranjo do cone da [[alcachofra]], do [[abacaxi]],<ref name="Jones 2006 544">{{citar livro|primeiro =Judy |último =Jones |coautor=William Wilson |título=An Incomplete Education |publicado=Ballantine Books |ano=2006 |isbn=978-0-7394-7582-9 |página=544 |capítulo=Science}}</ref> ou no desenrolar da [[samambaia]].<ref name="A. Brousseau 1969 525–532">{{citar periódico|autor =A. Brousseau |título=Fibonacci Statistics in Conifers |periódico=[[Fibonacci Quarterly]] |ano=1969 |número=7 |páginas= 525–532}}</ref>

== Origens ==
No ocidente, a sequência de Fibonacci apareceu pela primeira vez no livro ''[[Liber Abaci]]'' (1202) de Leonardo Fibonacci,<ref name="Sigler">{{citar livro|título=Fibonacci's Liber Abaci|autor=Sigler, Laurence E. (trad.)|primeiro=|editora=|ano=2002|local=|páginas=|isbn=0-387-95419-8|acessodata=|publicado=Springer-Verlag}} Capítulo II.12, pp. 404–405.</ref> embora ela já tivesse sido descrita por [[Grécia Antiga|gregos]] e [[Índia|indianos]].<ref name="GlobalScience">{{citar livro|título=Toward a Global Science |autor =Susantha Goonatilake |publicado=Indiana University Press |ano=1998 |página=126 |isbn=9780253333889 |url=http://books.google.com/?id=SI5ip95BbgEC&pg=PA126&dq=Virahanka+Fibonacci }}</ref><ref name="HistoriaMathematica">{{citar periódico|primeiro =Parmanand|último =Singh|título=The So-called Fibonacci numbers in ancient and medieval India|periódico=Historia Mathematica|volume=12|número=3|páginas=229–244|ano=1985|doi=10.1016/0315-0860(85)90021-7}}</ref><ref name="Donald Knuth 2006 50">{{citar livro|título=The Art Of Computer Programming, Volume 1 |autor =[[Donald Knuth]] |publicado=Addison Wesley |ano=1968 |isbn=8177587544 |url=http://books.google.com/?id=MooMkK6ERuYC&pg=PA100&dq=knuth+gopala+fibonacci#v=onepage |notes=citação: "Before Fibonacci wrote his work, the sequence Fn had already been discussed by Indian scholars, who had long been interested in rhythmic patterns... both Gopala (before 1135 AD) and Hemachandra (c. 1150) mentioned the numbers 1,2,3,5,8,13,21 explicitly...}}</ref> Fibonacci considerou o crescimento de uma população idealizada (não realista biologicamente) de coelhos. Os números descrevem o número de casais na população de coelhos depois de ''n'' meses se for suposto que:
[[Imagem:FibonacciRabbit.svg|miniaturadaimagem|340px|Ilustração representativa da ''série de Fibonacci'', demonstrando o crescimento populacional de coelhos (carregando ovos de páscoa).]]
* no primeiro mês nasce apenas um casal,
* casais amadurecem sexualmente (e reproduzem-se) apenas após o segundo mês de vida,
* não há problemas genéticos no cruzamento consanguíneo,
* todos os meses, cada casal fértil dá a luz a um novo casal, e
* os coelhos nunca morrem.

Mas genericamente, chama-se sequência de Fibonacci qualquer [[função (matemática)|função]] ''g'' tal que ''g''(''n'' + 2) = ''g''(''n'') + ''g''(''n'' + 1).  Essas funções são precisamente as de formato ''g''(''n'') = ''aF''(''n'') + ''bF''(''n'' + 1) para alguns números ''a'' e ''b'', então as sequências de Fibonacci formam um espaço vetorial com as funções  ''F''(''n'') e ''F''(''n'' + 1) como base.

Em particular, a sequência de Fibonacci com ''F''(1) = 1 e ''F''(2) = 3 é conhecida como a [[sequência de Lucas]]. A importância dos números de [[Édouard Lucas|Lucas]] ''L(n)'' reside no fato deles gerarem a [[Proporção áurea]] para as ''n''-ésimas potências:

<math display="block">\left( \frac 1 2 \left( 1 + \sqrt{5} \right) \right)^n = \frac 1 2 \left( L(n) + F(n) \sqrt{5} \right).</math>

Os números de Lucas se relacionam com os de Fibonacci pela fórmulas:<math display="block">L(n) = F(n-1) + F(n-2).,</math>

<math display="block">F(2n)=F(n)L(n),</math>
<math display="block">\prod_{p=1}^{n}L_{2^p}=F_{2^{n+1}}</math>

e
<math display="block">L(n)=\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n.</math>

Observando-se que <math>(1+\sqrt{5})(1-\sqrt{5})=-4,</math> logo <math>(1-\sqrt{5})=\frac{-4}{1+\sqrt{5}}</math>  e que <math>\left({\frac{1+\sqrt{5}}{2}}\right)^2=1+\left({\frac{1+\sqrt{5}}{2}}\right),</math> pois é a solução de <math>x^2=1+x</math>  e substituindo isso em <math>L(n),</math> obtemos a fórmula apenas em termos da raiz positiva:
<math display="block">L(n)=\frac{\left({1+\left({\frac{1+\sqrt{5})}{2}}\right)}\right)^n+(-1)^n}{{{(\frac{1+\sqrt{5}}{2}})^n}}</math>
Com esta fórmula podemos montar a sequência de Fibonacci e descobrir, por exemplo, quantos coelhos foram gerados no sexto mês, basta aplicar a fórmula descrita acima até chegar ao ponto inicial de 1 e 1, como mostra a figura abaixo:
[[Imagem:FibonacciBlocks.svg|none|Uma grade preenchida com quadrados cujos lados são números de Fibonacci, formando sucessivamente retângulos cada vez maiores e ''tendentes'' à ''razão áurea'']]

Ou seja, no sexto mês foram gerados 8 coelhos.
* F(6) = (F(6 - 1)) + (F(6 - 2))  = 5 e 4 → 8 ( Soma do Resultado de F(5) e F(4) )
* F(5) = (F(5 - 1)) + (F(5 - 2))  = 4 e 3 → 5 ( Soma do Resultado de F(4) e F(3) )
* F(4) = (F(4 - 1)) + (F(4 - 2) ) = 3 e 2 → 3 ( Soma do Resultado de F(3) e F(2) )
* F(3) = (F(3 - 1)) + (F(3 - 2))= 2 e 1 → 2
* F(2) = (F(2 - 1)) + (F(2 - 2)) = 1 e 0 → 1
e a primeira posição 1.

Note que a sequência de Fibonacci esta no resultado de cada posição: 1, 1, 2, 3, 5, 8, ...

== Representações alternativas ==
Para analisar a sequência de Fibonacci (e, em geral, quaisquer sequências) é conveniente obter outras maneiras de representá-la matematicamente.

Observação: os números da sequência também podem ser calculados por:
<math>F_{n+2}=\sqrt{\frac{F_n{F_{n+1}^2}(3{F_n}+4{F_{n+1}})+1}{{F_n}^2+{F_{n+1}}^2}}.</math>

Observe que não é possível reduzir essa expressão à fórmula de recorrência <math>F_{n+2}=F_{n+1}+F_n,</math> apesar de ambas fornecerem o mesmo resultado na sequência de Fibonacci.

=== Função geradora ===
Uma função geradora para uma sequência qualquer <math>a_0,a_1,a_2,\dots</math> é a função
<math display="block">f(x) = a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+\cdots,</math>
ou seja, uma [[série potências formais]] em que cada coeficiente é um elemento da sequência. Os números de Fibonacci possuem a seguinte função geradora
<math display="block">f\left(x\right)=\frac{x}{1-x-x^2}.</math>

Quando se expande esta função em potências de <math>x,</math> os coeficientes são justamente os termos da sequência de Fibonacci:
<math display="block">\frac{x}{1-x-x^2}=0x^0+1x^1+1x^2+2x^3+3x^4+5x^5+8x^6+13x^7+\cdots</math>

=== Fórmula explícita ===
Conforme mencionado por [[Johannes Kepler]], a taxa de crescimento dos números de Fibonacci, que é <math display="inline">F_{n+1}/F_n,</math> tende à [[Proporção áurea]], denotada por <math display="inline">\phi</math> <math display="inline">\phi = \frac{1+\sqrt{5}}{2} \approx 1,61803398875.</math> Em outras palavras, <math>\lim_{n \to \infty}\left(\frac{F_{n+1}}{F_n}\right)=\phi=\frac{1+\sqrt{5}}{2}=1,61803398875.</math> (De um modo mais geral, <math>\lim_{n \to \infty}\left(\frac{F_{n+k}}{F_n}\right)={\phi}^k.</math> )  Esta é a raiz positiva da equação de segundo grau ''x''²&nbsp;−&nbsp;''x''&nbsp;−&nbsp;1&nbsp;=&nbsp;0, então φ²&nbsp;=&nbsp;φ&nbsp;+&nbsp;1. Se multiplicarmos ambos os lados por φ<sup>''n''</sup>, teremos φ<sup>''n''+2</sup>&nbsp;=&nbsp;φ<sup>''n''+1</sup>&nbsp;+&nbsp;φ<sup>''n''</sup>, então a função φ<sup>''n''</sup> é uma sequência de Fibonacci. É possível demonstrar que a raiz negativa da mesma equação, 1&nbsp;−&nbsp;φ, tem as mesmas propriedades, então as duas funções φ<sup>''n''</sup> e (1&nbsp;−&nbsp;φ)<sup>''n''</sup> formam outra base para o espaço.

Ajustando os coeficientes para obter os valores iniciais adequados ''F''(0)&nbsp;=&nbsp;0 e ''F''(1)&nbsp;=&nbsp;1, tem-se a [[fórmula de Binet]]:
<math display="block">F\left(n\right) =  \frac{1}{\sqrt{5}}\left\{ \left ( \frac{1+\sqrt{5}}{2} \right )^n - \left ( \frac{1-\sqrt{5}}{2} \right )^n \right \} = {\phi^n \over \sqrt{5}} - {(1-\phi)^n \over \sqrt{5}}.</math>

Este resultado também pode ser derivado utilizando-se a técnica de funções geradoras, ou a técnica de resolver relações de recorrência.

Quando ''n'' tende a infinito, o segundo termo tende a zero, e os números de Fibonacci tendem à exponencial φ<sup>''n''</sup>/√5. O segundo termo já começa pequeno o suficiente para que os números de Fibonacci possam ser obtidos usando somente o primeiro termo arredondado para o inteiro mais próximo.

====Fórmula de Binet e o Binômio de Newton====
Se expandirmos a Fórmula de Binet usando o [[Binômio de Newton]], é possível também escrevê-la em termos [[Número racional|racionais]], ou seja, nessa forma:
:a) Se <math>n</math> for ímpar:
<math display="block">F(n)=\frac{ \displaystyle\sum_{p=0}^{(n-1)/2}{n\choose 2p+1}5^p }{2^{n-1}}</math>

:b) Se <math>n</math> for par:

<math display="block"> F(n)=\frac{ \displaystyle\sum_{p=0}^{(n-2)/2}{n\choose 2p+1}5^p }{2^{n-1}}</math>

:Ou ainda, de modo equivalente:
<math display="block"> F(n)=\frac{ \displaystyle\sum_{p=0}^{\lfloor (n-1)/2 \rfloor}{n\choose 2p+1}5^p }{2^{n-1}},</math> onde <math>\lfloor (n-1)/2 \rfloor</math> representa a parte inteira de (n-1)/2.

====Função inversa da fórmula de Binet====
Para resolver o problema inverso, ou seja, qual a posição que um dado número de Fibonacci ocupa na sequência, existe a [[função inversa]] da fórmula de Binet:<ref>''Mathematics - "How can I find an inverse to the Binet formula?"''. <http://math.stackexchange.com/questions/374758/how-can-i-find-an-inverse-to-the-binet-formula>. Consultado em 09 de maio de 2016.</ref>.

1) O número dado é um número de Fibonacci se <math>\sqrt{5{{F_n}^2}\pm 4}</math> for um número inteiro e positivo. Como ainda não sabemos o valor de <math>n,</math> (temos apenas o número que desejamos calcular: o suposto <math>F_n</math>), há que se testar inicialmente as duas possibilidades. Se <math>n</math> for ímpar, então <math>\sqrt{5{{F_n}^2}- 4}</math> será inteiro, e se <math>n</math> for par, então <math>\sqrt{5{{F_n}^2}+ 4}</math> será inteiro.

2) A posição que esse número ocupa na sequência é calculada por:
<math display="block">\lfloor n \rfloor=\log_{\left(\frac{1+{\sqrt{5}}}{2}\right)}{\left({\frac{{F_n}{\sqrt{5}}+{\sqrt{5{{F_n}^2}+4{(-1)}^{n}}}}{2}}\right)}.</math>
Onde <math>\lfloor n \rfloor</math> representa a parte inteira de <math>n.</math>

Exemplos:

1) Dado o número 1597, verifique se ele pertence à sequência de Fibonacci e, em caso afirmativo, determine a sua posição na sequência.
Verificamos que  <math>\sqrt{5(1597)^2- 4}= \sqrt{12752041}=3571</math> é inteiro, o que indica que ele pertence à sequência e <math>n</math> neste caso é ímpar.

Aplicando-se a função inversa da fórmula de Binet para <math>F_n=1597:</math>
<math display="block">\lfloor n \rfloor=\log_{\left(\frac{1+{\sqrt{5}}}{2}\right)}{\left({\frac{{F_n}{\sqrt{5}}+{\sqrt{5{{F_n}^2}+4{(-1)}^{n}}}}{2}}\right)}</math>

<math display="block">\lfloor n \rfloor=\log_{\left(\frac{1+{\sqrt{5}}}{2}\right)}{\left({\frac{{1597}{\sqrt{5}}+{\sqrt{5{(1597)^2}+4{(-1)}^{n}}}}{2}}\right)}</math>

Lembrando que <math>(-1)</math> elevado a qualquer número ímpar sempre resulta <math>(-1).</math> Logo:

<math>\lfloor n \rfloor=17,</math> o que significa que 1597 é o 17° número da sequência de Fibonacci. De fato:
<math display="block">1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, {\color{blue}1597} \cdots</math>

2) Verifique se o número <math >2016</math> pertence ou não à sequência de Fibonacci.

Neste caso, nem <math>\sqrt{5{(2016)^2}+4}</math> e nem <math>\sqrt{5{(2016)^2}- 4}</math> são números inteiros, o que indica que <math>2016</math> não é um número de Fibonacci.

De fato, <math>F_{17}=1597</math> e <math>F_{18}=2584>2016.</math>

=== Forma matricial ===
Para argumentos muito grandes, quando utiliza-se um computador [[bignum]], é mais fácil{{Carece de fontes|ciência=sim|data=fevereiro de 2014}} calcular os números de Fibonacci usando a seguinte equação matricial:
<math display="block">\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n =
       \begin{bmatrix} F\left(n+1\right) & F \left(n\right) \\
                       F\left(n\right)   & F \left(n-1\right) \end{bmatrix},
</math>
em que a potência de ''n'' é calculada através do produto matricial repetidas vezes.

Um exemplo de aplicação desta expressão matricial é na demonstração do [[teorema de Lamé]] sobre o [[algoritmo de Euclides]] para o cálculo do [[MDC]].<ref group="nota">Veja por exemplo o capítulo sobre o [[b:Teoria de números/Máximo divisor comum|máximo divisor comum]] do [[Wikilivros|wikilivro]] de [[b:Teoria de números|Teoria de números]].</ref>

[[Imagem:Fibonacci molle.JPG|thumb|Representação da Série de Fibonacci na Molle Antonelliana em Turim, Itália.]]

== Tipos de algoritmos ==
Há diversos [[algoritmo]]s (métodos) para calcular o <math>n</math>-ésimo elemento da sequência de Fibonacci, sendo que os mais comuns empregam um das seguintes abordagens:
* Recursiva
* Iterativa
* Dividir para conquistar

A seguir é apresentado um exemplo de cada um destes tipos de algoritmos em [[pseudocódigo]].

=== Abordagem recursiva ===
A própria definição da sequência de Fibonacci pode ser tomada como base para implementar um [[algoritmo recursivo]] que gera os termos da sequência, como é mostrado a seguir:

'''função''' <math>{\it fib}(n)</math>
:'''se''' <math>n<2</math> '''então'''
::'''retorne''' <math>n</math>
:'''caso contrário'''
::'''retorne''' <math>{\it fib}(n-1) + {\it fib}(n-2)</math>

Apesar de simples, essa estratégia não é recomendável porque os mesmos valores são calculados muitas vezes (a não ser que a [[linguagem de programação]] guarde automaticamente os valores calculados nas chamadas anteriores da mesma função com o mesmo argumento). Uma análise cuidadosa mostra que a complexidade computacional do algoritmo é <math>O(\varphi^n).</math> Por esse motivo, normalmente calcula-se os números de Fibonacci "de baixo para cima",{{Carece de fontes|ciência=sim|data=fevereiro de 2014}} começando com os dois valores 0 e 1, e depois repetidamente substituindo-se o primeiro número pelo segundo, e o segundo número pela soma dos dois anteriores.

Uma outra alternativa é fazer uso da fórmula apresentada na seção anterior, que envolve potências da [[proporção áurea]]. No entanto, isso pode não ser muito conveniente para valores grandes de ''n'', já que os erros de arredondamento se acumulam e a precisão dos números de [[ponto flutuante]] normalmente não será suficiente.

=== Abordagem iterativa ===
Com o uso de um algoritmo iterativo como o que é mostrado a seguir, é possível obter a sequência um pouco mais eficientemente:

'''função''' <math>{\it fib}(n)</math>
<math display="block">j\gets 1</math>
<math display="block">i\gets 0</math>

:'''para''' <math>k</math> de <math>1</math> até <math>n</math> '''faça'''
:<math display="block">t\gets i+j</math>
:<math display="block">i\gets j</math>
:<math display="block">j\gets t</math>
:'''retorne''' <math>j</math>

Neste caso, a complexidade computacional do algoritmo é <math>O(n).</math>

=== Abordagem dividir para conquistar ===
O algoritmo abaixo é bem mais eficiente e baseia-se na representação matricial da sequência de Fibonacci. Sua complexidade computacional é <math>O(\log(n)).</math>

'''função''' <math>{\it fib}(n)</math>
:'''se''' <math>n\leq0</math> '''então'''
::'''retorne''' <math>0</math>
<math display="block">i\gets n-1</math>
<math display="block">a \gets 1</math>
<math display="block">b \gets 0</math>
<math display="block">c \gets 0</math>
<math display="block">d \gets 1</math>
<math display="block">aux1 \gets 0</math>
<math display="block">aux2 \gets 0</math>
:'''enquanto''' <math>i > 0</math> '''faça'''
::'''se''' <math>i</math> é impar '''então'''
::<math display="block">aux1 \gets db + ca</math>
::<math display="block">aux2 \gets d(b + a) + cb</math>
::<math display="block">a \gets aux1</math>
::<math display="block">b \gets aux2</math>
:<math display="block">aux1 \gets c^2 + d^2</math>
:<math display="block">aux2 \gets d(2c + d)</math>
:<math display="block">c \gets aux1</math>
:<math display="block">d \gets aux2</math>
:<math display="block">i\gets i\div 2</math>
:'''retorne''' <math>a+b</math>

== Aplicações ==
Os números de Fibonacci são importantes para a análise em tempo real do [[algoritmo de Euclides|algoritmo euclidiano]], para determinar o [[máximo divisor comum]] de dois [[números inteiros]].

Matiyasevich mostrou que os números de Fibonacci podem ser definidos por uma [[Equação diofantina]], o que o levou à solução original do [[Teorema de Matiyasevichs|Décimo Problema de Hilbert]].

Os números de Fibonacci aparecem na fórmula das diagonais de um [[triângulo de Pascal]] (veja [[coeficiente binomial]]).

Um uso interessante da sequência de Fibonacci é na conversão de [[milha]]s para [[quilômetro]]s. Por exemplo, para saber aproximadamente a quantos quilômetros 5 milhas correspondem, pega-se o número de Fibonacci correspondendo ao número de milhas (5) e olha-se para o número seguinte (8). 5 milhas são aproximadamente 8 quilômetros. Esse método funciona porque, por coincidência, o fator de conversão entre milhas e quilômetros (1.609) é próximo de φ (1.618) (obviamente ele só é útil para aproximações bem grosseiras: além do factor de conversão ser diferente de φ, a série ''converge'' para φ).

[[Imagem:Fibonacci.ogg|thumb|Exemplo de sons Fibonacci]]

Em [[música]] os números de Fibonacci são utilizados para a afinação, tal como nas artes visuais, determinar proporções entre elementos formais. Um exemplo é a ''Música para Cordas, Percussão e Celesta'' de [[Béla Bartók]].

[[Le Corbusier]] usou a sequência de Fibonacci na construção do seu [[modulor]], um sistema de proporções baseadas no corpo humano e aplicadas ao projeto de [[arquitectura|arquitetura]].

Em [[The Wave Principal]], [[Ralph Nelson Elliot]] defende a ideia que as flutuações do mercado seguem um padrão de crescimento e decrescimento que pode ser analisado segundo os números de Fibonacci, uma vez determinada a escala de observação. Defende que as relações entre picos e vales do gráfico da flutuação de bolsa tendem a seguir razões numéricas aproximadas das razões de dois números consecutivos da sequência de Fibonacci.

[[Imagem:fib bolsa 1.jpg]]

Teorias mais recentes, defendem que é possível encontrar relações “de ouro” entre os pontos de pico e os de vale, como no gráfico abaixo:

[[Imagem:fib bolsa 2.jpg]]

Se tomarmos o valor entre o início do ciclo e o primeiro pico, e o compararmos com o valor entre este pico e o pico máximo, encontraremos também o número de ouro. O ciclo, naturalmente, pode estar invertido, e os momentos de pico podem se tornar momentos de vale, e vice-versa.


== Generalizações ==
Uma generalização da sequência de Fibonacci são as [[Sequência de Lucas|sequências de Lucas]]. Um tipo pode ser definido por:

<math display="block">U(0) = 0</math>
<math display="block">U(1) = 1</math>
<math display="block">U(n+2) = PU(n+1) - QU(n)</math>

onde a sequência normal de Fibonacci é o caso especial de <math>P = 1</math> e <math>Q = -1.</math> Outro tipo de sequência de Lucas começa com <math>V(0) = 2,</math> <math>V(1) = P.</math> Tais sequências têm aplicações na Teoria de Números e na prova que um dado número é primo (primalidade).

Os polinômios de Fibonacci são outra generalização dos números de Fibonacci.

== Identidades ==
*<math>\sum_{p=1}^{n}{F_n}^2=F_nF_{n+1}</math>

*<math>\sum_{p=1}^{n}{F_{2p}}=F_{2n+1}-1</math>

*<math>\sum_{p=1}^{n}{F_{2p-1}}=F_{2n}</math>

*<math>\sum_{p=1}^{2n}{F_{p}}=F_{2n+2}-1</math><ref>Propriedades matemáticas dos números de Fibonacci. <http://pessoal.sercomtel.com.br/matematica/alegria/fibonacci/seqfib1.htm {{Wayback|url=http://pessoal.sercomtel.com.br/matematica/alegria/fibonacci/seqfib1.htm |date=20160504213652 }}>. Consultado em 06 de maio de 2016.</ref>

*<math>\sum_{p=0}^{\lfloor n/2\rfloor}{n-p\choose p}=F_{n+1},</math> onde <math>\lfloor n/2\rfloor</math> denota a parte inteira de n/2.<ref>Wolfram MathWorld: Pascal's Triangle. <http://mathworld.wolfram.com/PascalsTriangle.html>. Consultado em 06 de maio de 2016.</ref>.

*<math>\sum_{p=1}^{n}{\frac{F_{p+1}}{F_{p+2}.F_{p+3}}}=\frac{F_{n+3}-2}{2F_{n+3}}.</math>

*<math>\sum_{p=1}^{n}{F_{4p}}=\sum_{p=1}^{2n}{F_pF_{p+1}}={F^{2}}_{2n+1}-1</math>

*<math>\sum_{p=0}^{n}{f_n}^3=\frac{f_{3n+4}+6(-1)^nf_{n-1}+5}{10}.</math> (Onde <math>f_n=F_{n+1})</math><ref>Sumofcubes.pdf. <https://www.math.hmc.edu/~benjamin/papers/sumfibocubes.pdf>. Acessado em 04 de maio de 2016.</ref>

*<math>F_nF_{n+1}-F_nF_{n-1}=F_n^{2}</math>
*<math>\sum_{k=0}^\infty \frac{1}{1+F_{2k+1}} = \frac{\sqrt{5}}{2},</math>
*<math>\sum_{k=1}^\infty \frac{(-1)^{k+1}}{\sum_{j=1}^k {F_{j}}^2} = \frac{\sqrt{5}-1}{2}.</math>
*<math>\psi = \sum_{k=1}^{\infty} \frac{1}{F_k} = 3.359885666243 \dots</math>
*<math>\sum_{n=0}^{\infty} \frac{1}{F_{2^n}} = \frac{7 - \sqrt{5}}{2}\,,</math>
*<math>\sum_{n=0}^N \frac{1}{F_{2^n}} = 3 - \frac{F_{2^N-1}}{F_{2^N}}.</math>
*<math>{F_n}^2+{F_{n+1}}^2=F_{2n+1}</math>
Além disso, <math>F_{n+2}=\sqrt{\frac{F_n{F_{n+1}^2}(3{F_n}+4{F_{n+1}})+1}{{F_n}^2+{F_{n+1}}^2}}</math>

*<math>F_nF_{n+2}+F_{n+1}F_{n+3}=F_{n+2}F_{n+3}-F_{n+1}F_n</math>
* <math>F_{n+2}=F_{n+1}+F_{n}</math> (da definição)
* <math>\sum_{n=1}^NF_{n}=F_{N+2}-1 </math> (usando a identidade telescópica)
* <math>\sum_{n=1}^NnF_{n}= NF_{N + 2} - F_{N+ 3}+2</math>
Esta fórmula pode ser provada por indução. Para <math> N=1 </math> é evidente. Supondo o resultado certo para <math> N\geq 1 </math>
<math display="block">\sum_{n=1}^{N+1}nF_{n}= \sum_{n=1}^{N}nF_{n}+(N+1) F_{N+1}</math>
<math display="block">=NF_{N + 2} - F_{N+ 3}+2+(N+1) F_{N+1}</math>
<math display="block">=NF_{N + 3} - F_{N+ 3}+2+ F_{N+1}</math>
<math display="block">=NF_{N + 3} - F_{N+ 3}+2+ F_{N+1}</math>
<math display="block">=NF_{N + 3} - F_{N+ 2}+2=  NF_{N + 3} - (F_{N+ 4}-F_{N+3})+2  </math>
<math display="block">=NF_{N+2}+2-F_{N+3}</math>
Ou heuristicamente
<math display="block">\sum_{n=1}^{N}nF_{n}= \sum_{n=1}^{N}n(F_{n+2}-F_{n+1})</math>
<math display="block">= \sum_{n=1}^{N}(nF_{n+2}-nF_{n+1})</math>
<math display="block">=\sum_{n=1}^{N}((n+2-2)F_{n+2}-(n+1-1)F_{n+1})</math>
<math display="block">=\sum_{n=1}^{N}((n+2)F_{n+2}-(n+1)F_{n+1})-\sum_{n=1}^{N}(2F_{n+2}-F_{n+1})</math>
<math display="block">=(N+2)F_{N+2}-2F_{2}-\sum_{n=1}^{N}(F_{n+2}+F_{n})</math>
<math display="block">=(N+2)F_{N+2}-2-(F_{N+4}-1-F_1-F_2+      F_{N+2}-1 )</math>
<math display="block">=(N+1)F_{N+2}+2-(F_{N+4})</math>
<math display="block">=NF_{N+2}+-(F_{N+4}-F_{N+2})</math>
<math display="block">=NF_{N+2}+2-F_{N+3}</math>

==Outras propriedades==
1) Considerando-se os inteiros positivos <math>a \ge 1</math> e <math>b \ge 1,</math> então :
<math display="block">F_{b+a}=F_{b-1}F_a+F_bF_{a+1}</math>
Prova:
:Para <math>a=1:</math>
<math display="block">F_{b+1}=F_{b-1}+F_{b}</math>
:Para <math>a=2</math>
<math display="block">F_{b+2}=F_{b}+ F_{b+1}</math>
:Supondo para todo <math>b>1,</math> com <math>q>k\ge2,</math> e usando-se o princípio da [[Indução matemática|Indução Matemática]],
<math display="block">F_{b+(q-2)}=F_{b-1}F_{q-2}+F_{b}F_{q-1}</math>
<math display="block">F_{b+(q-1)}=F_{b-1}F_{q-1}+F_{b}F_{q}</math>
:Somando-se membro a membro e considerando a fórmula recursiva,
<math display="block">F_{b+q}=F_{b-1}F_{q}+F_{b}F_{q+1}</math>
Isso vale também para <math>q.</math> Logo, fazendo-se a substituição:
<math display="block">F_{b+a}=F_{b-1}F_a+F_bF_{a+1}</math>

:2) Se <math>b</math> é divisível por <math>a,</math> então <math>F_{b}</math> é divisível por <math>F_{a}</math>
:Prova: <math>b=aq</math> para algum <math>q</math> inteiro não negativo. Hipótese de indução: <math>q \ge 1</math> e <math>F_{aq}</math> é divisível por <math>F_{a}.</math>
:Pela propriedade 1, citada acima:
<math display="block">F_{a(q+1)}=F_{aq+a}=F_{aq-1}F_{a}+F_{aq}F_{a+1}.</math>
:Como <math>F_{aq-1}F_{a}</math> e <math>F_{aq}F_{a+1}</math> são divisíveis por <math>F_{a},</math> pela hipótese de indução, então
<math display="block">F_{a}</math> divide a soma desses dois produtos, quer dizer:
<math display="block">F_{a(q+1)}</math> é divisível por <math>F_{a}</math>

:3) Se <math>c</math> é o [[máximo divisor comum]] (''mdc'') de <math>a</math> e <math>b,</math> então o máximo divisor comum de <math>F_{a}</math> e <math>F_{b}</math> é igual a <math>F_{c}.</math>
:Prova:
:Se <math>a=1,</math> o ''mdc'' é 1 e ''mdc'' de <math>F_{a}</math> e <math>F_{b}</math> é <math>F_{1}.</math> Se <math>a=b</math> não há o que provar.
:Se <math>a</math> é maior ou igual a <math>2</math> e menor que <math>b,</math>
<math display="block">F_{b}=F_{a+(b-a)}=F_{a-1}F_{b-a}+F_{a}F_{b-a+1}.</math> Consequentemente, o máximo divisor comum de <math>F_{a}</math> e <math>F_{b}</math> é igual ao ''mdc'' de <math>F_{a}</math> e <math>F_{a-1}F_{b-a},</math> ou seja, de <math>F_{a}</math> e <math>F_{b-a}.</math>
:Pela hipótese de indução:
<math display="block">F_{mdc(a, b-a)}=F_{mdc(a,b)}</math>

4) (Teorema de Zeckendorf).<ref>[http://Zeckendorf%20representation Representação de Zeckendorf]{{Ligação inativa|data=agosto de 2019}}. Encyclopedia of Mathematics (em inglês). Consultado em 02 de maio de 2016</ref> "Todo número inteiro positivo pode ser representado unicamente como a soma de números de Fibonacci de índices não consecutivos e maiores que 1."

5) Definindo <math>A_n=\sqrt{{F_n}^2+{F_{n+2}}^2},</math> os números <math>A_n,</math> <math>A_{n+1}</math> e <math>A_{n+2}</math> são as medidas de comprimento dos lados de um triângulo cuja área é <math>\frac{1}{2}</math> unidade.

== Número Tribonacci ==
Um '''número Tribonacci''' assemelha-se a um número de Fibonacci, mas em vez de começarmos com dois termos pré-definidos, a sequência é iniciada com três termos pré-determinados, e cada termo posterior é a soma dos três termos precedentes. Os primeiros números de uma pequena sequência Tribonacci são:
1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, etc.<ref>[http://www.research.att.com/projects/OEIS?Anum=A000073 A000073] [[OEIS]]</ref>

===Forma explícita dos números de Tribonacci<ref>Wolfram MathWorld <http://mathworld.wolfram.com/TribonacciNumber.html>.Acessado{{Ligação inativa|data=agosto de 2019}} em 04 de maio de 2016.</ref>===
De modo semelhante à sequência de Fibonacci, é possível obter a forma explícita de um número Tribonacci  <math>(T_n):</math>
<math display="block">T_1=T_2=1</math> e <math>T_3=2</math> e

<math display="block">T_n=T_{n-1}+T_{n-2}+T_{n-3}</math>
Sendo <math>\alpha,</math> <math>\beta</math> e <math>\gamma</math> as soluções da equação:
<math display="block">x^3-x^2-x-1=0.</math>

Então:
<math display="block">T_n=\frac{\alpha^{n+1}}{(\alpha-\beta)(\alpha-\gamma)}+\frac{\beta^{n+1}}{(\beta-\alpha)(\beta-\gamma)}+\frac{\gamma^{n+1}}{(\gamma-\alpha)(\gamma-\beta)}</math>

<math display="block">T_n=\frac{\alpha^{n}}{-{\alpha}^2+4{\alpha}-1}+\frac{\beta^{n}}{-{\beta}^2+4{\beta}-1}+\frac{\gamma^{n}}{-{\gamma}^2+4{\gamma}-1}</math>

===Função geradora===

<math display="block">\frac{x}{1-x-x^2-x^3}=1+x+2x^2+4x^3+7x^4+13x^5+24x^6+44x^7+81x^8+149x^9+...</math>
==Sequências recursivas semelhantes à de Fibonacci de modo geral==

De modo semelhante aos resultados obtidos sobre a sequência de Fibonacci apresentados acima, é possível descobrir, por raciocínios semelhantes, propriedades de sequências da forma <math>A_n=aA_{n-1}+bA_{n-2},</math> onde <math>a</math> e <math>b</math> são números reais.


Tomemos, como exemplo, a sequência definida recursivamente por <math>A_n=2A_{n-1}+A_{n-2}</math>  com <math>A_1=A_2=1.</math>

É a sequência <math>(1,1,3,7,17,41,99,239,577,...)</math>

De modo semelhante à sequência de Fibonacci, ao dividirmos um de seus termos pelo seu antecessor, o resultado também tenderá a um número real, só que neste caso é <math>(1+\sqrt{2})=2,41421356237309...</math>  Ou seja,

<math>\lim_{n \to \infty}\left(\frac{A_{n}}{A_{n-1}}\right)=1+\sqrt{2}=2,41421356237309....</math>

A propósito, o número <math>{1 + \sqrt{2}}</math> é conhecido como "Razão de prata" ou "Silver ratio"

Também é possível obter fórmulas explícitas para calcular cada termo <math>A_n</math> em função de <math>n,</math> neste caso o resultado é cada vez mais preciso à medida que <math>n</math> aumenta, até que a partir de <math>n=21</math> o resultado é exato. As fórmulas explícitas dessa sequência são:
<math display="block">A_n=\frac{{(1+\sqrt{2})}^n+{(1-\sqrt{2})}^n}{2{(1+\sqrt{2})}}</math>

e

<math display="block">A_n=\frac{{(1+\sqrt{2})}^n-{(1-\sqrt{2})}^n}{2{(1+\sqrt{2})}}.</math>

A tabela a seguir mostra os resultados para os 22 primeiros números dessa sequência:
{| class="wikitable"
! <math>n</math>
! <math>A_n</math>
(pela fórmula recursiva)
! <math>\frac{{(1+\sqrt{2})}^n+{(1-\sqrt{2})}^n}{2{(1+\sqrt{2})}}</math>
!<math>\frac{{(1+\sqrt{2})}^n-{(1-\sqrt{2})}^n}{2{(1+\sqrt{2})}}</math>
!<math>\frac{A_n}{A_{n-1}}</math>
|-
| 1 || 1 || 0,414213562373095 || 0,585786437626905 || <math>-</math>
|-
| 2 || 1 || 1,24264068711929 || 1,17157287525381 || 1
|-
| 3 || 3 || 2,89949493661166 || 2,92893218813452 || 3
|-
| 4 || 7 || 7,04163056034261 || 7,02943725152286 || 2,33333333333333
|-
| 5 || 17 || 16,9827560572969 || 16,9878066911802 || 2,42857142857143
|-
| 6 || 41 || 41,0071426749364 || 41,0050506338833 || 2,41176470588235
|-
| 7 || 99 || 98,9970414071697 || 98,9979079589469 || 2,41463414634146
|-
| 8 || 239 || 239,001225489276 || 239,000866551777 || 2,41414141414141
|-
| 9 || 577 || 576,999492385721 || 576,999641062501 || 2,41422594142259
|-
| 10 || 1393 || 1393,00021026072 || 1393,00014867678 || 2,41421143847487
|-
| 11 || 3363 || 3362,99991290716 || 3362,99993841606 || 2,41421392677674
|-
| 12 || 8119 || 8119,00003607503 || 8119,0000255089 || 2,41421349985132
|-
| 13 || 19601 || 19600,9999850572 || 19600,9999894339 || 2,41421357310014
|-
| 14 || 47321 || 47321,0000061895 || 47321,0000043766 || 2,41421356053263
|-
| 15 || 114243 || 114242,999997436 || 114242,999998187 || 2,41421356268887
|-
| 16 || 275807 || 275807,000001062 || 275807,000000751 || 2,41421356231892
|-
| 17 || 665857 || 665856,99999956 || 665856,999999688 || 2,41421356238239
|-
| 18 || 1607521 || 1607521,00000018 || 1607521,00000013 || 2,4142135623715
|-
| 19 || 3880899 || 3880898,99999992 || 3880898,99999994 || 2,41421356237337
|-
| 20 || 9369319 || 9369319,00000002 || 9369319,00000001 || 2,41421356237305
|-
| 21 || 22619537 || 22619537 || 22619537 || 2,4142135623731
|-
| 22 || 54608393 || 54608393 || 54608393 || 2,41421356237309
|-
| <math>\cdots</math> || <math>\cdots</math> || <math>\cdots</math> || <math>\cdots</math> || <math>\cdots</math>
|-
| <math>\infty</math>
| <math>A_n</math>
| <math>A_n</math>
| <math>A_n</math>
| <math>1+\sqrt{2}</math>
|}

Perceba, por exemplo, que nessa sequência é válido que:

<math display="block">{A_n}^2+{A_{n+1}}^2=A_{2n+1}-A_{2n}.</math>


Outro exemplo, seja a sequência definida por <math>B_{n+2}=B_{n+1}+B_n,</math> com <math>B_1=a</math> e <math>B_2=b,</math> onde <math>a</math> e <math>b</math> são números reais. Sendo <math>F_n</math> o n-ésimo termo da sequência de Fibonacci, então

<math>B_n=F_n{\left(a{\phi}^{-2}+b{\phi}^{-1}\right)},</math> onde <math>\phi=\left(\frac{1+\sqrt{5}}{2}\right).</math>

== A Sequência de Fibonacci na natureza ==
A sequência de Fibonacci está intrinsecamente ligada à natureza. Estes números são facilmente encontrados no arranjo de folhas do ramo de uma planta, em copas das árvores ou até mesmo no número de pétalas das flores.

As sementes das flores, frutos e, de forma particularmente interessante, as pinhas, trazem no seu escopo natural esta sequência. Como esta proporção trata-se de uma sucessão numérica, é possível perceber, em vários traços notáveis, a manifestação desta em muitos aspectos da natureza de maneira estética e funcional. Tal linha de análise é, muitas vezes, utilizada como base explicativa para a teoria criacionista denominada [[Design Inteligente]].

=== Nautilus ===
[[Imagem:NautilusCutawayLogarithmicSpiral-withGoldenSpiral.jpg|thumb|A Sequencia Fibonacci no Nautilus.|150px]]
Na espiral do [[Nautilidae|nautilus]], por exemplo, pode ser facilmente percebida a sequência de Fibonacci. A composição de quadrados com lados de medidas proporcionais aos números da sequência mostram a existência desta sucessão numérica nesta peça natural.

O primeiro quadrado terá os lados com medida 1, o segundo também, o terceiro terá os seus lados com medida 2, o quarto com medida 3, o quinto com medida 5, o sexto com medida 8 e, assim, sucessivamente.

=== Anatomia humana - dentição ===
Vistos frontalmente, os dentes anteriores estão na [[proporção áurea]] entre si. Por exemplo, a largura do incisivo central está proporcional à largura do [[incisivo lateral]], assim como o incisivo lateral está proporcional ao [[canino]], e o canino ao primeiro [[pré-molar]].

O segmento “incisivo central até o primeiro pré-molar” se encontra na proporção áurea em relação ao canto da boca (final do sorriso).
A altura do incisivo central está na proporção áurea em relação à largura dos dois centrais Na face relaxada, a linha dos lábios divide o terço inferior da face nos segmentos da proporção áurea: “da ponta do nariz à linha dos lábios” e “da linha dos lábios até o queixo” ([[retângulo de ouro]]).

=== A espiral ===
[[Imagem:Bromelia.png|thumb|250px]]
Na [[espiral]] formada pela folha de uma [[bromélia]], pode ser percebida a sequência de Fibonacci, através da composição de quadrados com arestas de medidas proporcionais aos elementos da sequência, por exemplo: 1, 1, 2, 3, 5, 8, 13… , tendentes à [[razão áurea]]. Este mesmo tipo de espiral também pode ser percebida na concha do [[Nautilidae|Nautilus]] marinho.

=== Arranjos nas folhas ===
Os arranjos das folhas de algumas plantas em torno do caule são números de Fibonacci. Com este arranjo, todas as folhas conseguem apanhar os raios solares uniformemente. Esta formação, em caso de chuva, também facilita o escoamento da água na planta.

=== Reprodução das abelhas ===
A seqüência de Fibonacci descreve perfeitamente a reprodução das abelhas. Recentemente, uma análise matemática-histórica do contexto e da proximidade com a cidade de "[[Bugia (Argélia)|Bugia]]" (que é derivado da versão francesa do nome desta cidade, ou seja
"Bougie", que significa "vela" em francês), importante exportadora de cera na época de Leonardo de Pisa, sugeriu ele, fez o que realmente a abelha-produtores de Bugia e o conhecimento das linhagens de abelhas que inspirou os números da seqüência de Fibonacci, em vez de o modelo de reprodução de coelhos.<ref>{{Citation |primeiro1 =T.C.|último1 =Scott|primeiro2 =P.|último2 =Marketos| url = http://www-history.mcs.st-andrews.ac.uk/Publications/fibonacci.pdf  |título= On the Origin of the Fibonacci Sequence |publicado= [[MacTutor History of Mathematics archive]], University of St Andrews|formato= PDF |data=março de 2014}}</ref>

== A Sequência de Fibonacci no cinema ==
O filme Pi de [[Darren Aronofsky]] apresenta várias referências à sequência de Fibonacci. Seu protagonista é Maximillian "Max" Cohen (Sean Gullette), um matemático brilhante e atormentado que tenta decodificar o padrão numérico do mercado de ações. Em uma cena, Max desenha quadrados com arestas de medidas proporcionais aos elementos da sequência de Fibonacci e os sobrepõe ao desenho do [[Homem Vitruviano]] de [[Leonardo da Vinci]], trazendo-lhe certezas às suas convicções de que a matemática é a linguagem da natureza. Em outra cena, Max apanha uma concha em uma praia e observa a espiral nela descrita. Em outro trecho do filme, Max encontra o judeu Lenny Meyer, que lhe fala da crença em que a Torah seria uma sequência de números que formam um código enviado por [[Deus]], quando entendidas as correspondências entre as letras do alfabeto hebraico a números. Max diz que alguns dos conceitos apresentados por Lenny são similares a uma sequência de Fibonacci.

A sequência também é tema de um episódio da série [[Touch (série)|Touch]] da Rede [[Fox Broadcasting Company|FOX]] e de Criminal Minds, no canal AXN.

Em [[O Código Da Vinci (filme)|O Código Da Vinci]], a sequência de Fibonacci foi usada como um código, mas também para confundir os personagens.

== Repfigits ==
Um ''repfigit'' ou ''número de Keith'' é um número inteiro, superior a 9, tal que os seus dígitos, ao começar uma sequência de Fibonacci, alcançam posteriormente o referido número. Um exemplo é 47, porque a sequência de Fibonacci que começa com 4 e 7 (4, 7, 11, 18, 29, 47) alcança o 47.
Outro exemplo é '''197''': 1+9+7= 17, 9+7+17= 33, 7+17+33= 57, 17+33+57= 107, 33+57+107= '''197'''.

Um repfigit pode ser uma sequência de Tribonacci se houver três dígitos no número, e de Tetranacci se o número tiver quatro dígitos, etc.

Alguns Números de Keith conhecidos: 14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, 3684, 4788, 7385, 7647, 7909, 31331, 34285…

===Definição===
Um número Keith é um inteiro positivo N que aparece como um termo em uma relação de recorrência linear com termos iniciais com base nas suas próprias casas decimais. Dado um número <math>n</math> número de quatro dígitos:

<math display="block">N=\sum_{i=0}^{n-1} 10^i  {d_i},</math>

uma sequência <math>S_N</math> é formada com condições iniciais <math>d_{n-1}, d_{n-2},\ldots, d_1, d_0</math> e com um termo geral produzido como a soma dos anteriores <math>n</math> termos. Se o número N aparece na sequência <math>S_N</math> então dizemos que <math>N</math> é um número de Keith.
Números de um dígito possuem a propriedade Keith trivialmente, e normalmente são excluídos.

===Tabela com os 94 primeiros números de Keith<ref>OEIS/A007629-Lista dos 94 primeiros números de Keith< http://oeis.org/A007629/b007629.txt ></ref>===

{| class="wikitable"
|1 || 14
|-
|2 || 19
|-
|3  || 28
|-
|4 ||  47
|-
|5  || 61
|-
|6  || 75
|-
|7  || 197
|-
|8  || 742
|-
|9  || 1104
|-
|10  || 1537
|-
|11 ||  2208
|-
|12  || 2580
|-
|13  || 3684
|-
|14  || 4788
|-
|15  || 7385
|-
|16  || 7647
|-
|17  || 7909
|-
|18  || 31331
|-
|19  || 34285
|-
|20  || 34348
|-
|21  || 55604
|-
|22  || 62662
|-
|23  || 86935
|-
|24  || 93993
|-
|25  || 120284
|-
|26  || 129106
|-
|27  || 147640
|-
|28  || 156146
|-
|29  || 174680
|-
|30  || 183186
|-
|31  || 298320
|-
|32  || 355419
|-
|33  || 694280
|-
|34  || 925993
|-
|35  || 1084051
|-
|36  || 7913837
|-
|37  || 11436171
|-
|38  || 33445755
|-
|39  || 44121607
|-
|40  || 129572008
|-
|41  || 251133297
|-
|42  || 24769286411
|-
|43  || 96189170155
|-
|44  || 171570159070
|-
|45  || 202366307758
|-
|46  || 239143607789
|-
|47  || 296658839738
|-
|48  || 1934197506555
|-
|49  || 8756963649152
|-
|50  || 43520999798747
|-
|51  || 74596893730427
|-
|52  || 97295849958669
|-
|53  || 120984833091531
|-
|54  || 270585509032586
|-
|55  || 754788753590897
|-
|56  || 3621344088074041
|-
|57  || 3756915124022254
|-
|58  || 4362827422508274
|-
|59  || 11812665388886672
|-
|60  || 14508137312404344
|-
|61  || 16402582054271374
|-
|62  || 69953250322018194
|-
|63  || 73583709853303061
|-
|64  || 119115440241433462
|-
|65  || 166308721919462318
|-
|66  || 301273478581322148
|-
|67  || 1362353777290081176
|-
|68  || 3389041747878384662
|-
|69  || 5710594497265802190
|-
|70  || 5776750370944624064
|-
|71  || 6195637556095764016
|-
|72  || 12763314479461384279
|-
|73  || 27847652577905793413
|-
|74  || 45419266414495601903
|-
|75  || 855191324330802397989
|-
|76  || 7657230882259548723593
|-
|77  || 26842994422637112523337
|-
|78  || 36899277593852609997403
|-
|79  || 61333853602129819189668
|-
|80  || 229146413136585558461227
|-
|81  || 9838678687915198599200604
|-
|82  || 18354972585225358067718266
|-
|83  || 19876234926457288511947945
|-
|84  || 98938191214220718050301312
|-
|85  || 133118411174059688391045955
|-
|86  || 153669354455482560987178342
|-
|87  || 154140275428339949899922650
|-
|88  || 154677881401007799974564336
|-
|89  || 295768237361291708645227474
|-
|90  || 956633720464114515890318410
|-
|91  || 988242310393860390066911414
|-
|92  || 9493976840390265868522067200
|-
|93  || 41796205765147426974704791528
|-
|94  || 70267375510207885242218837404
|}

{{Notas e referências}}

== Ver também ==
* [[Proporção áurea]]
* [[Divisão em média e extrema razão]]
* [[György Dóczi]]

== Ligações externas ==
{{commonscat}}
* {{Link|pt|2=http://www.uff.br/cdme/rza/rza-html/rza-fibonacci-br.html|3=O número de ouro e a sequência de Fibonacci|4=UFF}}
* {{Link|en|2=http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/phi.html|3=The Golden Section: Phi|4=University of Surrey}}
* {{Link||2=http://rosettacode.org/wiki/Fibonacci_sequence?uselang=pt-br |3=Implementações do algoritmo em diversas linguagens de programação|4=Rosetta Code}}

{{Classes de números naturais}}
{{Séries (matemáticas)}}
{{Portal3|Matemática}}

{{DEFAULTSORT:Fibonacci}}
[[Categoria:Sequências de números inteiros]]