5.1: Генеруючі функції

Template:MathjaxLevin

Існує надзвичайно потужний інструмент в дискретній математиці, який використовується для маніпулювання послідовностями, які називаються генеруючою функцією. Ідея така: замість нескінченної послідовності (наприклад:$2, 3, 5, 8, 12, \ldots$) ми дивимося на єдину функцію, яка кодує послідовність. Але не функція, яка дає термін$n$ th як вихід. Замість цього функція, чиї ряди степенів (як з числення) «відображає» терміни послідовності. Так, наприклад, ми б дивитися на потужність ряд,$2 + 3x + 5x^2 + 8x^3 + 12x^4 + \cdots$ який відображає послідовність$2, 3, 5, 8, 12, \ldots$ як коефіцієнти.

Нескінченний енергетичний ряд - це просто нескінченна сума термінів форми,$c_n$ яка$c_nx^n$ була деякою постійною. Таким чином, ми могли б написати силовий ряд, як це:

\ begin {рівняння*}\ sum_ {k=0} ^\ infty c_k x^k.\ end {рівняння*}

або розширено так

\ begin {рівняння*} c_0 + c_1x + c_2x^2 + c_3x^3 + c_4x^4 + c_5x^5 +\ cdots. \ end {рівняння*}

При розгляді в контексті генеруючих функцій ми називаємо такий енергетичний ряд генеруючим рядом. Генеруючий ряд генерує послідовність

\ begin {рівняння*} c_0, c_1, c_2, c_3, c_4, c_5,\ ldots. \ end {рівняння*}

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

Приклад$\PageIndex{1}$

Яку послідовність представляє генерує ряд$3 + 8x^2 + x^3 + \frac{x^5}{7} + 100x^6 + \cdots\text{?}$

Рішення

Ми просто зачитуємо коефіцієнти кожного$x^n$ term. So $a_0 = 3$ since the coefficient of $x^0$ is 3 ($x^0 = 1$ so this is the constant term). What is $a_1\text{?}$ It is NOT 8, since 8 is the coefficient of $x^2\text{,}$ so 8 is the term $a_2$ of the sequence. To find $a_1$ we need to look for the coefficient of $x^1$ which in this case is 0. So $a_1 = 0\text{.}$ Continuing, we have $a_2 = 8\text{,}$ $a_3 = 1\text{,}$ $a_4 = 0\text{,}$ and $a_5 = \frac{1}{7}\text{.}$ So we have the sequence

\ begin {рівняння*} 3, 0, 8, 1,\ frac {1} {7}, 100,\ ldots\ end {рівняння*}

Зверніть увагу, що при обговоренні генеруючих функцій ми завжди починаємо нашу послідовність з$a_0\text{.}$

Тепер ви можете дуже природно запитати, чому ми будемо робити таку річ. Однією з причин є те, що кодування послідовності з силовим рядом допомагає нам відстежувати, який термін є який у послідовності. Наприклад, якщо ми пишемо послідовність,$1, 3, 4, 6, 9, \ldots, 24, 41,\ldots$ неможливо визначити, який термін$24$ є (навіть якщо ми домовилися, що перший член повинен бути$a_0$). Однак, якби ми написали генеруючий ряд замість цього, ми б мали$1 + 3x + 4x^2 + 6x^3 + 9x^4 + \cdots + 24 x^{17} + 41 x^{18} + \cdots\text{.}$ Тепер зрозуміло, що 24 - це 17-й член послідовності (тобто$a_{17} = 24$). Звичайно, щоб отримати цю вигоду, ми могли б відобразити нашу послідовність будь-якою кількістю способів, можливо,$\fbox{1}_0 \fbox{3}_1 \fbox{4}_2 \fbox{6}_3 \fbox{9}_4 \cdots \fbox{24}_{17}\fbox{41}_{18}\cdots\text{,}$ але ми цього не робимо. Причина полягає в тому, що генеруючий ряд виглядає як звичайний силовий ряд (хоча ми інтерпретуємо це по-різному), тому ми можемо робити з ним речі, які ми зазвичай робимо з силовими рядами, такими як записати, до чого він сходиться.

