Números de Fibonacci

A sequência de Fibonacci é definida da seguinte maneira:

$$F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$$

Os primeiros elementos da sequência (OEIS A000045) são:

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

Propriedades

Os números de Fibonacci possuem muitas propriedades interessantes. Aqui estão algumas delas:

Codificação de Fibonacci

Podemos usar a sequência para codificar números inteiros positivos em palavras de código binárias. De acordo com o teorema de Zeckendorf, qualquer número natural $n$ pode ser representado exclusivamente como uma soma dos números de Fibonacci:

$$N = F_{k_1} + F_{k_2} + \ldots + F_{k_r}$$

tal que $k_1 \ge k_2 + 2,\ k_2 \ge k_3 + 2,\ \ldots,\ k_r \ge 2$ (ou seja: a representação não pode usar dois números Fibonacci consecutivos).

Segue-se que qualquer número pode ser codificado na sequência de Fibonacci. E podemos descrever essa representação com códigos binários $d_0 d_1 d_2 \dots d_s 1$, onde $d_i$ é $1$ se $F_{i+2}$ for usado na representação. O código será anexado com $1$ indicando o final do código da palavra. Observe que essa é a única ocorrência em que dois bits consecutivos são exibidos.

$$\begin{eqnarray} 1 &=& 1 &=& F_2 &=& (11)_F \\ 2 &=& 2 &=& F_3 &=& (011)_F \\ 6 &=& 5 + 1 &=& F_5 + F_2 &=& (10011)_F \\ 8 &=& 8 &=& F_6 &=& (000011)_F \\ 9 &=& 8 + 1 &=& F_6 + F_2 &=& (100011)_F \\ 19 &=& 13 + 5 + 1 &=& F_7 + F_5 + F_2 &=& (1001011)_F \end{eqnarray}$$

A codificação de um número inteiro $n$ pode ser feita com um algoritmo guoloso(greedy):

  1. Itere sobre os números de Fibonacci do maior para o menor até encontrar um menor ou igual a $n$.

  2. Suponha que esse número seja $F_i$. Subtraia $F_i$ de $n$ e coloque $1$ na posição $i-2$ da palavra do código (indexação começando de 0 do bit da esquerda até a direita).

  3. Repita até que não haja mais restos.

  4. Adicione um $1$ à palavra-código para indicar seu fim.

Para decodificar uma palavra de código, remova primeiro o $1$ final. Então, se o $i$-th bit estiver definido(set) (indexando de 0 do bit mais à esquerda para a direita), some $F_{i+2}$ ao número.

Fórmulas para o n-ésimo número de Fibonacci

O n-ésimo número de Fibonacci pode ser encontrado em $O(n)$ calculando os números um por um até $n$. Entretanto, existem métodos mais rápidos, como veremos.

Expressões

Existe uma fórmula conhecida como "fórmula de Binet", embora já fosse conhecida por Moivre:

$$F_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}}$$

É possível provar esta fórmula por indução, mas pode ser deduzida com a ajuda do conceito de gerar funções ou resolver uma equação funcional.

Você pode perceber imediatamente que o valor absoluto do segundo termo é sempre menor que $1$, e também diminui muito rapidamente (exponencialmente). Portanto, o valor do primeiro termo é "quase" $F_n$. Isso pode ser escrito estritamente como:

$$F_n = \left[\frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n}{\sqrt{5}}\right]$$

onde os colchetes indicam o arredondamento para o número inteiro mais próximo.

Como essas duas fórmulas exigiriam uma precisão muito alta ao trabalhar com números fracionários, elas são de pouca utilidade em cálculos práticos.

Forma de Matriz

Usando a seguinte relação:

$$\begin{pmatrix}F_{n-1} & F_{n} \cr\end{pmatrix} = \begin{pmatrix}F_{n-2} & F_{n-1} \cr\end{pmatrix} \cdot \begin{pmatrix}0 & 1 \cr 1 & 1 \cr\end{pmatrix}$$

Definindo $P \equiv \begin{pmatrix}0 & 1 \cr 1 & 1 \cr\end{pmatrix}$, obtemos:

$$\begin{pmatrix}F_n & F_{n+1} \cr\end{pmatrix} = \begin{pmatrix}F_0 & F_1 \cr\end{pmatrix} \cdot P^n$$

Portanto, para encontrar $F_n$, precisamos elevar a matriz $P$ ao índice $n$. Isso pode ser feito em $O(\log n)$ (Exponenciação binária).

Método de duplicação rápida

Usando o método acima, podemos encontrar estas equações: $$ \begin{array}{rll} F_{2k} &= F_k \left( 2F_{k+1} - F_{k} \right). \\ F_{2k+1} &= F_{k+1}^2 + F_{k}^2. \end{array}$$ Assim, usando as duas equações acima, os números de Fibonacci podem ser calculados pelo seguinte código:

pair<int, int> fib (int n) {
    if (n == 0)
        return {0, 1};

    auto p = fib(n >> 1);
    int c = p.first * (2 * p.second - p.first);
    int d = p.first * p.first + p.second * p.second;
    if (n & 1)
        return {d, c + d};
    else
        return {c, d};
}

O código acima retorna $F_n$ e $F_{n+1}$ como um par.

Periodicidade módulo p

Considere a sequência Fibonacci modulo $p$. Vamos provar que a sequência é periódica e o período começa com $F_1 = 1$ (ou seja, o pré-período contém apenas $F_0$).

amos provar isso por contradição. Considere os primeiros pares de números de Fibonacci $p^2 + 1$ modulo $p$:

$$(F_1,\ F_2),\ (F_2,\ F_3),\ \ldots,\ (F_{p^2 + 1},\ F_{p^2 + 2})$$

Só pode haver $p$ diferentes modulos de $p$, e no máximo $p^2$ de restos diferentes; portanto, existem pelo menos dois pares idênticos entre eles. Assim, a sequência é periódica.

Agora, escolhemos dois pares de restos idênticos com os menores índices da sequência. Sejam os pares $(F_a,\ F_{a + 1})$ e $(F_b,\ F_{b + 1})$. Provaremos que $a = 1$. Se isso fosse falso, haveria dois pares anteriores $(F_{a-1},\ F_a)$ e $(F_{b-1},\ F_b)$, nos quais, pela propriedade dos números de Fibonacci, também seriam iguais. No entanto, isso contradiz o fato de termos escolhido pares com os menores índices, completando nossa prova.

Problemas