Números de Fibonacci

La sucesión de Fibonacci se define de la siguiente manera:

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

Los primeros elementos de la sucesión (OEIS A000045 ) son:

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

Propiedades

Los números de Fibonacci poseen muchas propiedades interesantes. Aquí hay algunas de ellas:

Identidad de Cassini:

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

Esta identidad se puede demostrar por inducción. Una demostración de una sola línea de Knuth se obtiene tomando el determinante de la forma matricial 2x2 de más abajo.

La regla de “suma”:

$F_{n+k} = F_k F_{n+1} + F_{k-1} F_n$

Aplicando la identidad anterior al caso $k = n$ , obtenemos:

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

A partir de esto podemos demostrar por inducción que, para cualquier entero positivo $k$ , $F_{nk}$ es múltiplo de $F_n$ .
El recíproco también es cierto: si $F_m$ es múltiplo de $F_n$ , entonces $m$ es múltiplo de $n$ .
Identidad del GCD:

$GCD(F_m, F_n) = F_{GCD(m, n)}$

Los números de Fibonacci son las peores entradas posibles para el algoritmo de Euclides (véase el teorema de Lamé en Algoritmo de Euclides)

Codificación de Fibonacci

Podemos usar la sucesión para codificar enteros positivos en palabras de código binarias. Según el teorema de Zeckendorf, cualquier número natural $n$ se puede representar de forma única como una suma de 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$ (es decir: la representación no puede usar dos números de Fibonacci consecutivos).

Se sigue que cualquier número se puede codificar de forma única en la codificación de Fibonacci. Y podemos describir esta representación con códigos binarios $d_0 d_1 d_2 \dots d_s 1$ , donde $d_i$ es $1$ si $F_{i+2}$ se usa en la representación. Al código se le agregará un $1$ para indicar el final de la palabra de código. Nótese que esta es la única ocurrencia en la que aparecen dos bits 1 consecutivos.

$\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}$

La codificación de un entero $n$ se puede hacer con un algoritmo voraz (greedy) simple:

Iterar por los números de Fibonacci de mayor a menor hasta encontrar uno menor o igual que $n$ .
Supongamos que este número fue $F_i$ . Restar $F_i$ de $n$ y poner un $1$ en la posición $i-2$ de la palabra de código (indexando desde 0, del bit más a la izquierda al más a la derecha).
Repetir hasta que no quede resto.
Agregar un $1$ final a la palabra de código para indicar su fin.

Para decodificar una palabra de código, primero se quita el $1$ final. Después, si el $i$ -ésimo bit está prendido (indexando desde 0, del bit más a la izquierda al más a la derecha), se suma $F_{i+2}$ al número.

Fórmulas para el número de Fibonacci { data-toc-label=“Fórmulas para el $n$ -ésimo número de Fibonacci” }

Expresión en forma cerrada

Hay una fórmula conocida como “fórmula de Binet”, aunque ya era conocida por Moivre:

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

Esta fórmula es fácil de demostrar por inducción, pero se puede deducir con ayuda del concepto de funciones generatrices o resolviendo una ecuación funcional.

Se puede notar de inmediato que el valor absoluto del segundo término siempre es menor que $1$ , y además decrece muy rápido (exponencialmente). Por lo tanto, el valor del primer término por sí solo es “casi” $F_n$ . Esto se puede escribir de forma estricta como:

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

donde los corchetes denotan el redondeo al entero más cercano.

Como estas dos fórmulas exigirían una precisión muy alta al trabajar con números fraccionarios, son de poca utilidad en cálculos prácticos.

Fibonacci en tiempo lineal

El $n$ -ésimo número de Fibonacci se puede encontrar fácilmente en $O(n)$ calculando los números uno por uno hasta $n$ . Sin embargo, también hay formas más rápidas, como veremos.

Podemos partir de un enfoque iterativo, para aprovechar el uso de la fórmula $F_n = F_{n-1} + F_{n-2}$ ; por lo tanto, simplemente precalcularemos esos valores en un arreglo. Teniendo en cuenta los casos base para $F_0$ y $F_1$ .


int fib(int n) {
    int a = 0;
    int b = 1;
    for (int i = 0; i < n; i++) {
        int tmp = a + b;
        a = b;
        b = tmp;
    }
    return a;
}

De esta manera obtenemos una solución lineal, de tiempo $O(n)$ , conservando todos los valores anteriores a $n$ en la sucesión.

Forma matricial

Para pasar de $(F_n, F_{n-1})$ a $(F_{n+1}, F_n)$ , podemos expresar la recurrencia lineal como una multiplicación de matrices 2x2:

$(\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}) (\begin{array}{c} F_{n} \\ F_{n - 1} \end{array}) = (\begin{array}{c} F_{n} + F_{n - 1} \\ F_{n} \end{array}) = (\begin{array}{c} F_{n + 1} \\ F_{n} \end{array})$

$\begin{pmatrix} F_n + F_{n-1} \ F_{n} \end{pmatrix}$

$\begin{pmatrix} F_{n+1} \ F_{n} \end{pmatrix}$ $(1110) (F_{n} F_{n - 1}) = (F_{n} + F_{n - 1} F_{n}) = (F_{n + 1} F_{n})$

Esto nos permite tratar la iteración de la recurrencia como una multiplicación repetida de matrices, que tiene propiedades convenientes. En particular,

${(\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array})}^{n} (\begin{array}{c} F_{1} \\ F_{0} \end{array}) = (\begin{array}{c} F_{n + 1} \\ F_{n} \end{array})$

