secuencia de Fibonacci

La secuencia de Fibonacci aparece en las matemáticas indias , en relación con la prosodia sánscrita . ^{[ 4 ] [ 11 ] [ 12 ]} En la tradición poética sánscrita, existía interés en enumerar todos los patrones de sílabas largas (L) de 2 unidades de duración, yuxtapuestas con sílabas cortas (S) de 1 unidad de duración. Contando los diferentes patrones de L y S sucesivas con una duración total dada se obtienen los números de Fibonacci: el número de patrones de duración m unidades es F _{m +1} . ^{[ 5 ]}

El conocimiento de la secuencia de Fibonacci se expresó ya en Pingala ( c.  450  a. C.–200  a. C.). Singh cita la fórmula críptica de Pingala misrau cha ("los dos están mezclados") y a los eruditos que la interpretan en contexto como diciendo que el número de patrones para m tiempos ( F _{m +1} ) se obtiene añadiendo un [S] a los casos F _m y un [L] a los casos F _{m −1 .} ^{[ 13 ]} Bharata Muni también expresa conocimiento de la secuencia en el Natya Shastra ( c.  100  a. C.–c. 350 d . C.). ^{[ 3 ] [ 4 ]} Sin embargo, la exposición más clara de la secuencia surge en la obra de Virahanka ( c. 700 d. C.), cuya propia obra se ha perdido, pero está disponible en una cita de Gopala ( c. 1135): ^{[ 12 ]}     

Variaciones de dos metros anteriores [es la variación]  ... Por ejemplo, para [un metro de longitud] cuatro, al mezclarse variaciones de metros de dos [y] tres, se obtiene cinco. [resuelve los ejemplos 8, 13, 21]  ... De esta manera, el proceso debe seguirse en todas las mātrā-vṛttas [combinaciones prosódicas]. ^{[ a ]}

A Hemachandra ( c.  1150) también se le atribuye el conocimiento de la secuencia, ^{[ 3 ]} escribiendo que "la suma del último y el anterior es el número  ... del siguiente mātrā-vṛtta". ^{[ 15 ] [ 16 ]}

La secuencia de Fibonacci aparece por primera vez en el libro Liber Abaci ( El Libro de Cálculos , 1202) de Fibonacci , ^{[ 17 ] [ 18 ]} donde se utiliza para calcular el crecimiento de poblaciones de conejos. ^{[ 19 ]} Fibonacci considera el crecimiento de una población de conejos idealizada ( biológicamente irreal) , asumiendo que: una pareja reproductora recién nacida se coloca en un campo; cada pareja reproductora se aparea a la edad de un mes, y al final de su segundo mes siempre producen otra pareja de conejos; y los conejos nunca mueren, sino que continúan reproduciéndose para siempre. Fibonacci planteó el problema matemático del conejo : ¿cuántas parejas habrá en un año?

• Al final del primer mes, se aparean, pero sigue habiendo solo una pareja.
• Al final del segundo mes, producen una nueva pareja, por lo que hay 2 parejas en el campo.
• Al final del tercer mes, la pareja original produce una segunda pareja, pero esta segunda pareja solo se aparea para gestar durante un mes, por lo que hay 3 parejas en total.
• Al final del cuarto mes, la pareja original ha producido otra nueva pareja, y la pareja nacida hace dos meses también produce su primera pareja, con lo que suma 5 parejas.

Al final del n -ésimo mes, el número de parejas de conejos es igual al número de parejas maduras (es decir, el número de parejas en el mes n – 2 ) más el número de parejas vivas el mes anterior (mes n – 1 ). El número en el n -ésimo mes es el n -ésimo número de Fibonacci. ^{[ 20 ]}

El nombre "secuencia de Fibonacci" fue utilizado por primera vez por el teórico de números del siglo XIX Édouard Lucas . ^{[ 21 ]}

Like every sequence defined by a homogeneous linear recurrence with constant coefficients, the Fibonacci numbers have a closed-form expression.^[22] It has become known as Binet's formula, named after French mathematician Jacques Philippe Marie Binet, though it was already known by Abraham de Moivre and Daniel Bernoulli:^[23]

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

where ⁠${\displaystyle \varphi }$⁠ (phi) is the golden ratio and ⁠${\displaystyle \psi }$⁠ (psi) is its conjugate,^[24]

