Треугольник Хосоя

Треугольник Фибоначчи или треугольник Хосойя — это треугольник, составленный из чисел (подобно треугольнику Паскаля) на основе чисел Фибоначчи. Каждое число является суммой двух чисел выше по левой или правой диагонали. Первые несколько строк треугольника:

                                                1
                                             1     1
                                          2     1     2
                                       3     2     2     3
                                    5     3     4     3     5
                                 8     5     6     6     5     8
                             13     8    10     9    10     8    13
                          21    13    16    15    15    16    13    21
                       34    21    26    24    25    24    26    21    34
                    55    34    42    39    40    40    39    42    34    55
                 89    55    68    63    65    64    65    63    68    55    89
             144    89   110   102   105   104   104   105   102   110    89   144
                                              И т.д.

(См. последовательность A058071 в OEIS).

Название

Предпочтительным является название «треугольник Хосоя», в честь японского химика и математика Харуо Хосоя, который первым предложил такой треугольник в 1976 году. Использование названия «треугольник Фибоначчи» может привести к двусмысленности, так как оно использовалось для обозначения других математических объектов в более поздних работах.

Рекуррентное соотношение

Числа в этом треугольнике удовлетворяют рекуррентным формулам

H(0, 0) = H(1, 0) = H(1, 1) = H(2, 1) = 1

и

H(n, j) = H(n − 1, j) + H(n − 2, j)

= H(n − 1, j − 1) + H(n − 2, j − 2).

Связь с числами Фибоначчи

Элементы треугольника удовлетворяют тождеству

H(n, i) = F(i + 1) × F(n − i + 1).

Две крайние диагонали являются числами Фибоначчи, числа же в среднем вертикальном столбце являются квадратами чисел Фибоначчи. Все другие числа треугольника представляются в виде произведения двух различных чисел Фибоначчи, больших 1. Суммы по строкам треугольника дают элементы свёрнутой последовательности Фибоначчи.