Многочлены Фибоначчи

В математике многочлены Фибоначчи представляют собой последовательность полиномов, которое можно рассматривать как обобщение чисел Фибоначчи. Полиномы, сгенерированные аналогичным образом из чисел Люка, называются полиномами Люка .

• 1 Определение
• 2 Тождества
• 3 Комбинаторная интерпретация
• 4 Ссылки
• 5 Дополнительная литература
• 6 Внешние ссылки

Эти полиномы Фибоначчи определяются рекуррентным соотношением :

$F\; n\; (x)\; =\; \{0,\; если\; n\; =\; 0\; 1,\; если\; n\; =\; 1\; x\; F\; n\; -\; 1\; (x)\; +\; F\; n\; -\; 2\; (x),\; если\; n\; \ge \; 2\; \{\backslash \; displaystyle\; F\_\; \{n\}\; (x)\; =\; \{\backslash \; begin\; \{cases\}\; 0,\; \{\backslash \; t\_dv\; \{if\}\}\; n\; =\; 0\; \backslash \backslash \; 1,\; \{\backslash \; t\_dv\; \{if\}\}\; n\; =\; 1\; \backslash \backslash \; xF\_\; \{n-1\}\; (x)\; +\; F\_\; \{n-2\}\; (x),\; \{\backslash \; t\_dv\; \{if\}\}\; n\; \backslash \; geq\; 2\; \backslash \; end\; \{cases\}\}\}$

Первые несколько полиномов Фибоначчи:

$F\; 0\; (x)\; =\; 0\; \{\backslash \; displaystyle\; F\_\; \{0\}\; (x)\; =\; 0\; \backslash ,\}$

$F\; 1\; (x)\; =\; 1\; \{\backslash \; displaystyle\; F\_\; \{1\}\; (x)\; =\; 1\; \backslash ,\}$

$F\; 2\; (x)\; =\; x\; \{\backslash \; displaystyle\; F\_\; \{2\}\; (x)\; =\; x\; \backslash ,\}$

$F\; 3\; (x)\; =\; x\; 2\; +\; 1\; \{\backslash \; displaystyle\; F\_\; \{3\}\; (x)\; =\; x\; ^\; \{2\}\; +1\; \backslash ,\}$

$F\; 4\; (x)\; =\; x\; 3\; +\; 2\; Икс\; \{\backslash \; Displaystyle\; F\_\; \{4\}\; (х)\; =\; х\; ^\; \{3\}\; +\; 2x\; \backslash ,\}$

$F\; 5\; (х)\; =\; х\; 4\; +\; 3\; х\; 2\; +\; 1\; \{\backslash \; Displaystyle\; F\_\; \{5\}\; (х)\; =\; х\; ^\; \{4\}\; +\; 3x\; ^\; \{2\}\; +1\; \backslash ,\}$

$F\; 6\; (x)\; =\; x\; 5\; +\; 4\; x\; 3\; +\; 3\; x\; \{\backslash \; displaystyle\; F\_\; \{6\}\; (x)\; =\; x\; ^\; \{5\}\; +\; 4x\; ^\; \{3\}\; +\; 3x\; \backslash ,\}$

Многочлены Люка используют одно и то же повторение с разными начальными значениями: $L\; n\; (x)\; =\; \{\; 2,\; если\; n\; =\; 0\; x,\; если\; n\; =\; 1\; x\; L\; n\; -\; 1\; (x)\; +\; L\; n\; -\; 2\; (x),\; если\; n\; \ge \; 2.\; \{\backslash \; displaystyle\; L\_\; \{n\}\; (x)\; =\; \{\backslash \; begin\; \{cases\; \}\; 2,\; \{\backslash \; t\_dv\; \{if\}\}\; n\; =\; 0\; \backslash \backslash \; x,\; \{\backslash \; t\_dv\; \{if\}\}\; n\; =\; 1\; \backslash \backslash \; xL\_\; \{n-1\}\; (x)\; +\; L\_\; \{n-2\}\; (x),\; \{\backslash \; t\_dv\; \{if\}\}\; n\; \backslash \; geq\; 2.\; \backslash \; end\; \{cases\}\}\}$

Первые несколько полиномов Люка:

$L\; 0\; (x)\; =\; 2\; \{\backslash \; displaystyle\; L\_\; \{0\}\; (x)\; =\; 2\; \backslash ,\}$

$L\; 1\; (x)\; =\; x\; \{\backslash \; displaystyle\; L\_\; \{1\}\; (x)\; =\; x\; \backslash ,\}$

$L\; 2\; (x)\; =\; x\; 2\; +\; 2\; \{\backslash \; displaystyle\; L\_\; \{2\; \}\; (x)\; =\; x\; ^\; \{2\}\; +2\; \backslash ,\}$

$L\; 3\; (x)\; =\; x\; 3\; +\; 3\; x\; \{\backslash \; displaystyle\; L\_\; \{3\}\; (x)\; =\; x\; ^\; \{3\}\; +\; 3x\; \backslash ,\}$

$L\; 4\; (x)\; =\; x\; 4\; +\; 4\; x\; 2\; +\; 2\; \{\backslash \; displaystyle\; L\_\; \{4\}\; (x)\; =\; x\; ^\; \{4\}\; +\; 4x\; ^\; \{2\}\; +2\; \backslash ,\}$

$L\; 5\; (\; x)\; =\; x\; 5\; +\; 5\; x\; 3\; +\; 5\; x\; \{\backslash \; displaystyle\; L\_\; \{5\}\; (x)\; =\; x\; ^\; \{5\}\; +\; 5x\; ^\; \{3\}\; +\; 5x\; \backslash ,\}$

$L\; 6\; (x)\; =\; x\; 6\; +\; 6\; x\; 4\; +\; 9\; x\; 2\; +\; 2.\; \{\backslash \; displaystyle\; L\_\; \{6\}\; (x)\; =\; x\; ^\; \{6\}\; +\; 6x\; ^\; \{4\}\; +\; 9x\; ^\; \{2\}\; +2.\; \backslash ,\}$

Фибоначчи и числа Люка восстанавливаются путем вычисления многочленов при x = 1; Числа Пелля восстанавливаются путем оценки F n при x = 2. Степень F n равна n - 1, а степень L n это п. Обычная производящая функция для последовательностей:

$\sum \; n\; =\; 0\; \infty \; F\; n\; (x)\; tn\; =\; t\; 1\; -\; xt\; -\; t\; 2\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{\; \backslash \; infty\}\; F\_\; \{n\}\; (x)\; t\; ^\; \{n\}\; =\; \{\backslash \; frac\; \{t\}\; \{1-xt-t\; ^\; \{2\}\}\}\}$

$\sum \; n\; =\; 0\; \infty \; L\; n\; (x)\; tn\; =\; 2\; -\; xt\; 1\; -\; xt\; -\; t\; 2.\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{\backslash \; infty\}\; L\_\; \{n\}\; (x)\; t\; ^\; \{n\}\; =\; \{\backslash \; frac\; \{2-xt\}\; \{1-xt-t\; ^\; \{2\}\}\}.\; \}$