$${\displaystyle {\begin{aligned}\varphi &={\tfrac {1}{2}}{\bigl (}1+{\sqrt {5}}~\!{\bigr )}={\phantom {-}}1.61803\ldots ,\\[5mu]\psi &={\tfrac {1}{2}}{\bigl (}1-{\sqrt {5}}~\!{\bigr )}=-0.61803\ldots .\end{aligned}}}$$

The numbers ⁠${\displaystyle \varphi }$⁠ and ⁠${\displaystyle \psi }$⁠ are the two solutions of the quadratic equation⁠${\displaystyle \textstyle x^{2}-x-1=0}$⁠, that is, ⁠${\displaystyle (x-\varphi )(x-\psi )=x^{2}-x-1}$⁠, and thus they satisfy the identities ⁠${\displaystyle \varphi +\psi =1}$⁠ and ⁠${\displaystyle \varphi \psi =-1}$⁠.

Since ${\displaystyle \psi =-\varphi ^{-1}}$, Binet's formula can also be written as

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

To see the relation between the sequence and these constants,^[25] note that ${\displaystyle \varphi }$ and ${\displaystyle \psi }$ are also roots of ${\displaystyle x^{n}=x^{n-1}+x^{n-2},}$ so the powers of ${\displaystyle \varphi }$ and ${\displaystyle \psi }$ satisfy the Fibonacci recurrence. In other words,

$${\displaystyle {\begin{aligned}\varphi ^{n}&=\varphi ^{n-1}+\varphi ^{n-2},\\[3mu]\psi ^{n}&=\psi ^{n-1}+\psi ^{n-2}.\end{aligned}}}$$

It follows that for any values a and b, the sequence defined by

$${\displaystyle U_{n}=a\varphi ^{n}+b\psi ^{n}}$$

satisfies the same recurrence. If a and b are chosen so that U₀ = 0 and U₁ = 1 then the resulting sequence U_n must be the Fibonacci sequence. This is the same as requiring a and b satisfy the system of equations:

$${\displaystyle {\begin{aligned}a\varphi ^{0}+b\psi ^{0}&=0\\a\varphi ^{1}+b\psi ^{1}&=1\end{aligned}}}$$

which has solution

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

producing the required formula.

Taking the starting values U₀ and U₁ to be arbitrary constants and solving the system of equations gives the general solution $${\displaystyle {\begin{aligned}a&={\frac {U_{1}-U_{0}\psi }{\sqrt {5}}},\\[3mu]b&={\frac {U_{0}\varphi -U_{1}}{\sqrt {5}}}.\end{aligned}}}$$ In particular, choosing a = 1 makes the n-th element of the sequence closely approximate the n-th power of ⁠${\displaystyle \varphi }$⁠ for large enough values of n. This arises when U₀ = 2 and U₁ = 1, which produces the sequence of Lucas numbers.

Since ${\textstyle \left|{\frac {\psi ^{n}}{\sqrt {5}}}\right|<{\frac {1}{2}}}$ for all n ≥ 0, the number F_n is the closest integer to ${\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}}$. Therefore, it can be found by rounding, using the nearest integer function: $${\displaystyle F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}\right\rceil ,\ n\geq 0.}$$

In fact, the rounding error quickly becomes very small as n grows, being less than 0.1 for n ≥ 4, and less than 0.01 for n ≥ 8. This formula is easily inverted to find an index of a Fibonacci number F: $${\displaystyle n(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}F\right\rceil ,\ F\geq 1.}$$

Instead using the floor function gives the largest index of a Fibonacci number that is not greater than F: $${\displaystyle n_{\mathrm {largest} }(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}(F+1/2)\right\rfloor ,\ F\geq 0,}$$ where ${\displaystyle \log _{\varphi }(x)=\ln(x)/\ln(\varphi )=\log _{10}(x)/\log _{10}(\varphi )}$, ${\displaystyle \ln(\varphi )=0.481211\ldots }$,^[26] and ${\displaystyle \log _{10}(\varphi )=0.208987\ldots }$.^[27]

Since F_n is asymptotic to ${\displaystyle \varphi ^{n}/{\sqrt {5}}}$, the number of digits in F_n is asymptotic to ${\displaystyle n\log _{10}\varphi \approx 0.2090\,n}$. As a consequence, for every integer d > 1 there are either 4 or 5 Fibonacci numbers with d decimal digits.

