The Fibonacci sequence
0, 1, 1, 2, 3, 5, 8, 13, …
is defined by u0 = 0, u1 = 1, and un = un−1 + un−2 for . There are many elementary formulae relating the various un, most of which, since the sequence is defined inductively, are themselves usually proved by induction.