Наприклад, з обчислення ми знаємо, що ряд$1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \frac{x^4}{24} + \cdots + \frac{x^n}{n!} + \cdots$ степенів сходиться до функції$e^x\text{.}$ Таким чином, ми можемо використовувати$e^x$ як спосіб говорити про послідовність коефіцієнтів рядів потужності для$e^x\text{.}$ Коли ми записуємо приємну компактну функцію, яка має нескінченний ряд потужності, який ми розглядаємо як генеруючий ряд, то ми називаємо цю функцію генеруючою функцією. У цьому прикладі ми б сказали

\ begin {рівняння*} 1, 1,\ frac {1} {2},\ frac {1} {6},\ frac {1} {24},\ ldots,\ frac {1} {n!} ,\ ldots\ mbox {має генеруючу функцію} e^x\ end {рівняння*}

Побудова генеруючих функцій

$e^x$Приклад дуже конкретний. У нас досить дивна послідовність, і єдина причина, по якій ми знаємо її генеруючу функцію, полягає в тому, що ми знаємо серію Тейлора для$e^x\text{.}$ Нашої мети зараз є зібрати деякі інструменти для побудови генеруючої функції певної заданої послідовності.

Давайте подивимося, що генерують функції для деяких дуже простих послідовностей. Найпростіший з усіх: 1, 1, 1, 1, 1,... Як виглядає генеруюча серія? Це просто$1 + x + x^2 + x^3 + x^4 + \cdots\text{.}$ Тепер, чи можемо ми знайти замкнуту формулу для цього силового ряду? Так! Ця конкретна серія насправді просто геометрична серія із загальним співвідношенням$x\text{.}$ Отже, якщо ми використовуємо нашу техніку «множення, зсув та віднімання» з розділу 2.2, ми маємо

\ begin {вирівнювати*} S\ ампер = 1 + x + x^2 + x ^ 3 +\ cdots\\ підкреслення {- xS}\ ампер\ підкреслення {\,\, = ~~~~~~~~x^2 + x^3 + x ^ 4 +\ cdots}\\ (1-х) S\ amp = 1\ кінець {вирівнювати*}

Тому ми бачимо, що

\ begin {рівняння*} 1 + х + x^2 + x^3\ cdots =\ dfrac {1} {1-x}\ end {рівняння*}

Ви можете згадати з обчислення, що це вірно лише на інтервалі збіжності для рядів степенів, у цьому випадку$|x| \lt 1\text{.}$, коли Це вірно для нас, але нам все одно. Ми ніколи не збираємося нічого підключати до тих пір,$x\text{,}$ поки існує якась цінність,$x$ для якої генеруюча функція та генеруюча серія погоджуються, ми щасливі. І в цьому випадку ми щасливі.

$1,1,1,\ldots$

Генеруюча функція$1,1,1,1,1,1,\ldots$ для$\dfrac{1}{1-x}$

Давайте використаємо цю основну генеруючу функцію, щоб знайти генеруючі функції для більшої кількості послідовностей. Що робити, якщо ми$-x\text{.}$ замінимо$x$ на Ми отримаємо

\ begin {рівняння*}\ frac {1} {1+x} = 1 - x + x^2 - x^3 +\ cdots\ mbox {який генерує} 1, -1, -1,\ ldots\ end {рівняння*}

Якщо ми замінимо$x$ на,$3x$ ми отримаємо

\ begin {рівняння*}\ frac {1} {1-3x} = 1 + 3x + 9x^2 + 27x^3 +\ cdots\ mbox {який генерує} 1, 3, 9, 27,\ ldots\ end {рівняння*}

Замінивши$x$ в,$\frac{1}{1-x}$ ми можемо отримати генеруючі функції для різних послідовностей, але не для всіх. Наприклад, ви не можете підключити нічого,$x$ щоб отримати генеруючу функцію для$2,2,2,2, \ldots\text{.}$ Однак ми ще не загубилися. Зверніть увагу, що кожен член$2, 2, 2, 2, \ldots$ є результатом множення членів$1, 1, 1, 1, \ldots$ на константу 2. Так помножте генеруючу функцію на 2, а також.

