Sequência de Fibonacci
Na matemática, a sucessão de Fibonacci, é uma sequência de números inteiros, começando normalmente por 0 e 1, na qual cada termo subsequente corresponde à soma dos dois anteriores. A sequência recebeu o nome do matemático italiano Leonardo de Pisa ou Leonardo Fibonacci, mais conhecido por apenas 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.
No ocidente, a sequência de Fibonacci apareceu pela primeira vez no livro Liber Abaci (1202) de Leonardo Fibonacci, embora ela já tivesse sido descrita por gregos e indianos. 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: Mas genericamente, chama-se sequência de Fibonacci qualquer 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 Lucas L(n) reside no fato deles gerarem a Proporção áurea para as n-ésimas potências:
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: F n + 2 = F n F n + 1 2 ( 3 F n + 4 F n + 1 ) + 1 F n 2 + F n + 1 2 . {\displaystyle 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}}}}.} Observe que não é possível reduzir essa expressão à fórmula de recorrência F n + 2 = F n + 1 + F n , {\displaystyle F_{n+2}=F_{n+1}+F_{n},} apesar de ambas fornecerem o mesmo resultado na sequência de Fibonacci.
Função geradora
Uma função geradora para uma sequência qualquer a 0 , a 1 , a 2 , … {\displaystyle a_{0},a_{1},a_{2},\dots } é a função f ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + a 4 x 4 + ⋯ , {\displaystyle f(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+a_{4}x^{4}+\cdots ,} 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 f ( x ) = x 1 − x − x 2 . {\displaystyle f\left(x\right)={\frac {x}{1-x-x^{2}}}.} Quando se expande esta função em potências de x , {\displaystyle x,} os coeficientes são justamente os termos da sequência de Fibonacci: x 1 − x − x 2 = 0 x 0 + 1 x 1 + 1 x 2 + 2 x 3 + 3 x 4 + 5 x 5 + 8 x 6 + 13 x 7 + ⋯ {\displaystyle {\frac {x}{1-x-x^{2}}}=0x^{0}+1x^{1}+1x^{2}+2x^{3}+3x^{4}+5x^{5}+8x^{6}+13x^{7}+\cdots }
Fórmula explícita
Conforme mencionado por Johannes Kepler, a taxa de crescimento dos números de Fibonacci, que é F n + 1 / F n , {\textstyle F_{n+1}/F_{n},} tende à Proporção áurea, denotada por ϕ {\textstyle \phi } ϕ = 1 + 5 2 ≈ 1 , 61803398875. {\textstyle \phi ={\frac {1+{\sqrt {5}}}{2}}\approx 1,61803398875.} Em outras palavras, lim n → ∞ ( F n + 1 F n ) = ϕ = 1 + 5 2 = 1 , 61803398875. {\displaystyle \lim _{n\to \infty }\left({\frac {F_{n+1}}{F_{n}}}\right)=\phi ={\frac {1+{\sqrt {5}}}{2}}=1,61803398875.} (De um modo mais geral, lim n → ∞ ( F n + k F n ) = ϕ k . {\displaystyle \lim _{n\to \infty }\left({\frac {F_{n+k}}{F_{n}}}\right)={\phi }^{k}.} ) Esta é a raiz positiva da equação de segundo grau x² − x − 1 = 0, então φ² = φ + 1. Se multiplicarmos ambos os lados por φn, teremos φn+2 = φn+1 + φn, então a função φn é uma sequência de Fibonacci. É possível demonstrar que a raiz negativa da mesma equação, 1 − φ, tem as mesmas propriedades, então as duas funções φn e (1 − φ)n formam outra base para o espaço.
Forma matricial
Para argumentos muito grandes, quando utiliza-se um computador bignum, é mais fácil[carece de fontes?] calcular os números de Fibonacci usando a seguinte equação matricial: [ 1 1 1 0 ] n = [ F ( n + 1 ) F ( n ) F ( n ) F ( n − 1 ) ] , {\displaystyle {\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}},} 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.[nota 4]
Há diversos algoritmos (métodos) para calcular o n {\displaystyle n} -ésimo elemento da sequência de Fibonacci, sendo que os mais comuns empregam um das seguintes abordagens: 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 f i b ( n ) {\displaystyle {\it {fib}}(n)} 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 é O ( φ n ) . {\displaystyle O(\varphi ^{n}).} Por esse motivo, normalmente calcula-se os números de Fibonacci "de baixo para cima",[carece de fontes?] 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.
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 f i b ( n ) {\displaystyle {\it {fib}}(n)} j ← 1 {\displaystyle j\gets 1} i ← 0 {\displaystyle i\gets 0} Neste caso, a complexidade computacional do algoritmo é O ( n ) . {\displaystyle O(n).}
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 é O ( log ( n ) ) . {\displaystyle O(\log(n)).} função f i b ( n ) {\displaystyle {\it {fib}}(n)} i ← n − 1 {\displaystyle i\gets n-1} a ← 1 {\displaystyle a\gets 1} b ← 0 {\displaystyle b\gets 0} c ← 0 {\displaystyle c\gets 0} d ← 1 {\displaystyle d\gets 1} a u x 1 ← 0 {\displaystyle aux1\gets 0} a u x 2 ← 0 {\displaystyle aux2\gets 0}
Algoritmo em C
O algoritmo abaixo é um exemplo de como escrever um código simples em C para encontrar a sequência de Fibonacci.
Os números de Fibonacci são importantes para a análise em tempo real do 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 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 milhas para quilômetros. 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: Yuri Elias Rodrigues · CC0 · Openverse
Uma generalização da sequência de Fibonacci são as sequências de Lucas. Um tipo pode ser definido por: U ( 0 ) = 0 {\displaystyle U(0)=0} U ( 1 ) = 1 {\displaystyle U(1)=1} U ( n + 2 ) = P U ( n + 1 ) − Q U ( n ) {\displaystyle U(n+2)=PU(n+1)-QU(n)} onde a sequência normal de Fibonacci é o caso especial de P = 1 {\displaystyle P=1} e Q = − 1. {\displaystyle Q=-1.} Outro tipo de sequência de Lucas começa com V ( 0 ) = 2 , {\displaystyle V(0)=2,} V ( 1 ) = P . {\displaystyle V(1)=P.} 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.
Além disso, F n + 2 = F n F n + 1 2 ( 3 F n + 4 F n + 1 ) + 1 F n 2 + F n + 1 2 {\displaystyle 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}}}}} Esta fórmula pode ser provada por indução. Para N = 1 {\displaystyle N=1} é evidente. Supondo o resultado certo para N ≥ 1 {\displaystyle N\geq 1} ∑ n = 1 N + 1 n F n = ∑ n = 1 N n F n + ( N + 1 ) F N + 1 {\displaystyle \sum _{n=1}^{N+1}nF_{n}=\sum _{n=1}^{N}nF_{n}+(N+1)F_{N+1}} = N F N + 2 − F N + 3 + 2 + ( N + 1 ) F N + 1 {\displaystyle =NF_{N+2}-F_{N+3}+2+(N+1)F_{N+1}} = N F N + 3 − F N + 3 + 2 + F N + 1 {\displaystyle =NF_{N+3}-F_{N+3}+2+F_{N+1}} = N F N + 3 − F N + 3 + 2 + F N + 1 {\displaystyle =NF_{N+3}-F_{N+3}+2+F_{N+1}} = N F N + 3 − F N + 2 + 2 = N F N + 3 − ( F N + 4 − F N + 3 ) + 2 {\displaystyle =NF_{N+3}-F_{N+2}+2=NF_{N+3}-(F_{N+4}-F_{N+3})+2} = N F N + 2 + 2 − F N + 3 {\displaystyle =NF_{N+2}+2-F_{N+3}} Ou heuristicamente ∑ n = 1 N n F n = ∑ n = 1 N n ( F n + 2 − F n + 1 ) {\displaystyle \sum _{n=1}^{N}nF_{n}=\sum _{n=1}^{N}n(F_{n+2}-F_{n+1})} = ∑ n = 1 N ( n F n + 2 − n F n + 1 ) {\displaystyle =\sum _{n=1}^{N}(nF_{n+2}-nF_{n+1})} = ∑ n = 1 N ( ( n + 2 − 2 ) F n + 2 − ( n + 1 − 1 ) F n + 1 ) {\displaystyle =\sum _{n=1}^{N}((n+2-2)F_{n+2}-(n+1-1)F_{n+1})} = ∑ n = 1 N ( ( n + 2 ) F n + 2 − ( n + 1 ) F n + 1 ) − ∑ n = 1 N ( 2 F n + 2 − F n + 1 ) {\displaystyle =\sum _{n=1}^{N}((n+2)F_{n+2}-(n+1)F_{n+1})-\sum _{n=1}^{N}(2F_{n+2}-F_{n+1})} = ( N + 2 ) F N + 2 − 2 F 2 − ∑ n = 1 N ( F n + 2 + F n ) {\displaystyle =(N+2)F_{N+2}-2F_{2}-\sum _{n=1}^{N}(F_{n+2}+F_{n})} = ( N + 2 ) F N + 2 − 2 − ( F N + 4 − 1 − F 1 − F 2 + F N + 2 − 1 ) {\displaystyle =(N+2)F_{N+2}-2-(F_{N+4}-1-F_{1}-F_{2}+F_{N+2}-1)} = ( N + 1 ) F N + 2 + 2 − ( F N + 4 ) {\displaystyle =(N+1)F_{N+2}+2-(F_{N+4})} = N F N + 2 + − ( F N + 4 − F N + 2 ) {\displaystyle =NF_{N+2}+-(F_{N+4}-F_{N+2})} = N F N + 2 + 2 − F N + 3 {\displaystyle =NF_{N+2}+2-F_{N+3}}
1) Considerando-se os inteiros positivos a ≥ 1 {\displaystyle a\geq 1} e b ≥ 1 , {\displaystyle b\geq 1,} então : F b + a = F b − 1 F a + F b F a + 1 {\displaystyle F_{b+a}=F_{b-1}F_{a}+F_{b}F_{a+1}} Prova: F b + 1 = F b − 1 + F b {\displaystyle F_{b+1}=F_{b-1}+F_{b}} F b + 2 = F b + F b + 1 {\displaystyle F_{b+2}=F_{b}+F_{b+1}} F b + ( q − 2 ) = F b − 1 F q − 2 + F b F q − 1 {\displaystyle F_{b+(q-2)}=F_{b-1}F_{q-2}+F_{b}F_{q-1}} F b + ( q − 1 ) = F b − 1 F q − 1 + F b F q {\displaystyle F_{b+(q-1)}=F_{b-1}F_{q-1}+F_{b}F_{q}} F b + q = F b − 1 F q + F b F q + 1 {\displaystyle F_{b+q}=F_{b-1}F_{q}+F_{b}F_{q+1}} Isso vale também para q . {\displaystyle q.} Logo, fazendo-se a substituição: F b + a = F b − 1 F a + F b F a + 1 {\displaystyle F_{b+a}=F_{b-1}F_{a}+F_{b}F_{a+1}} F a ( q + 1 ) = F a q + a = F a q − 1 F a + F a q F a + 1 . {\displaystyle F_{a(q+1)}=F_{aq+a}=F_{aq-1}F_{a}+F_{aq}F_{a+1}.}
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.
Forma explícita dos números de Tribonacci
De modo semelhante à sequência de Fibonacci, é possível obter a forma explícita de um número Tribonacci ( T n ) : {\displaystyle (T_{n}):} T 1 = T 2 = 1 {\displaystyle T_{1}=T_{2}=1} e T 3 = 2 {\displaystyle T_{3}=2} e T n = T n − 1 + T n − 2 + T n − 3 {\displaystyle T_{n}=T_{n-1}+T_{n-2}+T_{n-3}} Sendo α , {\displaystyle \alpha ,} β {\displaystyle \beta } e γ {\displaystyle \gamma } as soluções da equação: x 3 − x 2 − x − 1 = 0. {\displaystyle x^{3}-x^{2}-x-1=0.} Então: T n = α n + 1 ( α − β ) ( α − γ ) + β n + 1 ( β − α ) ( β − γ ) + γ n + 1 ( γ − α ) ( γ − β ) {\displaystyle 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 )}}}
Função geradora
x 1 − x − x 2 − x 3 = 1 + x + 2 x 2 + 4 x 3 + 7 x 4 + 13 x 5 + 24 x 6 + 44 x 7 + 81 x 8 + 149 x 9 + . . . {\displaystyle {\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}+...}
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 A n = a A n − 1 + b A n − 2 , {\displaystyle A_{n}=aA_{n-1}+bA_{n-2},} onde a {\displaystyle a} e b {\displaystyle b} são números reais. Tomemos, como exemplo, a sequência definida recursivamente por A n = 2 A n − 1 + A n − 2 {\displaystyle A_{n}=2A_{n-1}+A_{n-2}} com A 1 = A 2 = 1. {\displaystyle A_{1}=A_{2}=1.} É a sequência ( 1 , 1 , 3 , 7 , 17 , 41 , 99 , 239 , 577 , . . . ) {\displaystyle (1,1,3,7,17,41,99,239,577,...)} 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 é ( 1 + 2 ) = 2 , 41421356237309... {\displaystyle (1+{\sqrt {2}})=2,41421356237309...} Ou seja, lim n → ∞ ( A n A n − 1 ) = 1 + 2 = 2 , 41421356237309.... {\displaystyle \lim _{n\to \infty }\left({\frac {A_{n}}{A_{n-1}}}\right)=1+{\sqrt {2}}=2,41421356237309....}
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
Na espiral do 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
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 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" (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.
