Несколько дней назад слушал доклад Тома Кемптона (Tom Kempton), и утащил оттуда красивую байку про числа Фибоначчи (хотя доклад был о более сложных вещах, конечно).

Давайте возьмём золотое сечение φ; оно удовлетворяет уравнению φ^2=φ+1.

Посмотрим на множество чисел вида a+bφ, где a и b целые (иными словами, на кольцо Z[φ]). Поскольку φ удовлетворяет уравнению φ^2=φ+1, на этом множестве действует умножение на φ:
φ(a+bφ) = b + (a+b) φ.
В частности, в координатах (a,b) это линейное преобразование. Причём то самое, которое переводит (F_{n-1},F_n) в (F_n,F_{n+1}).
(В частности, отсюда легко увидеть, что φ^n = F_{n-1} + F_n φ.)