Многочлены Фибоначчи - Википедия - Fibonacci polynomials

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

Определение

Эти Фибоначчи многочлены определяются отношение повторения:^[1]

${ displaystyle F_ {n} (x) = { begin {case} 0, & { mbox {if}} n = 0 1, & { mbox {if}} n = 1 xF_ {n -1} (x) + F_ {n-2} (x), & { mbox {if}} n geq 2 end {case}}}$

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

${ Displaystyle F_ {0} (х) = 0 ,}$

${ Displaystyle F_ {1} (х) = 1 ,}$

${ Displaystyle F_ {2} (х) = х ,}$

${ Displaystyle F_ {3} (х) = х ^ {2} +1 ,}$

${ Displaystyle F_ {4} (х) = х ^ {3} + 2x ,}$

${ Displaystyle F_ {5} (х) = х ^ {4} + 3x ^ {2} +1 ,}$

${ Displaystyle F_ {6} (х) = х ^ {5} + 4x ^ {3} + 3x ,}$

Многочлены Лукаса используют одно и то же повторение с разными начальными значениями:^[2]${ displaystyle L_ {n} (x) = { begin {case} 2, & { mbox {if}} n = 0 x, & { mbox {if}} n = 1 xL_ {n -1} (x) + L_ {n-2} (x), & { mbox {if}} n geq 2. end {case}}}$

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

${ Displaystyle L_ {0} (х) = 2 ,}$

${ Displaystyle L_ {1} (х) = х ,}$

${ Displaystyle L_ {2} (х) = х ^ {2} +2 ,}$

${ Displaystyle L_ {3} (х) = х ^ {3} + 3x ,}$

${ Displaystyle L_ {4} (х) = х ^ {4} + 4x ^ {2} +2 ,}$

${ Displaystyle L_ {5} (х) = х ^ {5} + 5x ^ {3} + 5x ,}$

${ Displaystyle L_ {6} (х) = х ^ {6} + 6x ^ {4} + 9x ^ {2} +2. ,}$

Числа Фибоначчи и Люка восстанавливаются путем вычисления многочленов в Икс = 1; Числа Пелла восстанавливаются путем оценки F_п в Икс = 2. Степени F_п является п - 1 и степень L_п является п. В обычная производящая функция для последовательностей:^[3]

${ displaystyle sum _ {n = 0} ^ { infty} F_ {n} (x) t ^ {n} = { frac {t} {1-xt-t ^ {2}}}}$

${ displaystyle sum _ {n = 0} ^ { infty} L_ {n} (x) t ^ {n} = { frac {2-xt} {1-xt-t ^ {2}}}. }$

Многочлены могут быть выражены через Последовательности Лукаса в качестве

${ Displaystyle F_ {п} (х) = U_ {п} (х, -1), ,}$

${ Displaystyle L_ {п} (х) = V_ {п} (х, -1). ,}$

Идентичности

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

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

${ Displaystyle F _ {- n} (x) = (- 1) ^ {n-1} F_ {n} (x), , L _ {- n} (x) = (- 1) ^ {n} L_ {n} (x).}$

Другие личности включают:^[4]

${ Displaystyle F_ {m + n} (x) = F_ {m + 1} (x) F_ {n} (x) + F_ {m} (x) F_ {n-1} (x) ,}$

${ Displaystyle L_ {m + n} (x) = L_ {m} (x) L_ {n} (x) - (- 1) ^ {n} L_ {m-n} (x) ,}$

${ Displaystyle F_ {n + 1} (x) F_ {n-1} (x) -F_ {n} (x) ^ {2} = (- 1) ^ {n} ,}$

${ Displaystyle F_ {2n} (x) = F_ {n} (x) L_ {n} (x). ,}$

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

${ displaystyle F_ {n} (x) = { frac { alpha (x) ^ {n} - beta (x) ^ {n}} { alpha (x) - beta (x)}}, , L_ {n} (x) = alpha (x) ^ {n} + beta (x) ^ {n},}$

куда

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

решения (в т) из

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

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

${ displaystyle x ^ {n} = F_ {n + 1} (x) + sum _ {k = 1} ^ { lfloor n / 2 rfloor} (- 1) ^ {k} left [{ binom {n} {k}} - { binom {n} {k-1}} right] F_ {n + 1-2k} (x).}$

Например,

${ displaystyle x ^ {4} = F_ {5} (x) -3F_ {3} (x) + 2F_ {1} (x) ,}$

${ displaystyle x ^ {5} = F_ {6} (x) -4F_ {4} (x) + 5F_ {2} (x) ,}$

${ displaystyle x ^ {6} = F_ {7} (x) -5F_ {5} (x) + 9F_ {3} (x) -5F_ {1} (x) ,}$

${ displaystyle x ^ {7} = F_ {8} (x) -6F_ {6} (x) + 14F_ {4} (x) -14F_ {2} (x) ,}$

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

Комбинаторная интерпретация

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

Если F(п,k) - коэффициент при Икс^k в F_п(Икс), так

${ Displaystyle F_ {n} (x) = sum _ {k = 0} ^ {n} F (n, k) x ^ {k}, ,}$

тогда F(п,k) - количество способов п−1 на 1 прямоугольник можно выложить плиткой 2 на 1 домино и квадратов 1 на 1 так, чтобы ровно k квадраты используются.^[1] Эквивалентно, F(п,k) - количество способов написания п−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(п,k) равно биномиальный коэффициент

${ Displaystyle F (п, к) = { binom { tfrac {п + к-1} {2}} {к}}}$

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

Рекомендации

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

дальнейшее чтение

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

внешняя ссылка

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