\ begin {рівняння*}\ frac {2} {1-x} = 2 + 2x + 2x^2 + 2x^3 +\ cdots\ mbox {який генерує} 2, 2, 2, 2,\ ldots\ end {рівняння*}

Аналогічно, щоб знайти генеруючу функцію для послідовності$3, 9, 27, 81, \ldots\text{,}$ відзначимо, що ця послідовність є результатом множення кожного члена$1, 3, 9, 27, \ldots$ на 3. Оскільки у нас є генеруюча функція для$1, 3, 9, 27, \ldots$ ми можемо сказати

\ begin {рівняння*}\ frac {3} {1-3x} = 3\ cdot 1 + 3\ cdot 3x + 3\ cdot 9x^2 + 3\ cdot 27x^3 +\ cdots\ mbox {який генерує} 3, 9, 27, 81,\ ldots\ кінець {рівняння*}

Як щодо послідовності$2, 4, 10, 28, 82, \ldots\text{?}$ Тут терміни завжди на 1 більше, ніж сили 3. Тобто ми додали послідовності$1,1,1,1,\ldots$ та$1,3,9, 27,\ldots$ термін за терміном. Тому ми можемо отримати генеруючу функцію, додавши відповідні генеруючі функції:

\ почати {вирівнювати*} 2 + 4x + 10x^2 + 28x^3 +\ cdots\ amp = (1 + 1) + (1 + 3) х + (1 + 9) x^2 + (1 + 27) x^3 +\ cdots\\ ампер = 1 + x + x ^ 2 + x ^ 3 +\ cdots + 1 + 3x 9x^2 + 27x^2 + ^3 +\ cdots\\ амп =\ гідророзриву {1} {1-x} +\ гідророзриву {1} {1-3x}\ кінець {align*}

Веселощі не зупиняються на досягнутому: якщо ми замінимо$x$ в нашій оригінальній генеруючій функції,$x^2$ ми отримаємо

\ begin {рівняння*}\ frac {1} {1-x^2} = 1 + x^2 + x^4 + x^6\ cdots\ mbox {який генерує} 1, 0, 1, 0,\ ldots. \ end {рівняння*}

Як ми могли отримати$0,1,0,1,0,1,\ldots\text{?}$ Start з попередньою послідовністю і зрушити її на 1. Але як ви це робите? Щоб побачити, як працює зсув, давайте спочатку спробуємо отримати генеруючу функцію для послідовності$0, 1, 3, 9, 27, \ldots\text{.}$ Ми знаємо, що$\frac{1}{1-3x} = 1 + 3x + 9x^2 + 27x^3 + \cdots\text{.}$ Щоб отримати нуль спереду, нам потрібен генеруючий ряд, щоб виглядати$x + 3x^2 + 9x^3 + 27x^4+ \cdots$ (так що немає постійного терміну). Множення на$x$ має такий ефект. Таким чином, генеруюча функція для$0, 1, 3, 9, 27, \ldots$ є$\frac{x}{1-3x}\text{.}$ Це також буде працювати, щоб отримати генеруючу функцію для$0,1,0,1,0,1,\ldots\text{:}$

\ begin {рівняння*}\ frac {x} {1-x^2} = x + x^3 + x^5 +\ cdots\ mbox {який генерує} 0, 1, 0, 1, 0, 1\ ldots\ end {рівняння*}

Що робити, якщо ми додамо послідовності$1,0,1,0,1,0,\ldots$ і$0,1,0,1,0,1,\ldots$ термін за терміном? Ми повинні отримати$1,1,1,1,1,1\ldots\text{.}$ Що відбувається, коли ми додаємо генеруючі функції? Це працює (спробуйте)!

\ begin {рівняння*}\ розрив {1} {1-x^2} +\ розрив {x} {1-x^2} =\ гідророзриву {1} {1-x}. \ end {рівняння*}

