Editing Fibonacci sequence (section)

== Other identities ==
Numerous other identities can be derived using various methods. Here are some of them:<ref name="MathWorld">{{MathWorld|urlname=FibonacciNumber |title=Fibonacci Number|mode=cs2}}</ref>

=== Cassini's and Catalan's identities ===
{{Main|Cassini and Catalan identities}}
Cassini's identity states that
<math display=block>{F_n}^2 - F_{n+1}F_{n-1} = (-1)^{n-1}</math>
Catalan's identity is a generalization:
<math display=block>{F_n}^2 - F_{n+r}F_{n-r} = (-1)^{n-r}{F_r}^2</math>

=== d'Ocagne's identity ===
<math display=block>F_m F_{n+1} - F_{m+1} F_n = (-1)^n F_{m-n}</math>
<math display=block>F_{2 n} = {F_{n+1}}^2 - {F_{n-1}}^2 = F_n \left (F_{n+1}+F_{n-1} \right ) = F_nL_n</math>
where {{math|''L''<sub>''n''</sub>}} is the {{mvar|n}}-th [[Lucas number]]. The last is an identity for doubling {{mvar|n}}; other identities of this type are
<math display=block>F_{3 n} = 2{F_n}^3 + 3 F_n F_{n+1} F_{n-1} = 5{F_n}^3 + 3 (-1)^n F_n</math>
by Cassini's identity.

<math display=block>F_{3 n+1} = {F_{n+1}}^3 + 3 F_{n+1}{F_n}^2 - {F_n}^3</math>
<math display=block>F_{3 n+2} = {F_{n+1}}^3 + 3 {F_{n+1}}^2 F_n + {F_n}^3</math>
<math display=block>F_{4 n} = 4 F_n F_{n+1} \left ({F_{n+1}}^2 + 2{F_n}^2 \right ) - 3{F_n}^2 \left ({F_n}^2 + 2{F_{n+1}}^2 \right )</math>
These can be found experimentally using [[lattice reduction]], and are useful in setting up the [[special number field sieve]] to [[Factorization|factorize]] a Fibonacci number.

More generally,<ref name="MathWorld" />

<math display=block>F_{k n+c} = \sum_{i=0}^k \binom k i F_{c-i} {F_n}^i {F_{n+1}}^{k-i}.</math>

or alternatively

<math display=block>F_{k n+c} = \sum_{i=0}^k \binom k i F_{c+i} {F_n}^i {F_{n-1}}^{k-i}.</math>

Putting {{math|1=''k'' = 2}} in this formula, one gets again the formulas of the end of above section [[#Matrix form|Matrix form]].