1.2.3. Рекурентні співвідношення і раціональні твірні функції

Послідовність Фібоначчі означається лінійним рекурентним співвідношенням

Виходячи із цього співвідношення і початкових значень послідовності, ми змогли знайти звичайний вигляд твірної функції. Твірна функція виявилась раціональною – відношенням двох многочленів.

Теорема 1.2.1. Нехай послідовність задана лінійним рекурентним співвідношенням із сталими

,причому степінь многочлена дорівнює а степінь многочлена не перевищує .

Доведення. Помноживши твірну функцію на

(1.2.9)

отримаємо

+

,

де степінь многочлена не перевищує . Дійсно коефіцієнт при в правій частині рівності співпадає з правою частиною виразу (2.8). звідси ми отримуємо твердження теореми.

Зауважимо, що твердження теореми 1.2.1 дало нам більш сильніше твердження: ми довели, що многочлен має вигляд

Наслідок векторної твірної функції для послідовності Фібоначчі також використовується на випадок довільної рекурентної послідовності. В загальному випадку двохвимірний вектор треба замінити – вимірним вектором

,

а матриця переходу до наступного – вимірного вектора, що відповідатиме наступному рекурентному співвідношенню, матиме вигляд

Таким чином, ми отримаємо векторну твірну функцію

Матрицю не можна привести до діагонального виду лінійними перетвореннями. Це можна зробити, якщо її власні числа (тобто корені многочлена) попарно відмінні. Але в зальному випадку її можна привести до жорданової нормальної форми, степені якої також не важко обчислити.

Виявляється, що раціональні твірні функції в точності співпадають з твірними функціями для послідовностей, які задані лінійними рекурентними співвідношеннями. Точніше, справедлива наступна обернена теорема.

Теорема 1.2.2. Якщо твірна функція раціональна, , де взаємно прості, то починаючи з деякого номера послідовність задається рекурентним співвідношенням , де - степінь многочлена , а - деякі константи.

1.2.4. Добуток Адамара раціональних твірних функцій.

Одна з найбільш кращих властивостей раціональних твірних функцій – їх замкненість відносно добутку Адамара.

Означення 1.2.3. Добутком Адамара твірних функцій

і

називається твірна функція

Таким чином, добуток Адамара двох послідовностей – це послідовність, яка складається з орректно добутків відповідних членів послідовності. Необхідність твірної функції для добутку Адамара виникає при перерахунку пар об’єктів однакового порядку: якщо число об’єктів першого типу рівний , а число об’єктів другого типу , то число пар об’єктів, складених із елементів першого і другого типів, дорівнює .

Теорема 1.2.4. Добуток Адамара двох раціональних твірних функцій раціональний.

Лема 1. Твірна функція для послідовності раціональна тоді і тільки тоді, коли існують такі числа і такі многочлени,що починаючи з деякого номера

(1.2.10)

Вираз в правій частині рівності називається квазімногочленом від змінної . [1, 13- 26].