Ось підлий: що станеться, якщо взяти похідну від$\frac{1}{1-x}\text{?}$ Ми$\frac{1}{(1-x)^2}\text{.}$ отримуємо З іншого боку, якщо ми розмежовуємо термін за терміном у ряді влади, ми отримаємо,$(1 + x + x^2 + x^3 + \cdots)' = 1 + 2x + 3x^2 + 4x^3 + \cdots$ який генерує ряд для$1, 2, 3, 4, \ldots\text{.}$ Це говорить

$1,2,3,\ldots$

Генеруюча функція$1, 2, 3, 4, 5, \ldots$ для$\d\frac{1}{(1-x)^2}.$

Візьміть другу похідну:$\frac{2}{(1-x)^3} = 2 + 6x + 12x^2 + 20x^3 + \cdots\text{.}$ Так$\frac{1}{(1-x)^3} = 1 + 3x + 6x^2 + 10x^3 + \cdots$ це генеруюча функція для трикутних чисел,$1,3,6,10\ldots$ (хоча тут ми маємо$a_0 = 1$ поки$T_0 = 0$ зазвичай).

Різниця

Ми бачили, як знайти генеруючі функції за$\frac{1}{1-x}$ допомогою множення (на константу або на$x$), підстановки, додавання та диференціації. Щоб використовувати кожен з них, ви повинні помітити спосіб$1,1,1,1,1\ldots$ перетворення послідовності в потрібну послідовність. Це не завжди легко. Це також насправді не так, як ми аналізували послідовності. Одна річ, яку ми часто розглядали, - це послідовність відмінностей між термінами послідовності. Це виявиться корисним у пошуку генеруючих функцій, а також. Послідовність відмінностей часто простіше, ніж вихідна послідовність. Так що, якщо ми знаємо генеруючу функцію для відмінностей, ми хотіли б використовувати це, щоб знайти генеруючу функцію для вихідної послідовності.

Наприклад, розглянемо послідовність$2, 4, 10, 28, 82, \ldots\text{.}$ Як ми могли б перейти до послідовності перших відмінностей:$2, 6, 18, 54,\ldots\text{?}$ Ми хочемо відняти 2 з 4, 4 з 10, 10 з 28, і так далі. Так що, якщо ми віднімаємо (термін за терміном) послідовність$0, 2, 4, 10, 28,\ldots$ з$2, 4, 10, 28\ldots\text{,}$ ми будемо встановлені. Ми можемо отримати генеруючу функцію для$0,2,4,10,28,\ldots$ від генеруючої функції for$2,4,10,28\ldots$ шляхом множення на$x\text{.}$ Use$A$ для представлення генеруючої функції для$2, 4, 10, 28, 82, \ldots$ Тоді:

\ почати {вирівнювати*} A\ ампер = 2 + 4x+ 10x^2 +82x^3 + 82x^4 +\ cdots\\ підкреслення {-xA}\ ампер\ підкреслення {\,\, = 0 + 2x + 4x^2 + 10x^3 + 82x^5 +\ cdots}\\ (1-х) A\ amp = 2 + 2x + 6x^2 + 18x^3+ 54x^4 +\ cdots\ кінець {вирівнювати*}

Хоча ми не отримуємо точно послідовність відмінностей, ми отримуємо щось близько. У цьому конкретному випадку ми вже знаємо генеруючу функцію$A$ (ми знайшли її в попередньому розділі), але більшу частину часу ми будемо використовувати цю техніку різниці, щоб знайти,$A\text{:}$ чи є у нас генеруюча функція для послідовності відмінностей, ми можемо потім вирішити для$A\text{.}$

Приклад$\PageIndex{2}$

Знайдіть генеруючу функцію для$1, 3, 5, 7, 9,\ldots\text{.}$

Рішення

Зверніть увагу, що послідовність відмінностей постійна. Ми знаємо, як знайти генеруючу функцію для будь-якої постійної послідовності. Так позначають генеруючу функцію для$1, 3, 5, 7, 9, \ldots$ by $A\text{.}$ We have

