✳flâneur — a map of the web's best reading

Fibonacci Numbers - Algorithms for Competitive Programming

cp-algorithms.com · 1,694 words · saved by 1 readers

This can be proved by induction. A one-line proof by Knuth comes from taking the determinant of the 2x2 matrix form below. From this we can prove by induction that for any positive integer     𝑘 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math> $k$ ,     𝐹 𝑛 𝑘 <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mrow data-mjx-texclass="ORD"><mi>n</mi><mi>k</mi></mrow></msub></math> $F_{nk}$  is multiple of     𝐹 𝑛 <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>n</mi></msub></math> $F_n$ . The inverse is also true: if     𝐹 𝑚 <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>m</mi></msub></math> $F_m$  is multiple of     𝐹 𝑛 <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>n</mi></msub></math> $F_n$ , then     𝑚 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>m</mi></math> $m$  is multiple of     𝑛 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math> $n$ . GCD identi

Last update: April 22, 2025 &emsp; Translated From: e-maxx.ru Fibonacci Numbers &para; The Fibonacci sequence is defined as follows: $$F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$$ The first elements of the sequence ( OEIS A000045 ) are: $$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...$$ Properties &para; Fibonacci numbers possess a lot of interesting properties. Here are a few of them: Cassini's identity: $$F_{n-1} F_{n+1} - F_n^2 = (-1)^n$$ This can be proved by induction. A one-line proof by Knuth comes from taking the determinant of the 2x2 matrix form below. The "addition" rule: $$F_{n+k} = F

Explore this link on the map →

saved by

related reading