Свойства трёхмерной последовательности Фибоначчи

Докажем следующие две теоремы:

1. Все числа аддитивной тройки попарно взаимно просты.

2. Любая аддитивная тройка со взаимно простыми компонентами входит в трёхмерную последовательность Фибоначчи, причём ровно один раз.

Доказательство (Теорема 1). Посчитаем наибольший общий делитель любых двух чисел в такой тройке. По алгоритму Евклида, он равен наибольшему общему делителю в предыдущей аддитивной тройке, из которой была образована данная. Так как все такие тройки, в конечном итоге, образуются из простейших троек, в которых любые два числа взаимно просты, то в любой тройке все числа попарно взаимно просты. Теорема доказана.

Доказательство (Теорема 2). Разобьём теорему на два утверждения. Первое утверждение: «Никакая тройка в последовательности не встретится дважды». Второе утверждение: «Любая аддитивная тройка со взаимно простыми компонентами входит в трёхмерную последовательность Фибоначчи».

Обозначим за отношение между двумя числами, сумма которых образует третье число аддитивной тройки (для удобства отношения можно брать циклически, например, если сумма стоит на втором месте в тройке, то берётся отношение третьего числа к первому; а если сумма стоит на первом месте, то рассматривается отношение второго числа к третьему). Так как числа аддитивной тройки попарно взаимно просты, то λ можно считать несократимой дробью. Для конкретной тройки M_a[b] известен номер множества, в котором она содержится, значит, можно сказать, на каком месте в тройке стоит сумма. Следовательно (так как числа взаимно просты), из несократимой дроби  можно восстановить исходную тройку. Поэтому далее вместо аддитивных троек мы для удобства доказательства будем писать лишь число λ. Ясно, что если было выписано число λ, то в более нижних рядах будут выписаны числа  и . Теперь докажем исходные утверждения. Понятно, что производная «первым способом», то есть f(λ) даёт тройку ( ), а вторым способом, то есть g(λ), даёт тройку ( ). Зная такое число, можно определить (с учётом приведенных неравенств), с помощью какой производной оно было образовано. Действительно, если λ<1, то она образована с помощью первой производной, если λ>1, то с помощью второй. Если λ=1, то эта тройка – простейшая. Итак, для каждой аддитивной тройки мы однозначно восстанавливаем её первообразные вплоть до простейшей тройки. Если бы встретились две одинаковые тройки, то они, с учётом приведенных рассуждений, были бы образованы от одной простейшей, и стояли бы в одном множестве, а значит, совпадали. Поэтому такое невозможно. Первое утверждение доказано. С другой стороны, чтобы доказать второе утверждение, достаточно рассмотреть произвольную дробь  и показать, что с помощью приведенных выше преобразований можно получить эту дробь из единицы. Это нетрудно сделать, используя алгоритм Евклида. Если дробь больше единицы, отнимем от неё единицу. Если меньше, то разделим единицу на эту дробь. Так как числа в дроби взаимно просты, то бесконечно такие преобразования выполнять нельзя, поэтому рано или поздно мы придём к единице, а значит, такое число (и соответствующая ему аддитивная тройка) будет содержаться в 3-х мерной последовательности Фибоначчи.

Теорема доказана.