\ почати {вирівнювати*} A\ ампер = 1 + 3x + 5x^2 + 7x^3 + 9x^4 +\ cdots\\ підкреслення {-xA}\ ампер\ підкреслення {\,\, = 0 + х + 3х^2 + 5x^4+ 9x^5 +\ cdots}\\ (1-х) A\ amp = 1 + 2x + 2x + 2x^2 + 2x^3 + 2x^4 +\ cdots\ кінець {вирівнювати*}

Ми знаємо, що$2x + 2x^2 + 2x^3 + 2x^4 + \cdots = \dfrac{2x}{1-x}\text{.}$ Thus

\ begin {рівняння*} (1-х) A = 1 +\ frac {2x} {1-х}. \ end {рівняння*}

Тепер вирішуйте для$A\text{:}$

\ begin {рівняння*} A =\ гідророзриву {1} {1-x} +\ гідророзриву {2x} {(1-х) ^2} =\ гідророзриву {1+х} {(1-х) ^2}. \ end {рівняння*}

Чи має це сенс? Перш ніж ми спростили два дроби в один, ми додавали генеруючу функцію для послідовності.$1,1,1,1,\ldots$ to the generating function for the sequence $0, 2, 4, 6, 8, 10, \ldots$ (remember $\frac{1}{(1-x)^2}$ generates $1,2,3,4,5, \ldots\text{,}$ multiplying by $2x$ shifts it over, putting the zero out front, and doubles each term). If we add these term by term, we get the correct sequence $1,3,5,7, 9, \ldots\text{.}$

Тепер, коли у нас є генеруюча функція для непарних чисел, ми можемо використовувати це, щоб знайти генеруючу функцію для квадратів:

Приклад$\PageIndex{3}$

Знаходимо генеруючу функцію для$1, 4, 9, 16, \ldots\text{.}$ Note, яку ми беремо$1 = a_0\text{.}$

Рішення

Знову викликаємо генеруючу функцію для послідовності$A\text{.}$ Using differencing:

\ почати {вирівнювати*} A\ ампер = 1 + 4x+ 9x^2 + 16x^3 +\ cdots\\ підкреслення {- xA}\ ампер\ підкреслення {\,\, = 0 + х + 4x^2 + 9x^3 + 16x^4 +\ cdots}\\ (1-х) A\ amp = 1 + 3x + 5x^2 + 7x^3 +\ cdots\ кінець {вирівнювати*}

Так як$1 + 3x + 5x^2 + 7x^3 + \cdots = \d\frac{1+x}{(1-x)^2}$ we have $A = \d\frac{1+x}{(1-x)^3}\text{.}$

У кожному з прикладів вище ми знайшли різницю між послідовними термінами, які дали нам послідовність відмінностей, для яких ми знали генеруючу функцію. Ми можемо узагальнити це до більш складних зв'язків між термінами послідовності. Наприклад, якщо ми знаємо, що послідовність задовольняє відношення повторення$a_n = 3a_{n-1} - 2a_{n-2}\text{?}$ Іншими словами, якщо взяти член послідовності і відняти 3 рази попередній член, а потім додати 2 рази термін перед цим, ми отримаємо 0 (так як$a_n - 3a_{n-1} + 2a_{n-2} = 0$). Це буде триматися для всіх, крім перших двох членів послідовності. Таким чином, після перших двох членів, послідовність результатів цих розрахунків буде послідовність 0, для яких ми точно знаємо генеруючу функцію.

Приклад$\PageIndex{4}$

Послідовність$1, 3, 7, 15, 31, 63, \ldots$ задовольняє відношення повторення$a_n = 3a_{n-1} - 2a_{n-2}\text{.}$ Знайти генеруючу функцію для послідовності.

Рішення

Виклик генеруючої функції для послідовності$A\text{.}$ We have

\ почати {вирівнювати*} А\ ампер = 1 + 3х+ 7х^2 + 15x^3 + 31x^4 +\ cdots + a_nx^n +\ cdots\\ cdots\\ -3xa\ ампер = 0 - 3x - 9x^2 - 21x^3 -\ cdots - 3a_ {n-1} x^n -\ cdots\\ підкреслення +~~~2x^2A_ {~} ^ {~^ {~}}}\ ампер\ підкреслення {\,\, = 0 + 0x + 2x^2 + 6x^3 + 14x^4 +\ cdots + 2a_ {n-2} х ^ n +\ cdots}\ (1-3x+2x^2) A\ підсилювач = 1\ кінець {вирівнювати*}