More generally, in the baseb representation, the number of digits in F_n is asymptotic to ${\displaystyle n\log _{b}\varphi ={\frac {n\log \varphi }{\log b}}.}$

Johannes Kepler observed that the ratio of consecutive Fibonacci numbers converges. He wrote that "as 5 is to 8 so is 8 to 13, practically, and as 8 is to 13, so is 13 to 21 almost", and concluded that these ratios approach the golden ratio ⁠${\displaystyle \varphi }$⁠:^[28][29]$${\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi .}$$

This convergence holds regardless of the starting values ${\displaystyle U_{0}}$ and ${\displaystyle U_{1}}$, unless ${\displaystyle U_{1}=-U_{0}/\varphi }$. This can be verified using Binet's formula. For example, the initial values 3 and 2 generate the sequence 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, .... The ratio of consecutive elements in this sequence shows the same convergence towards the golden ratio.

In general, ${\displaystyle \lim _{n\to \infty }{\frac {F_{n+m}}{F_{n}}}=\varphi ^{m}}$, because the ratios between consecutive Fibonacci numbers approaches ${\displaystyle \varphi }$.

Since the golden ratio satisfies the equation $${\displaystyle \varphi ^{2}=\varphi +1,}$$

this expression can be used to decompose higher powers ${\displaystyle \varphi ^{n}}$ as a linear function of lower powers, which in turn can be decomposed all the way down to a linear combination of ${\displaystyle \varphi }$ and 1. The resulting recurrence relationships yield Fibonacci numbers as the linear coefficients: $${\displaystyle \varphi ^{n}=F_{n}\varphi +F_{n-1}.}$$ Esta ecuación se puede demostrar por inducción sobre n ≥ 1 : $${\displaystyle {\begin{aligned}\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}.\end{aligned}}}$$ Para${\displaystyle \psi =-1/\varphi }$, también es cierto que${\displaystyle \psi ^{2}=\psi +1}$y también es cierto que $${\displaystyle \psi ^{n}=F_{n}\psi +F_{n-1}.}$$

Estas expresiones también son válidas para n < 1 si la secuencia de Fibonacci F _n se extiende a enteros negativos utilizando la regla de Fibonacci.${\displaystyle F_{n}=F_{n+2}-F_{n+1}.}$

La fórmula de Binet proporciona una prueba de que un entero positivo x es un número de Fibonacci si y solo si al menos uno de${\displaystyle 5x^{2}+4}$o${\displaystyle 5x^{2}-4}$es un cuadrado perfecto . ^{[ 30 ]} Esto se debe a que la fórmula de Binet, que se puede escribir como${\displaystyle F_{n}=(\varphi ^{n}-(-1)^{n}\varphi ^{-n})/{\sqrt {5}}}$, se puede multiplicar por${\displaystyle {\sqrt {5}}\varphi ^{n}}$y resuelta como una ecuación cuadrática en${\displaystyle \varphi ^{n}}$mediante la fórmula cuadrática :

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

Comparando esto con${\displaystyle \varphi ^{n}=F_{n}\varphi +F_{n-1}=(F_{n}{\sqrt {5}}+F_{n}+2F_{n-1})/2}$De ello se deduce que

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

En particular, el lado izquierdo es un cuadrado perfecto.

Most identities involving Fibonacci numbers can be proved using combinatorial arguments using the fact that ${\displaystyle F_{n}}$ can be interpreted as the number of (possibly empty) sequences of 1s and 2s whose sum is ${\displaystyle n-1}$. This can be taken as the definition of ${\displaystyle F_{n}}$ with the conventions ${\displaystyle F_{0}=0}$, meaning no such sequence exists whose sum is −1, and ${\displaystyle F_{1}=1}$, meaning the empty sequence "adds up" to 0. In the following, ${\displaystyle |{...}|}$ is the cardinality of a set:

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

