Теоретико-числовые свойства чисел Фибоначчи

Введем обозначение Фактически, задача свелась к доказательству того, что для всех Проведем доказательство по индукции по парам чисел База индукции тривиальна для всех Теперь допустим, что для всех где , кроме пары утверждение уже доказано; покажем утверждение для Для этого снова вспомним тождество

С помощью него получим, что

Поскольку по предположению индукции и получаем что и что и требовалось доказать.