Ми помножили$A$ by $-3x$ which shifts every term over one spot and multiplies them by $-3\text{.}$ On the third line, we multiplied $A$ by $2x^2\text{,}$ which shifted every term over two spots and multiplied them by 2. When we add up the corresponding terms, we are taking each term, subtracting 3 times the previous term, and adding 2 times the term before that. This will happen for each term after $a_1$ because $a_n - 3a_{n-1} + 2a_{n-2} = 0\text{.}$ In general, we might have two terms from the beginning of the generating series, although in this case the second term happens to be 0 as well.

Тепер нам просто потрібно вирішити для$A\text{:}$

\ begin {рівняння*} A =\ frac {1} {1 - 3x + 2x^2}. \ end {рівняння*}

Множення та часткові суми

Що відбувається з послідовностями при множенні двох генеруючих функцій? Давайте подивимося:$A = a_0 + a_1x + a_2x^2 + \cdots$ і$B = b_0 + b_1x + b_2x^2 + \cdots\text{.}$ щоб помножити$A$ і$B\text{,}$ нам потрібно зробити багато розподілу (нескінченне FOIL?) але майте на увазі, що ми будемо групувати як терміни і потрібно лише записати перші кілька термінів, щоб побачити шаблон. Постійний термін -$a_0b_0\text{.}$ Коефіцієнт$x$ є$a_0b_1 + a_1b_0\text{.}$ І так далі. Отримуємо:

\ почати {рівняння*} AB = a_0b_0 + (a_0b_1 + a_1b_0) х + (a_0b_2 + a_1b_1 + a_2b_0) x^2 + (a_0b_3 + a_1b_2 + a_2b_1 + a_3b_0) x^3 +\ cdots\ кінець {рівняння*}

Приклад$\PageIndex{5}$

«Помножити» послідовність$1, 2, 3, 4, \ldots$ на послідовність$1, 2, 4, 8, 16, \ldots\text{.}$

Рішення

Новий постійний термін - це просто$1 \cdot 1\text{.}$ The next term will be $1\cdot 2 + 2 \cdot 1 = 4\text{.}$ The next term: $1 \cdot 4 + 2 \cdot 2 + 3 \cdot 1 = 11\text{.}$ One more: $1 \cdot 8 + 2 \cdot 4 + 3 \cdot 2 + 4 \cdot 1 = 28\text{.}$ The resulting sequence is

\ begin {рівняння*} 1, 4, 11, 28, 57,\ ldots\ end {рівняння*}

Так як генеруюча функція для$1,2,3,4, \ldots$ is $\frac{1}{(1-x)^2}$ and the generating function for $1,2,4,8, 16, \ldots$ is $\frac{1}{1-2x}\text{,}$ we have that the generating function for $1,4, 11, 28, 57, \ldots$ is $\frac{1}{(1-x)^2(1-2x)}$

Розглянемо особливий випадок, коли ви множите послідовність на$1, 1, 1, \ldots\text{.}$ Наприклад,$1,1,1,\ldots$$1, 2, 3, 4, 5\ldots\text{.}$ помножте на Перший$1\cdot 1 = 1\text{.}$ член -$1\cdot 2 + 1 \cdot 1 = 3\text{.}$ Тоді$1\cdot 3 + 1\cdot 2 + 1 \cdot 1 = 6\text{.}$ Наступний член буде 10. Отримуємо трикутні числа. Точніше, ми отримуємо послідовність часткових сум з$1,2,3,4,5, \ldots\text{.}$ точки зору генеруючих функцій, ми беремо$\frac{1}{1-x}$ (генеруючи$1,1,1,1,1\ldots$) і множимо її на$\frac{1}{(1-x)^2}$ (генеруючи$1,2,3,4,5,\ldots$), і це дає$\frac{1}{(1-x)^3}\text{.}$ Це не повинно бути несподіванкою, оскільки ми знайшли ту саму генеруючу функцію для трикутні числа раніше.

