В математике , то многочлены Фибоначчи являются многочленом последовательность , которую можно рассматривать как обобщение чисел Фибоначчи . Полиномы, сгенерированные аналогичным образом из чисел Люка , называются полиномами Люка .
Определение
Эти полиномы Фибоначчи определяются рекуррентным соотношением :
F
п
(
Икс
)
знак равно
{
0
,
если
п
знак равно
0
1
,
если
п
знак равно
1
Икс
F
п
-
1
(
Икс
)
+
F
п
-
2
(
Икс
)
,
если
п
≥
2
{\ 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}}}
Многочлены Лукаса используют одно и то же повторение с разными начальными значениями:
L
п
(
Икс
)
знак равно
{
2
,
если
п
знак равно
0
Икс
,
если
п
знак равно
1
Икс
L
п
-
1
(
Икс
)
+
L
п
-
2
(
Икс
)
,
если
п
≥
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}}}
Их можно определить для отрицательных показателей как
F
-
п
(
Икс
)
знак равно
(
-
1
)
п
-
1
F
п
(
Икс
)
,
{\ Displaystyle F _ {- n} (x) = (- 1) ^ {n-1} F_ {n} (x),}
L
-
п
(
Икс
)
знак равно
(
-
1
)
п
L
п
(
Икс
)
.
{\ displaystyle L _ {- n} (x) = (- 1) ^ {n} L_ {n} (x).}
Примеры
Первые несколько полиномов Фибоначчи:
F
0
(
Икс
)
знак равно
0
{\ Displaystyle F_ {0} (х) = 0 \,}
F
1
(
Икс
)
знак равно
1
{\ Displaystyle F_ {1} (х) = 1 \,}
F
2
(
Икс
)
знак равно
Икс
{\ Displaystyle F_ {2} (х) = х \,}
F
3
(
Икс
)
знак равно
Икс
2
+
1
{\ Displaystyle F_ {3} (х) = х ^ {2} +1 \,}
F
4
(
Икс
)
знак равно
Икс
3
+
2
Икс
{\ Displaystyle F_ {4} (х) = х ^ {3} + 2x \,}
F
5
(
Икс
)
знак равно
Икс
4
+
3
Икс
2
+
1
{\ Displaystyle F_ {5} (х) = х ^ {4} + 3x ^ {2} +1 \,}
F
6
(
Икс
)
знак равно
Икс
5
+
4
Икс
3
+
3
Икс
{\ Displaystyle F_ {6} (х) = х ^ {5} + 4x ^ {3} + 3x \,}
Первые несколько полиномов Лукаса:
L
0
(
Икс
)
знак равно
2
{\ Displaystyle L_ {0} (х) = 2 \,}
L
1
(
Икс
)
знак равно
Икс
{\ Displaystyle L_ {1} (х) = х \,}
L
2
(
Икс
)
знак равно
Икс
2
+
2
{\ Displaystyle L_ {2} (х) = х ^ {2} +2 \,}
L
3
(
Икс
)
знак равно
Икс
3
+
3
Икс
{\ Displaystyle L_ {3} (х) = х ^ {3} + 3x \,}
L
4
(
Икс
)
знак равно
Икс
4
+
4
Икс
2
+
2
{\ Displaystyle L_ {4} (х) = х ^ {4} + 4x ^ {2} +2 \,}
L
5
(
Икс
)
знак равно
Икс
5
+
5
Икс
3
+
5
Икс
{\ Displaystyle L_ {5} (х) = х ^ {5} + 5x ^ {3} + 5x \,}
L
6
(
Икс
)
знак равно
Икс
6
+
6
Икс
4
+
9
Икс
2
+
2.
{\ Displaystyle L_ {6} (х) = х ^ {6} + 6x ^ {4} + 9x ^ {2} +2. \,}
Характеристики
Степень F n равна n - 1, а степень L n равна n .
Числа Фибоначчи и Люка восстанавливаются путем вычисления полиномов при x = 1; Числа Пелла восстанавливаются путем вычисления F n при x = 2.
В обычные производящие функции для последовательностей являются:
∑
п
знак равно
0
∞
F
п
(
Икс
)
т
п
знак равно
т
1
-
Икс
т
-
т
2
{\ displaystyle \ sum _ {n = 0} ^ {\ infty} F_ {n} (x) t ^ {n} = {\ frac {t} {1-xt-t ^ {2}}}}
∑
п
знак равно
0
∞
L
п
(
Икс
)
т
п
знак равно
2
-
Икс
т
1
-
Икс
т
-
т
2
.
{\ displaystyle \ sum _ {n = 0} ^ {\ infty} L_ {n} (x) t ^ {n} = {\ frac {2-xt} {1-xt-t ^ {2}}}. }
Многочлены могут быть выражены в терминах последовательностей Люка как
F
п
(
Икс
)
знак равно
U
п
(
Икс
,
-
1
)
,
{\ Displaystyle F_ {п} (х) = U_ {п} (х, -1), \,}
L
п
(
Икс
)
знак равно
V
п
(
Икс
,
-
1
)
.
{\ Displaystyle L_ {п} (х) = V_ {п} (х, -1). \,}
Их также можно выразить через многочлены Чебышева и как
Т
п
(
Икс
)
{\ Displaystyle {\ mathcal {T}} _ {п} (х)}
U
п
(
Икс
)
{\ Displaystyle {\ mathcal {U}} _ {п} (х)}
F
п
(
Икс
)
знак равно
я
п
-
1
⋅
U
п
-
1
(
-
я
Икс
2
)
,
{\ Displaystyle F_ {п} (х) = я ^ {п-1} \ cdot {\ mathcal {U}} _ {п-1} ({\ tfrac {-ix} {2}}), \,}
L
п
(
Икс
)
знак равно
2
⋅
я
п
⋅
Т
п
(
-
я
Икс
2
)
,
{\ displaystyle L_ {n} (x) = 2 \ cdot i ^ {n} \ cdot {\ mathcal {T}} _ {n} ({\ tfrac {-ix} {2}}), \,}
где - мнимая единица .
я
{\ displaystyle i}
Идентичности
Как частные случаи последовательностей Люка, многочлены Фибоначчи удовлетворяют ряду тождеств, таких как
F
м
+
п
(
Икс
)
знак равно
F
м
+
1
(
Икс
)
F
п
(
Икс
)
+
F
м
(
Икс
)
F
п
-
1
(
Икс
)
{\ Displaystyle F_ {m + n} (x) = F_ {m + 1} (x) F_ {n} (x) + F_ {m} (x) F_ {n-1} (x) \,}
L
м
+
п
(
Икс
)
знак равно
L
м
(
Икс
)
L
п
(
Икс
)
-
(
-
1
)
п
L
м
-
п
(
Икс
)
{\ Displaystyle L_ {m + n} (x) = L_ {m} (x) L_ {n} (x) - (- 1) ^ {n} L_ {mn} (x) \,}
F
п
+
1
(
Икс
)
F
п
-
1
(
Икс
)
-
F
п
(
Икс
)
2
знак равно
(
-
1
)
п
{\ Displaystyle F_ {n + 1} (x) F_ {n-1} (x) -F_ {n} (x) ^ {2} = (- 1) ^ {n} \,}
F
2
п
(
Икс
)
знак равно
F
п
(
Икс
)
L
п
(
Икс
)
.
{\ Displaystyle F_ {2n} (x) = F_ {n} (x) L_ {n} (x). \,}
Выражения в закрытой форме, похожие на формулу Бине:
F
п
(
Икс
)
знак равно
α
(
Икс
)
п
-
β
(
Икс
)
п
α
(
Икс
)
-
β
(
Икс
)
,
L
п
(
Икс
)
знак равно
α
(
Икс
)
п
+
β
(
Икс
)
п
,
{\ displaystyle F_ {n} (x) = {\ frac {\ alpha (x) ^ {n} - \ beta (x) ^ {n}} {\ alpha (x) - \ beta (x)}}, \, L_ {n} (x) = \ alpha (x) ^ {n} + \ beta (x) ^ {n},}
куда
α
(
Икс
)
знак равно
Икс
+
Икс
2
+
4
2
,
β
(
Икс
)
знак равно
Икс
-
Икс
2
+
4
2
{\ displaystyle \ alpha (x) = {\ frac {x + {\ sqrt {x ^ {2} +4}}} {2}}, \, \ beta (x) = {\ frac {x - {\ sqrt) {х ^ {2} +4}}} {2}}}
являются решениями (по t )
т
2
-
Икс
т
-
1
знак равно
0.
{\ displaystyle t ^ {2} -xt-1 = 0. \,}
Для многочленов Люка n > 0 имеем
L
п
(
Икс
)
знак равно
∑
k
знак равно
0
⌊
п
/
2
⌋
п
п
-
k
(
п
-
k
k
)
Икс
п
-
2
k
.
{\ displaystyle L_ {n} (x) = \ sum _ {k = 0} ^ {\ lfloor n / 2 \ rfloor} {\ frac {n} {nk}} {\ binom {nk} {k}} x ^ {n-2k}.}
Связь между многочленами Фибоначчи и стандартными базисными многочленами задается формулой
Икс
п
знак равно
F
п
+
1
(
Икс
)
+
∑
k
знак равно
1
⌊
п
/
2
⌋
(
-
1
)
k
[
(
п
k
)
-
(
п
k
-
1
)
]
F
п
+
1
-
2
k
(
Икс
)
.
{\ 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).}
Например,
Икс
4
знак равно
F
5
(
Икс
)
-
3
F
3
(
Икс
)
+
2
F
1
(
Икс
)
{\ displaystyle x ^ {4} = F_ {5} (x) -3F_ {3} (x) + 2F_ {1} (x) \,}
Икс
5
знак равно
F
6
(
Икс
)
-
4
F
4
(
Икс
)
+
5
F
2
(
Икс
)
{\ displaystyle x ^ {5} = F_ {6} (x) -4F_ {4} (x) + 5F_ {2} (x) \,}
Икс
6
знак равно
F
7
(
Икс
)
-
5
F
5
(
Икс
)
+
9
F
3
(
Икс
)
-
5
F
1
(
Икс
)
{\ displaystyle x ^ {6} = F_ {7} (x) -5F_ {5} (x) + 9F_ {3} (x) -5F_ {1} (x) \,}
Икс
7
знак равно
F
8
(
Икс
)
-
6
F
6
(
Икс
)
+
14
F
4
(
Икс
)
-
14
F
2
(
Икс
)
{\ displaystyle x ^ {7} = F_ {8} (x) -6F_ {6} (x) + 14F_ {4} (x) -14F_ {2} (x) \,}
Комбинаторная интерпретация
Коэффициенты полиномов Фибоначчи можно определить по треугольнику Паскаля по «мелким» диагоналям (показаны красным). Суммы коэффициентов - это числа Фибоначчи.
Если F ( n , k ) - коэффициент при x k в F n ( x ), поэтому
F
п
(
Икс
)
знак равно
∑
k
знак равно
0
п
F
(
п
,
k
)
Икс
k
,
{\ Displaystyle F_ {n} (x) = \ sum _ {k = 0} ^ {n} F (n, k) x ^ {k}, \,}
тогда 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
(
п
,
k
)
знак равно
(
п
+
k
-
1
2
k
)
{\ Displaystyle F (п, к) = {\ binom {\ tfrac {п + к-1} {2}} {к}}}
когда n и k имеют противоположную четность. Это дает возможность считывать коэффициенты из треугольника Паскаля, как показано справа.
использованная литература
Бенджамин, Артур Т .; Куинн, Дженнифер Дж. (2003). «§9.4 Многочлен Фибоначчи и Люка» . Доказательства, которые действительно важны: искусство комбинаторного доказательства . Математические экспозиции Дольчиани. 27 . Математическая ассоциация Америки . п. 141 . ISBN 978-0-88385-333-7 .
Филиппу, Андреас Н. (2001) [1994], "Многочлены Фибоначчи" , Энциклопедия математики , EMS Press
Филиппу, Андреас Н. (2001) [1994], "Многочлены Лукаса" , Энциклопедия математики , EMS Press
Вайсштейн, Эрик В. «Полином Лукаса» . MathWorld .
Джин, З. О многочленах Лукаса и некоторых их новых тождествах. Adv Differ Equ 2018, 126 (2018). https://doi.org/10.1186/s13662-018-1527-9
дальнейшее чтение
внешние ссылки
<img src="https://en.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">