$\begin{pmatrix} F_{n+1} \ F_{n} \end{pmatrix}$ $(1110)^{n} (F_{1} F_{0}) = (F_{n + 1} F_{n})$

donde $F_1 = 1, F_0 = 0$ . De hecho, como

$(\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}) = (\begin{array}{cc} F_{2} & F_{1} \\ F_{1} & F_{0} \end{array})$

podemos usar la matriz de forma directa:

${(\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array})}^{n} = (\begin{array}{cc} F_{n + 1} & F_{n} \\ F_{n} & F_{n - 1} \end{array})$

Así, para encontrar $F_n$ en tiempo $O(\log n)$ , hay que elevar la matriz a la $n$ . (Véase Exponenciación binaria)


struct matrix {
    long long mat[2][2];
    matrix friend operator *(const matrix &a, const matrix &b){
        matrix c;
        for (int i = 0; i < 2; i++) {
          for (int j = 0; j < 2; j++) {
              c.mat[i][j] = 0;
              for (int k = 0; k < 2; k++) {
                  c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
              }
          }
        }
        return c;
    }
};

matrix matpow(matrix base, long long n) {
    matrix ans{ {
      {1, 0},
      {0, 1}
    } };
    while (n) {
        if(n&1)
            ans = ans*base;
        base = base*base;
        n >>= 1;
    }
    return ans;
}

long long fib(int n) {
    matrix base{ {
      {1, 1},
      {1, 0}
    } };
    return matpow(base, n).mat[0][1];
}

Método de duplicación rápida

Al expandir la expresión matricial anterior para $n = 2\cdot k$

$(\begin{array}{cc} F_{2 k + 1} & F_{2 k} \\ F_{2 k} & F_{2 k - 1} \end{array}) = {(\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array})}^{2 k} = {(\begin{array}{cc} F_{k + 1} & F_{k} \\ F_{k} & F_{k - 1} \end{array})}^{2}$

$\begin{pmatrix} 1 & 1\ 1 & 0 \end{pmatrix}$ ^{2k}

$\begin{pmatrix} F_{k+1} & F_{k}\ F_{k} & F_{k-1} \end{pmatrix}$ ^2 $(F_{2 k + 1} F_{2 k} F_{2 k} F_{2 k - 1}) = (1110)^{2 k} = (F_{k + 1} F_{k} F_{k} F_{k - 1})^{2}$

podemos encontrar estas ecuaciones más simples:

$\begin{aligned} F_{2 k + 1} & = F_{k + 1}^{2} + F_{k}^{2} \\ F_{2 k} & = F_{k} (F_{k + 1} + F_{k - 1}) = F_{k} (2 F_{k + 1} - F_{k}) \end{aligned} .$

Así, usando las dos ecuaciones anteriores, los números de Fibonacci se pueden calcular fácilmente con el siguiente 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};
}

El código anterior devuelve $F_n$ y $F_{n+1}$ como un par.

Periodicidad módulo p

Consideremos la sucesión de Fibonacci módulo $p$ . Demostraremos que la sucesión es periódica.

Demostrémoslo por contradicción. Consideremos los primeros $p^2 + 1$ pares de números de Fibonacci tomados módulo $p$ :

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

Solo puede haber $p$ restos distintos módulo $p$ , y a lo sumo $p^2$ pares distintos de restos, así que hay al menos dos pares idénticos entre ellos. Esto basta para demostrar que la sucesión es periódica, ya que un número de Fibonacci solo está determinado por sus dos predecesores. Por lo tanto, si se repiten dos pares de números consecutivos, eso también significa que los números posteriores al par se repetirán de la misma manera.

Ahora elegimos dos pares de restos idénticos con los índices más chicos en la sucesión. Sean los pares $(F_a,\ F_{a + 1})$ y $(F_b,\ F_{b + 1})$ . Demostraremos que $a = 0$ . Si esto fuera falso, habría dos pares anteriores $(F_{a-1},\ F_a)$ y $(F_{b-1},\ F_b)$ que, por la propiedad de los números de Fibonacci, también serían iguales. Sin embargo, esto contradice el hecho de que habíamos elegido pares con los índices más chicos, lo que completa nuestra demostración de que no hay preperíodo (es decir, los números son periódicos a partir de $F_0$ ).

Números de Fibonacci

Propiedades

Codificación de Fibonacci

Fórmulas para el nthn^{\text{th}}nth número de Fibonacci { data-toc-label=“Fórmulas para el n-ésimo número de Fibonacci” }

Expresión en forma cerrada

Fibonacci en tiempo lineal

Forma matricial

(1110)(FnFn−1)=(Fn+Fn−1Fn)=(Fn+1Fn) (1amp;11amp;0)\begin{pmatrix} 1 &amp; 1 \ 1 &amp; 0 \end{pmatrix}(11​amp;1amp;0​) (FnFn−1)\begin{pmatrix} F_n \ F_{n-1} \end{pmatrix}(Fn​Fn−1​​)

(Fn+Fn−1Fn)\begin{pmatrix} F_n + F_{n-1} \ F_{n} \end{pmatrix}(Fn​+Fn−1​Fn​​)

(1110)n(F1F0)=(Fn+1Fn) (1amp;11amp;0)\begin{pmatrix} 1 &amp; 1 \ 1 &amp; 0 \end{pmatrix}(11​amp;1amp;0​)^n (F1F0)\begin{pmatrix} F_1 \ F_0 \end{pmatrix}(F1​F0​​)