Справа в тому, що якщо вам потрібно знайти генеруючу функцію для суми перших$n$ членів певної послідовності, і ви знаєте генеруючу функцію для цієї послідовності, ви можете помножити її на$\frac{1}{1-x}\text{.}$ Щоб повернутися від послідовності часткових сум до вихідної послідовності, ви дивитеся на послідовність відмінностей. Коли ви отримуєте послідовність відмінностей, ви в кінцевому підсумку множите на$1-x\text{,}$ або еквівалентно, діливши на$\frac{1}{1-x}\text{.}$ Множення на$\frac{1}{1-x}$ дає часткові суми, діливши на$\frac{1}{1-x}$ дає відмінності.

Розв'язування рекуррентних відносин з генеруючими функціями

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

Приклад$\PageIndex{6}$

Вирішити зв'язок повторення$a_n = 3a_{n-1} - 2a_{n-2}$ з початковими умовами$a_0 = 1$ та$a_1 = 3\text{.}$

Рішення

Ми бачили в прикладі вище, що це повторення відношення дає послідовність$1, 3, 7, 15, 31, 63, \ldots$ which has generating function $\dfrac{1}{1 - 3x + 2x^2}\text{.}$ We did this by calling the generating function $A$ and then computing $A - 3xA + 2x^2A$ which was just 1, since every other term canceled out.

Але як нам допомагає знання генеруючої функції? Спочатку розбийте генеруючу функцію на дві простіші. Для цього ми можемо використовувати розкладання часткових дробів. Почніть з факторингу знаменника:

\ begin {рівняння*}\ розрив {1} {1-3x + 2x^2} =\ гідророзриву {1} {(1-х) (1-2x)}. \ end {рівняння*}

Розкладання часткового дробу говорить нам, що ми можемо записати цю фракцію як суму двох дробів (розкладаємо заданий дріб):

\ begin {рівняння*}\ розрив {1} {(1-x) (1-2x)} =\ frac {a} {1-x} +\ frac {b} {1-2x}\ text {~~ для деяких констант} a\ text {і} b.\ end {рівняння*}

Щоб знайти$a$ and $b$ we add the two decomposed fractions using a common denominator. This gives

\ begin {рівняння*}\ розрив {1} {(1-x) (1-2x)} =\ розрив {a (1-2x) + b (1-x)} {(1-х) (1-х) (1-2x)}. \ end {рівняння*}

так

\ begin {рівняння*} 1 = a (1-2x) + b (1-х). \ end {рівняння*}

Це повинно бути вірно для всіх значень$x\text{.}$ If $x = 1\text{,}$ then the equation becomes $1 = -a$ so $a = -1\text{.}$ When $x = \frac{1}{2}$ we get $1 = b/2$ so $b = 2\text{.}$ This tells us that we can decompose the fraction like this:

\ begin {рівняння*}\ гідророзриву {1} {(1-x) (1-x) (1-2x)}} =\ розрив {-1} {1-x} +\ гідророзриву {2} {1-2x}. \ end {рівняння*}

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

\ begin {рівняння*}\ frac {-1} {1-x} = -1 - x - x^2 -x^3 - x^4 -\ cdots\ mbox {який генерує} -1, -1, -1, -1,\ ldots. \ end {рівняння*}\ почати {рівняння*}\ frac {2} {1-2x} = 2+ 4x + 8x^2 + 16x^3 + 32x^4 +\ cdots\ mbox {який генерує} 2, 4, 8, 16, 32,\ ldots. \ end {рівняння*}

Ми можемо дати замкнуту формулу для$n$th term of each of these sequences. The first is just $a_n = -1\text{.}$ The second is $a_n = 2^{n+1}\text{.}$ The sequence we are interested in is just the sum of these, so the solution to the recurrence relation is

\ begin {рівняння*} a_n = 2^ {n+1} - 1\ end {рівняння*}

Тепер ми можемо додати генеруючі функції до нашого списку методів для вирішення рекуррентних відносин.