Фибоначијеви полиноми

Из Википедије, слободне енциклопедије

Фибоначијеви полиноми дефинишу се следећом рекурзијом:

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

Сматрају се генерализацијом Фибоначијевога низа.

Својства и Лукасови полиноми[уреди]

Генерирајућа функција Фибоначијевих полинома је:

 \sum_{n=0}^\infty F_n(x) t^n = \frac{t}{1-xt-t^2}.

Првих неколико Фибоначијевих полинома:

F_0(x)=0 \,
F_1(x)=1 \,
F_2(x)=x \,
F_3(x)=x^2+1 \,
F_4(x)=x^3+2x \,
F_5(x)=x^4+3x^2+1 \,
F_6(x)=x^5+4x^3+3x \,

Лукасови полиноми користе исту рекурзију, али са нешто другачијим почетним вредностима: L_n(x) = \begin{cases}
2, & \mbox{ako } n = 0 \\
x, & \mbox{ako } n = 1 \\
x L_{n - 1}(x) + L_{n - 2}(x), & \mbox{ako } n \geq 2.
\end{cases}

Генерирајућа функција Лукасових полинома је:

 \sum_{n=0}^\infty L_n(x) t^n = \frac{2-xt}{1-xt-t^2}.

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

L_0(x)=2 \,
L_1(x)=x \,
L_2(x)=x^2+2 \,
L_3(x)=x^3+3x \,
L_4(x)=x^4+4x^2+2 \,
L_5(x)=x^5+5x^3+5x \,
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)\,
L_{m+n}(x)=L_m(x)L_n(x)-(-1)^nL_{m-n}(x)\,
F_{n+1}(x)F_{n-1}(x)- F_n(x)^2=(-1)^n\,
F_{2n}(x)=F_n(x)L_n(x).\,

Комбинаторна интерпретација[уреди]

Уз помоћ полудијагонала Паскаловога троугла могу да се ичитају Фибоначијеви бројеви (црвено означени). Они представљају суму бројева на полудијагонали.

Ако је F(n,k) коефицијент од xk у Fn(x), тако да је:

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)=\binom{\tfrac{n+k-1}{2}}{k}

Уз помоћ те релације Фибоначијеви бројеви могу да се очитаваку из Паскаловога троугла.

Литература[уреди]