Многочлены могут быть выражены в терминах последовательностей Люка как

$F\; n\; (x)\; =\; U\; n\; (x,\; -\; 1),\; \{\backslash \; displaystyle\; F\_\; \{n\}\; (x)\; =\; U\_\; \{n\}\; (x,\; -1),\; \backslash ,\}$

$L\; n\; (x)\; =\; V\; n\; (x,\; -\; 1).\; \{\backslash \; displaystyle\; L\_\; \{n\}\; (x)\; =\; V\_\; \{n\}\; (x,\; -1).\; \backslash ,\}$

Как частные случаи последовательностей Люка, многочлены Фибоначчи удовлетворяют ряду тождеств.

Во-первых, они могут быть определены для отрицательных индексов как

$F\; -\; n\; (x)\; =\; (-\; 1)\; n\; -\; 1\; F\; n\; (x),\; L\; -\; n\; (x)\; =\; (-\; 1)\; n\; L\; n\; (х).\; \{\backslash \; Displaystyle\; F\; \_\; \{-\; n\}\; (x)\; =\; (-\; 1)\; ^\; \{n-1\}\; F\_\; \{n\}\; (x),\; \backslash ,\; L\; \_\; \{-\; n\}\; (x)\; =\; (-\; 1)\; ^\; \{n\}\; L\_\; \{n\}\; (x).\}$

Другие тождества включают:

$F\; m\; +\; n\; (x)\; =\; F\; m\; +\; 1\; (x)\; F\; n\; (x)\; +\; F\; m\; (x)\; F\; n\; -\; 1\; (x)\; \{\backslash \; Displaystyle\; F\_\; \{m\; +\; n\}\; (x)\; =\; F\_\; \{m\; +\; 1\}\; (x)\; F\_\; \{n\}\; (x)\; +\; F\_\; \{m\}\; (x)\; F\_\; \{n-1\}\; (x)\; \backslash ,\}$

$L\; м\; +\; N\; (Икс)\; знак\; равно\; L\; м\; (Икс)\; L\; N\; (Икс)\; -\; (-\; 1)\; N\; L\; м\; -\; N\; (Икс)\; \{\backslash \; Displaystyle\; L\_\; \{м\; +\; п\}\; (х)\; =\; L\_\; \{м\; \}\; (x)\; L\_\; \{n\}\; (x)\; -\; (-\; 1)\; ^\; \{n\}\; L\_\; \{mn\}\; (x)\; \backslash ,\}$

