Обобщенные числа Фибоначчи

Мы рассмотрели на предыдущей странице нашего Музея важный математический объект, называемый Треугольником Паскаля. А теперь проделаем некоторые "манипуляции" над Треугольником Паскаля. Сдвинем каждый ряд Треугольника Паскаля на один столбец вправо относительно предыдущего ряда. В результате такого преобразования мы получим следующую числовую таблицу, называемую 1-Треугольником Паскаля.

1-Треугольник Паскаля

111111111111
       12345678910
       1361015212836
       1410203556
       151535
       16
1123581321345589144

Очень просто доказать, что сумма биномиальных коэффициентов в n-м столбце 1-Треугольника Паскаля равен числу Фибоначчи Fn+1. Это означает, что если мы будем двигаться вдоль нижнего ряда 1-Треугольника Паскаля, начиная с 0-го столбца, мы получим ряд Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, ...!

И далее, если мы сдвинем исходный Треугольник Паскаля на p столбцов вправо относительно предыдущего ряда (p = 0, 1, 2, 3, ... ), мы получим числовую таблицу, называемую p-Треугольником Паскаля. Ясно, что 0-треугольник Паскаля, то есть p-Треугольник Паскаля, соответствующий p = 0, есть ни что иное, как исходный Треугольник Паскаля. Например, p-Треугольники Паскаля, соответствующие p = 2 и p = 3, имеют следующий вид соответственно:

2-Треугольник Паскаля

1111111111111
       12345678910
       13610152128
       141020
       1
111234691319284160

3-Треугольник Паскаля

1111111111111
       123456789
       1361015
       1
11112345710141926

Суммируя биномиальные коэффициенты в столбцах 2- и 3-Треугольника Паскаля, мы получим две новые числовые последовательности, имеющие следующие свойства: n-й член последовательности

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, ...

начиная с n = 4 равен сумме (n-1)-го и (n-3)-го членов, а n-й член последовательности

1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, ...

начиная с n = 5 равен сумме (n-1)-го и (n-4)-го членов.

Эти примеры дают нам право ввести следующее определение.

Определение.
Для заданного p = 0, 1, 2, 3, ... числовые последовательности Fp(n), задаваемые следующим рекуррентным соотношением
Fp(n) = Fp(n-1) + Fp(n-p-1)   c   n>p+1;(1)
Fp(1) = Fp(2) = ... = Fp(p+1) = 1(2)

называются p-числами Фибоначчи. Мы можем увидеть из p-Треугольника Паскаля, что сумма биномиальных коэффициентов n-го столбца p-Треугольника Паскаля равна p-числу Фибоначчи Fp(n+1).

Таким образом, мы обнаружили бесконечное количество новых числовых последовательностей, состоящих из p-чисел Фибоначчи (p = 0, 1, 2, 3, ...). Эти числовые последовательности включают в себя двоичную последовательность (p = 0) и классические числа Фибоначчи (p = 1).