In this manner the recurrence relation $${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$$ puede entenderse dividiendo el${\displaystyle F_{n}}$secuencias en dos conjuntos que no se superponen, donde todas las secuencias comienzan con 1 o 2: $${\displaystyle F_{n}=|\{(1,...),(1,...),...\}|+|\{(2,...),(2,...),...\}|}$$ Excluyendo el primer elemento, los términos restantes en cada secuencia suman${\displaystyle n-2}$o${\displaystyle n-3}$y la cardinalidad de cada conjunto es${\displaystyle F_{n-1}}$o${\displaystyle F_{n-2}}$dando un total de${\displaystyle F_{n-1}+F_{n-2}}$secuencias, mostrando que esto es igual a${\displaystyle F_{n}}$.

De manera similar se puede demostrar que la suma de los primeros números de Fibonacci hasta el n -ésimo es igual al ( n + 2) -ésimo número de Fibonacci menos  1. ^{[ 33 ]} En símbolos: $${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$$

Esto se puede observar dividiendo todas las secuencias que suman${\displaystyle n+1}$basado en la ubicación de los dos primeros. Específicamente, cada conjunto consta de aquellas secuencias que comienzan${\displaystyle (2,...),(1,2,...),...,}$hasta los dos últimos sets${\displaystyle \{(1,1,...,1,2)\},\{(1,1,...,1)\}}$cada uno con cardinalidad 1.

Siguiendo la misma lógica que antes, al sumar la cardinalidad de cada conjunto vemos que

${\displaystyle F_{n+2}=F_{n}+F_{n-1}+...+|\{(1,1,...,1,2)\}|+|\{(1,1,...,1)\}|}$

... donde los dos últimos términos tienen el valor${\displaystyle F_{1}=1}$De esto se deduce que${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$.

Un argumento similar, agrupando las sumas por la posición del primer  1 en lugar del primer  2, da dos identidades más: $${\displaystyle \sum _{i=0}^{n-1}F_{2i+1}=F_{2n}}$$ y $${\displaystyle \sum _{i=1}^{n}F_{2i}=F_{2n+1}-1.}$$ En palabras, la suma de los primeros números de Fibonacci con índice impar hasta${\displaystyle F_{2n-1}}$es el (2 n ) -ésimo número de Fibonacci, y la suma de los primeros números de Fibonacci con índice par hasta${\displaystyle F_{2n}}$es el (2 n + 1) -ésimo número de Fibonacci menos  1. ^{[ 34 ]}

Se puede utilizar otro truco para demostrarlo. $${\displaystyle \sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}}$$ o en palabras, la suma de los cuadrados de los primeros números de Fibonacci hasta${\displaystyle F_{n}}$es el producto de los números de Fibonacci n -ésimo y ( n + 1) -ésimo. Para ver esto, comencemos con un rectángulo de Fibonacci de tamaño${\displaystyle F_{n}\times F_{n+1}}$y descomponerlo en cuadrados de tamaño${\displaystyle F_{n},F_{n-1},...,F_{1}}$; a partir de esto, la identidad se deduce comparando áreas:

Las identidades de Fibonacci a menudo se pueden demostrar fácilmente utilizando la inducción matemática .

Por ejemplo, reconsiderar $${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1.}$$ Agregar${\displaystyle F_{n+1}}$a ambas partes da

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

y así tenemos la fórmula para${\displaystyle n+1}$$${\displaystyle \sum _{i=1}^{n+1}F_{i}=F_{n+3}-1}$$

De manera similar, agregue${\displaystyle {F_{n+1}}^{2}}$a ambos lados de $${\displaystyle \sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}}$$ dar $${\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}}$$

La fórmula de Binet es $${\displaystyle {\sqrt {5}}F_{n}=\varphi ^{n}-\psi ^{n}.}$$ Esto puede utilizarse para demostrar identidades de Fibonacci.

Por ejemplo, para demostrar que${\textstyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$ tenga en cuenta que el lado izquierdo multiplicado por${\displaystyle {\sqrt {5}}}$se convierte $${\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}}}$$ según sea necesario, utilizando los hechos.${\textstyle \varphi \psi =-1}$y${\textstyle \varphi -\psi ={\sqrt {5}}}$para simplificar las ecuaciones.

La identidad de Cassini afirma que $${\displaystyle F_{n}^{2}-F_{n+1}F_{n-1}=(-1)^{n-1}}$$ La identidad catalana es una generalización: $${\displaystyle F_{n}^{2}-F_{n+r}F_{n-r}=(-1)^{n-r}F_{r}^{2}}$$

$${\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}}$$ donde L _n es el n - ésimo número de Lucas . El último es una identidad para duplicar n ; otras identidades de este tipo son $${\displaystyle F_{3n}=2F_{n}^{3}+3F_{n}F_{n+1}F_{n-1}=5F_{n}^{3}+3(-1)^{n}F_{n}}$$ por la identidad de Cassini.

