Фибоначијеви полиноми дефинишу се следећом рекурзијом:
F
n
(
x
)
=
{
0
,
if
n
=
0
1
,
if
n
=
1
x
F
n
−
1
(
x
)
+
F
n
−
2
(
x
)
,
if
n
≥
2
{\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}}}
Сматрају се генерализацијом Фибоначијевога низа .
Својства и Лукасови полиноми
уреди
Генерирајућа функција Фибоначијевих полинома је:
∑
n
=
0
∞
F
n
(
x
)
t
n
=
t
1
−
x
t
−
t
2
.
{\displaystyle \sum _{n=0}^{\infty }F_{n}(x)t^{n}={\frac {t}{1-xt-t^{2}}}.}
Првих неколико Фибоначијевих полинома:
F
0
(
x
)
=
0
{\displaystyle F_{0}(x)=0\,}
F
1
(
x
)
=
1
{\displaystyle F_{1}(x)=1\,}
F
2
(
x
)
=
x
{\displaystyle F_{2}(x)=x\,}
F
3
(
x
)
=
x
2
+
1
{\displaystyle F_{3}(x)=x^{2}+1\,}
F
4
(
x
)
=
x
3
+
2
x
{\displaystyle F_{4}(x)=x^{3}+2x\,}
F
5
(
x
)
=
x
4
+
3
x
2
+
1
{\displaystyle F_{5}(x)=x^{4}+3x^{2}+1\,}
F
6
(
x
)
=
x
5
+
4
x
3
+
3
x
{\displaystyle F_{6}(x)=x^{5}+4x^{3}+3x\,}
Лукасови полиноми користе исту рекурзију, али са нешто другачијим почетним вредностима:
L
n
(
x
)
=
{
2
,
ako
n
=
0
x
,
ako
n
=
1
x
L
n
−
1
(
x
)
+
L
n
−
2
(
x
)
,
ako
n
≥
2.
{\displaystyle L_{n}(x)={\begin{cases}2,&{\mbox{ako }}n=0\\x,&{\mbox{ako }}n=1\\xL_{n-1}(x)+L_{n-2}(x),&{\mbox{ako }}n\geq 2.\end{cases}}}
Генерирајућа функција Лукасових полинома је:
∑
n
=
0
∞
L
n
(
x
)
t
n
=
2
−
x
t
1
−
x
t
−
t
2
.
{\displaystyle \sum _{n=0}^{\infty }L_{n}(x)t^{n}={\frac {2-xt}{1-xt-t^{2}}}.}
Првих неколико Лукасових полинома је:
L
0
(
x
)
=
2
{\displaystyle L_{0}(x)=2\,}
L
1
(
x
)
=
x
{\displaystyle L_{1}(x)=x\,}
L
2
(
x
)
=
x
2
+
2
{\displaystyle L_{2}(x)=x^{2}+2\,}
L
3
(
x
)
=
x
3
+
3
x
{\displaystyle L_{3}(x)=x^{3}+3x\,}
L
4
(
x
)
=
x
4
+
4
x
2
+
2
{\displaystyle L_{4}(x)=x^{4}+4x^{2}+2\,}
L
5
(
x
)
=
x
5
+
5
x
3
+
5
x
{\displaystyle L_{5}(x)=x^{5}+5x^{3}+5x\,}
L
6
(
x
)
=
x
6
+
6
x
4
+
9
x
2
+
2.
{\displaystyle L_{6}(x)=x^{6}+6x^{4}+9x^{2}+2.\,}
Постоје и друга својства тих полинома:
F
m
+
n
(
x
)
=
F
m
+
1
(
x
)
F
n
(
x
)
+
F
m
(
x
)
F
n
−
1
(
x
)
{\displaystyle F_{m+n}(x)=F_{m+1}(x)F_{n}(x)+F_{m}(x)F_{n-1}(x)\,}
L
m
+
n
(
x
)
=
L
m
(
x
)
L
n
(
x
)
−
(
−
1
)
n
L
m
−
n
(
x
)
{\displaystyle L_{m+n}(x)=L_{m}(x)L_{n}(x)-(-1)^{n}L_{m-n}(x)\,}
F
n
+
1
(
x
)
F
n
−
1
(
x
)
−
F
n
(
x
)
2
=
(
−
1
)
n
{\displaystyle F_{n+1}(x)F_{n-1}(x)-F_{n}(x)^{2}=(-1)^{n}\,}
F
2
n
(
x
)
=
F
n
(
x
)
L
n
(
x
)
.
{\displaystyle F_{2n}(x)=F_{n}(x)L_{n}(x).\,}
Комбинаторна интерпретација
уреди
Уз помоћ полудијагонала Паскаловога троугла могу да се ичитају Фибоначијеви бројеви (црвено означени). Они представљају суму бројева на полудијагонали. Ако је F (n ,k ) коефицијент од xk у Fn (x ), тако да је:
F
n
(
x
)
=
∑
k
=
0
n
F
(
n
,
k
)
x
k
,
{\displaystyle F_{n}(x)=\sum _{k=0}^{n}F(n,k)x^{k},\,}
онда F (n ,k ) представља број начина на који се може добити n−1 сумом само помоћу 1 и 2, а при томе се 1 користи к пута. Тако је нпр. F(6,3)=4, јер се
5 може добити на 4 начина:1+1+1+2, 1+1+2+1, 1+2+1+1 и 2+1+1+1.
На основу тога следи да је F (n ,k ) једнак биномном коефицијенту :
F
(
n
,
k
)
=
(
n
+
k
−
1
2
k
)
{\displaystyle F(n,k)={\binom {\tfrac {n+k-1}{2}}{k}}}
Уз помоћ те релације Фибоначијеви бројеви могу да се очитаваку из Паскаловога троугла .
Литература
уреди