$F\; n\; +\; 1\; (x)\; F\; n\; -\; 1\; (x)\; -\; F\; n\; (х)\; 2\; =\; (-\; 1)\; n\; \{\backslash \; displaystyle\; F\_\; \{n\; +\; 1\}\; (x)\; F\_\; \{n-1\}\; (x)\; -F\_\; \{n\}\; (x)\; ^\; \{2\}\; =\; (-\; 1)\; ^\; \{\; n\}\; \backslash ,\}$

$F\; 2\; n\; (x)\; =\; F\; n\; (x)\; L\; n\; (x).\; \{\backslash \; displaystyle\; F\_\; \{2n\}\; (x)\; =\; F\_\; \{n\}\; (x)\; L\_\; \{n\}\; (x).\; \backslash ,\}$

Выражения в закрытой форме, похожие на формулу Бине:

$F\; n\; (x)\; знак\; равно\; \alpha \; (Икс)\; N\; -\; \beta \; (Икс)\; N\; \alpha \; (Икс)\; -\; \beta \; (Икс),\; L\; N\; (Икс)\; =\; \alpha \; (Икс)\; N\; +\; \beta \; (Икс)\; N,\; \{\backslash \; Displaystyle\; F\_\; \{п\}\; (х)\; =\; \{\backslash \; frac\; \{\backslash \; alpha\; (x)\; ^\; \{n\}\; -\; \backslash \; beta\; (x)\; ^\; \{n\}\}\; \{\backslash \; alpha\; (x)\; -\; \backslash \; beta\; (x)\}\},\; \backslash ,\; L\_\; \{n\}\; (x)\; =\; \backslash \; alpha\; (x)\; ^\; \{n\}\; +\; \backslash \; beta\; (x)\; ^\; \{n\},\}$

где

$\alpha \; (x)\; =\; x\; +\; x\; 2\; +\; 4\; 2,\; \beta \; (x)\; =\; x\; -\; x\; 2\; +\; 4\; 2\; \{\backslash \; displaystyle\; \backslash \; alpha\; (x)\; =\; \{\backslash \; frac\; \{x\; +\; \{\backslash \; sqrt\; \{x\; ^\; \{2\}\; +4\}\}\}\; \{2\}\},\; \backslash ,\; \backslash \; beta\; (x)\; =\; \{\backslash \; frac\; \{x-\; \{\backslash \; sqrt\; \{x\; ^\; \{2\}\; +4\}\}\}\; \{2\}\}\}$

- это решения (в t) уравнения

$t\; 2\; -\; xt\; -\; 1\; =\; 0.\; \{\backslash \; displaystyle\; t\; ^\; \{2\}\; -xt-1\; =\; 0.\; \backslash ,\}$

Связь между многочленами Фибоначчи и стандартными базисными многочленами задается формулой

$xn\; =\; F\; n\; +\; 1\; (x)\; +\; \sum \; k\; =\; 1\; \lfloor \; n\; /\; 2\; \rfloor \; (\; -\; 1)\; k\; [(nk)\; -\; (nk\; -\; 1)]\; F\; n\; +\; 1\; -\; 2\; k\; (x).\; \{\backslash \; displaystyle\; x\; ^\; \{n\}\; =\; F\_\; \{n\; +\; 1\}\; (x)\; +\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{\backslash \; lfloor\; n\; /\; 2\; \backslash \; rfloor\}\; (-\; 1)\; ^\; \{k\}\; \backslash \; left\; [\{\backslash \; binom\; \{n\}\; \{k\}\}\; -\; \{\backslash \; binom\; \{n\}\; \{k-1\}\}\; \backslash \; right]\; F\_\; \{n\; +\; 1-2k\}\; (x).\}$

Например,

$x\; 4\; =\; F\; 5\; (х)\; -\; 3\; F\; 3\; (x)\; +\; 2\; F\; 1\; (x)\; \{\backslash \; displaystyle\; x\; ^\; \{4\}\; =\; F\_\; \{5\}\; (x)\; -3F\_\; \{3\}\; (x)\; +\; 2F\_\; \{1\}\; (x)\; \backslash ,\}$

$x\; 5\; =\; F\; 6\; (x)\; -\; 4\; F\; 4\; (x)\; +\; 5\; F\; 2\; (x)\; \{\backslash \; displaystyle\; x\; ^\; \{5\}\; =\; F\_\; \{6\}\; (x)\; -4F\_\; \{4\}\; (\; x)\; +\; 5F\_\; \{2\}\; (x)\; \backslash ,\}$