$${\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}+3F_{n+1}^{2}F_{n}+F_{n}^{3}}$$$${\displaystyle F_{4n}=4F_{n}F_{n+1}\left(F_{n+1}^{2}+2F_{n}^{2}\right)-3F_{n}^{2}\left(F_{n}^{2}+2F_{n+1}^{2}\right)}$$ These can be found experimentally using lattice reduction, and are useful in setting up the special number field sieve to factorize a Fibonacci number.

More generally,^[35]

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

or alternatively

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

Putting k = 2 in this formula, one gets again the formulas of the end of above section Matrix form.

The ordinary generating function of the Fibonacci sequence is the power series

$${\displaystyle s(z)=\sum _{k=0}^{\infty }F_{k}z^{k}=0+z+z^{2}+2z^{3}+3z^{4}+5z^{5}+\cdots .}$$

This series is convergent for any complex number${\displaystyle z}$ satisfying ${\displaystyle |z|<1/\varphi \approx 0.618,}$ and its sum has a simple closed form:^[36]

$${\displaystyle s(z)={\frac {z}{1-z-z^{2}}}.}$$

This can be proved by multiplying by ${\textstyle (1-z-z^{2})}$: $${\displaystyle {\begin{aligned}(1-z-z^{2})s(z)&=\sum _{k=0}^{\infty }F_{k}z^{k}-\sum _{k=0}^{\infty }F_{k}z^{k+1}-\sum _{k=0}^{\infty }F_{k}z^{k+2}\\&=\sum _{k=0}^{\infty }F_{k}z^{k}-\sum _{k=1}^{\infty }F_{k-1}z^{k}-\sum _{k=2}^{\infty }F_{k-2}z^{k}\\&=0z^{0}+1z^{1}-0z^{1}+\sum _{k=2}^{\infty }(F_{k}-F_{k-1}-F_{k-2})z^{k}\\&=z,\end{aligned}}}$$ where all terms involving ${\displaystyle z^{k}}$ for ${\displaystyle k\geq 2}$ cancel out because of the defining Fibonacci recurrence relation.

Using ${\displaystyle z={10}^{-n}}$ lays out the Fibonacci numbers through the second-last number with ${\displaystyle n}$ digits in the decimal expansion of ${\displaystyle s(z)}$. For example, $${\displaystyle s(10^{-3})={\frac {0.001}{0.998999}}={\frac {1000}{998999}}=000.\,001\,001\,002\,003\,005\,008\,013\,\ldots .}$$

The partial fraction decomposition is given by $${\displaystyle s(z)={\frac {1}{\sqrt {5}}}\left({\frac {1}{1-\varphi z}}-{\frac {1}{1-\psi z}}\right)}$$ where ${\textstyle \varphi ={\tfrac {1}{2}}\left(1+{\sqrt {5}}\right)}$ is the golden ratio and ${\displaystyle \psi ={\tfrac {1}{2}}\left(1-{\sqrt {5}}\right)}$ is its conjugate.

The exponential generating function of the Fibonacci sequence may also be derived from the recurrence relation, giving a homogeneouslinear differential equation: $${\displaystyle {\begin{aligned}\sum _{k=0}^{\infty }F_{k+2}{\frac {x^{k}}{k!}}={}&\sum _{k=0}^{\infty }F_{k+1}{\frac {x^{k}}{k!}}+\sum _{k=0}^{\infty }F_{k}{\frac {x^{k}}{k!}}\\F^{\prime \prime }(x)={}&F^{\prime }(x)+F(x)\end{aligned}}}$$ The characteristic polynomial of this equation is ${\textstyle r^{2}=r+1}$, to which the solutions are exactly the golden ratio${\textstyle \varphi }$ and its conjugate${\textstyle \psi }$. Combined with the initial values ${\textstyle F_{0}=F(0)=0}$ and ${\textstyle F_{1}=F^{\prime }(0)=1}$, the exponential generating function of the Fibonacci numbers is given by the entire function$${\displaystyle F(x)={\frac {e^{\varphi x}-e^{\psi x}}{\sqrt {5}}}}$$ Evaluating the derivatives of the exponential generating function at ${\textstyle x=0}$ gives Binet's formula: $${\displaystyle F^{(n)}(0)=F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}}}$$

