Полиномы Фибоначчи - Fibonacci polynomials

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

Определение

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

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

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

${\displaystyle F_{0}(x)=0\,}$

${\displaystyle F_{1}(x)=1\,}$

${\displaystyle F_{2}(x)=x\,}$

${\displaystyle F_{3}(x)=x^{2}+1\,}$

${\displaystyle F_{4}(x)=x^{3}+2x\,}$

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

${\displaystyle F_{6}(x)=x^{5}+4x^{3}+3x\,}$

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

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

${\displaystyle L_{0}(x)=2\,}$

${\displaystyle L_{1}(x)=x\,}$

${\displaystyle L_{2}(x)=x^{2}+2\,}$

${\displaystyle L_{3}(x)=x^{3}+3x\,}$

${\displaystyle L_{4}(x)=x^{4}+4x^{2}+2\,}$

${\displaystyle L_{5}(x)=x^{5}+5x^{3}+5x\,}$

${\displaystyle L_{6}(x)=x^{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_{n}(x)=U_{n}(x,-1),\,}$

${\displaystyle L_{n}(x)=V_{n}(x,-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(n,k)={\binom {\tfrac {n+k-1}{2}}{k}}}$

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

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

1. Бенджамин и Куинн стр. 141
2. Бенджамин и Куинн стр. 142
3. Вайсштейн, Эрик В. «Многочлен Фибоначчи». MathWorld.
4. Springer

• Бенджамин, Артур Т.; Куинн, Дженнифер Дж. (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 (Треугольник коэффициентов многочленов Фибоначчи)