$x\; 6\; =\; F\; 7\; (x)\; -\; 5\; F\; 5\; (x)\; +\; 9\; F\; 3\; (x)\; -\; 5\; F\; 1\; (x)\; \{\backslash \; displaystyle\; x\; ^\; \{6\}\; =\; F\_\; \{7\}\; (x)\; -5F\_\; \{5\}\; (x)\; +\; 9F\_\; \{3\}\; (x)\; -5F\_\; \{1\}\; (x)\; \backslash ,\}$

$x\; 7\; =\; F\; 8\; (x)\; -\; 6\; F\; 6\; (x)\; +\; 14\; F\; 4\; (x)\; -\; 14\; F\; 2\; (x)\; \{\backslash \; displaystyle\; x\; ^\; \{7\}\; =\; F\_\; \{8\}\; (x)\; -6F\_\; \{6\}\; (x)\; +\; 14F\_\; \{4\}\; (\; x)\; -14F\_\; \{2\}\; (x)\; \backslash ,\}$

Доказательство этого факта дается, начиная со страницы 5 здесь.

Коэффициенты полиномов Фибоначчи могут быть считаны из Треугольник Паскаля, следующий по «неглубоким» диагоналям (показан красным). Суммы коэффициентов - это числа Фибоначчи.

Если F (n, k) является коэффициентом x в F n (x), то

$F\; n\; (x)\; =\; \sum \; k\; Знак\; равно\; 0\; N\; F\; (N,\; K)\; xk,\; \{\backslash \; Displaystyle\; F\_\; \{n\}\; (x)\; =\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{n\}\; F\; (n,\; k)\; x\; ^\; \{k\},\; \backslash ,\}$

, тогда F (n, k) - количество способов, которыми прямоугольник n − 1 на 1 может быть выложен плиткой 2 на 1 домино и 1 на 1 квадратов, так что будет использовано ровно k квадратов. Эквивалентно, F (n, k) - это количество способов записать n − 1 как упорядоченную сумму, включающую только 1 и 2, так что 1 используется ровно k раз. Например, F (6,3) = 4 и 5 можно записать 4 способами: 1 + 1 + 1 + 2, 1 + 1 + 2 + 1, 1 + 2 + 1 + 1, 2 + 1 + 1 + 1., как сумма, включающая только 1 и 2, при этом 1 используется 3 раза. Подсчитав, сколько раз 1 и 2 использовались в такой сумме, очевидно, что F (n, k) равно биномиальному коэффициенту

$F\; (n,\; k)\; =\; (n\; +\; k\; -\; 1\; 2\; k)\; \{\backslash \; displaystyle\; F\; (n,\; k)\; =\; \{\backslash \; binom\; \{\backslash \; tfrac\; \{n\; +\; k-1\}\; \{2\}\}\; \{k\}\}\}$

, когда n и k имеют противоположную четность. Это дает возможность считывать коэффициенты из треугольника Паскаля, как показано справа.

• Бенджамин, Артур Т. ; Куинн, Дженнифер Дж. (2003). «§9.4 Полином Фибоначчи и Люка». Действительно важные доказательства: искусство комбинаторного доказательства. Математические экспозиции Дольчиани. 27. Математическая ассоциация Америки. п. 141. ISBN 978-0-88385-333-7.
• Филиппу, Андреас Н. (2001) [1994], Энциклопедия математики, EMS Press
• Филиппу, Андреас Н. (2001) [1994], Энциклопедия математики, EMS Press
• Вайстейн, Эрик У. «Полином Люка». MathWorld.

• Hoggatt, V.E. ; Бикнелл, Марджори (1973). «Корни многочленов Фибоначчи». Ежеквартальный отчет Фибоначчи. 11: 271–274. ISSN 0015-0517. MR 0332645.
• Hoggatt, V.E.; Лонг, Кальвин Т. (1974). «Свойства делимости обобщенных многочленов Фибоначчи». Ежеквартальный отчет Фибоначчи. 12: 113. MR 0352034.
• Риччи, Паоло Эмилио (1995). «Обобщенные многочлены Люка и многочлены Фибоначчи». Rivista di Matematica della Università di Parma. V. Ser. 4 : 137–146. MR 1395332.
• Юань, Йи; Чжан, Вэньпэн (2002). «Некоторые тождества, включающие многочлены Фибоначчи». Ежеквартальный отчет Фибоначчи. 40 (4): 314. MR 1920571.
• Cigler, Johann (2003). «q-полиномы Фибоначчи». Ежеквартальный отчет Фибоначчи (41): 31–40. MR 1962279.

• OEISпоследовательность A162515 (Треугольник коэффициентов многочленов, определенных формой Бине)
• OEIS последовательность A011973 (Треугольник коэффициентов Фибоначчи многочлены)