Every third number of the sequence is even (a multiple of ⁠${\displaystyle F_{3}=2}$⁠) and, more generally, every ⁠${\displaystyle k}$⁠-th number of the sequence is a multiple of ⁠${\displaystyle F_{k}}$⁠. Thus the Fibonacci sequence is an example of a divisibility sequence. In fact, the Fibonacci sequence satisfies the stronger divisibility property^[41][42]$${\displaystyle \gcd(F_{a},F_{b},F_{c},\ldots )=F_{\gcd(a,b,c,\ldots )}\,}$$ where gcd is the greatest common divisor function. (This relation is different if a different indexing convention is used, such as the one that starts the sequence with ⁠${\displaystyle F_{0}=1}$⁠ and ⁠${\displaystyle F_{1}=1}$⁠.)

In particular, any three consecutive Fibonacci numbers are pairwise coprime because both ${\displaystyle F_{1}=1}$ and ⁠${\displaystyle F_{2}=1}$⁠. That is, $${\displaystyle \gcd(F_{n},F_{n+1})=\gcd(F_{n},F_{n+2})=\gcd(F_{n+1},F_{n+2})=1}$$ for every n.

Every prime numberp divides a Fibonacci number that can be determined by the value of pmodulo 5. If p is congruent to 1 or 4 modulo 5, then p divides F_p−1, and if p is congruent to 2 or 3 modulo 5, then, p divides F_p+1. The remaining case is that p = 5, and in this case p divides F_p.

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

These cases can be combined into a single, non-piecewise formula, using the Legendre symbol:^[43]$${\displaystyle p\mid F_{p\,-~\!\left({\frac {5}{p}}\right)}.}$$

The above formula can be used as a primality test in the sense that if $${\displaystyle n\mid F_{n\,-~\!\left({\frac {5}{n}}\right)},}$$ where the Legendre symbol has been replaced by the Jacobi symbol, then this is evidence that n is a prime, and if it fails to hold, then n is definitely not a prime. If n is composite and satisfies the formula, then n is a Fibonacci pseudoprime. When m is large –say a 500-bit number –then we can calculate F_m (mod n) efficiently using the matrix form. Thus

$${\displaystyle {\begin{pmatrix}F_{m+1}&F_{m}\\F_{m}&F_{m-1}\end{pmatrix}}\equiv {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{m}{\pmod {n}}.}$$ Here the matrix power A^m is calculated using modular exponentiation, which can be adapted to matrices.^[44]

A Fibonacci prime is a Fibonacci number that is prime. The first few are:^[45]

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

Fibonacci primes with thousands of digits have been found, but it is not known whether there are infinitely many.^[46]

F_kn is divisible by F_n, so, apart from F₄ = 3, any Fibonacci prime must have a prime index. As there are arbitrarily long runs of composite numbers, there are therefore also arbitrarily long runs of composite Fibonacci numbers.

No Fibonacci number greater than F₆ = 8 is one greater or one less than a prime number.^[47]

The only nontrivial square Fibonacci number is 144.^[48] Attila Pethő proved in 2001 that there is only a finite number of perfect power Fibonacci numbers.^[49] In 2006, Y. Bugeaud, M. Mignotte, and S. Siksek proved that 8 and 144 are the only such non-trivial perfect powers.^[50]

The only triangular Fibonacci numbers are 1, 3, 21, and 55, which was conjectured by Vern Hoggatt and proved by Luo Ming.^[51]

No Fibonacci number can be a perfect number.^[52] More generally, no Fibonacci number other than 1 can be multiply perfect,^[53] and no ratio of two Fibonacci numbers can be perfect.^[54]

With the exceptions of 1, 8 and 144 (F₁ = F₂, F₆ and F₁₂) every Fibonacci number has a prime factor that is not a factor of any smaller Fibonacci number (Carmichael's theorem).^[55] As a result, 8 and 144 (F₆ and F₁₂) are the only Fibonacci numbers that are the product of other Fibonacci numbers.^[56]

The divisibility of Fibonacci numbers by a prime p is related to the Legendre symbol${\displaystyle {\bigl (}{\tfrac {p}{5}}{\bigr )}}$ which is evaluated as follows: $${\displaystyle \left({\frac {p}{5}}\right)={\begin{cases}0&{\text{if }}p=5\\1&{\text{if }}p\equiv \pm 1{\pmod {5}}\\-1&{\text{if }}p\equiv \pm 2{\pmod {5}}.\end{cases}}}$$

If p is a prime number then $${\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}}.}$$^[57][58]

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