Дискретная математика — рекуррентное соотношение

В этой главе мы обсудим, как рекурсивные методы могут выводить последовательности и использоваться для решения задач подсчета. Процедура поиска членов последовательности рекурсивным способом называется рекуррентным отношением . Мы изучаем теорию линейных рекуррентных соотношений и их решения. Наконец, мы вводим производящие функции для решения рекуррентных отношений.

Определение

Рекуррентное отношение — это уравнение, которое рекурсивно определяет последовательность, в которой следующий член является функцией предыдущих членов (выражая $F_n$ как некоторую комбинацию $F_i$ с $i <n$).

Пример — ряд Фибоначчи — $F_n = F_ {n-1} + F_ {n-2}$, Ханойская башня — $F_n = 2F_ {n-1} + 1$

Линейные рекуррентные отношения

Линейное рекуррентное уравнение степени k или порядка k — это рекуррентное уравнение в формате $x_n = A_1 x_ {n-1} + A_2 x_ {n-1} + A_3 x_ {n-1} + \ dots A_k x_ {nk}$ ($A_n$ — константа, а $A_k \ neq 0$) на последовательности чисел как полинома первой степени.

Вот некоторые примеры линейных рекуррентных уравнений —

Рецидив отношений	Начальные значения	Решения
F n = F n-1 + F n-2	a 1 = a 2 = 1	Число Фибоначчи
F n = F n-1 + F n-2	а 1 = 1, а 2 = 3	Номер Лукаса
F n = F n-2 + F n-3	a 1 = a 2 = a 3 = 1	Падовская последовательность
F n = 2F n-1 + F n-2	a 1 = 0, a 2 = 1	Число Пелла

Как решить линейное рекуррентное соотношение

Предположим, что два упорядоченных линейных рекуррентных соотношения имеют вид — $F_n = AF_ {n-1} + BF_ {n-2}$, где A и B — действительные числа.

Характеристическое уравнение для вышеуказанного рекуррентного соотношения —

$$x ^ 2 - Axe - B = 0$$

Три случая могут возникнуть при поиске корней —

Случай 1 — Если это уравнение учитывается как $(x- x_1) (x- x_1) = 0$ и оно дает два различных реальных корня $x_1$ и $x_2$, то $F_n = ax_1 ^ n + bx_2 ^ n$ является решение. [Здесь a и b являются константами]

Случай 2 — Если это уравнение вычисляется как $(x- x_1) ^ 2 = 0$, и оно порождает один действительный корень $x_1$, то решением является $F_n = a x_1 ^ n + bn x_1 ^ n$.

Случай 3 — Если уравнение дает два различных комплексных корня, $x_1$ и $x_2$ в полярной форме $x_1 = r \ angle \ theta$ и $x_2 = r \ angle (- \ theta)$, то $F_n = r ^ n (a cos (n \ theta) + b sin (n \ theta))$ является решением.

Проблема 1

Решите рекуррентное соотношение $F_n = 5F_ {n-1} - 6F_ {n-2}$, где $F_0 = 1$ и $F_1 = 4$.

Решение

Характеристическое уравнение рекуррентного соотношения —

$$x ^ 2 - 5x + 6 = 0,$$

Итак, $(x - 3) (x - 2) = 0$

Следовательно, корни —

$x_1 = 3$ и $x_2 = 2$

Корни реальны и различны. Итак, это в форме дела 1

Следовательно, решение —

$$F_n = ax_1 ^ n + bx_2 ^ n$$

Здесь $F_n = a3 ^ n + b2 ^ n \ (As \ x_1 = 3 \ and \ x_2 = 2)$

Следовательно,

$1 = F_0 = a3 ^ 0 + b2 ^ 0 = a + b$

$4 = F_1 = a3 ^ 1 + b2 ^ 1 = 3a + 2b$

Решая эти два уравнения, мы получаем $a = 2$ и $b = -1$

Следовательно, окончательное решение —

$$ F_n = 2,3 ^ n + (-1). 2 ^ n = 2,3 ^ n — 2 ^ n $$

Проблема 2

Решите рекуррентное соотношение — $F_n = 10F_ {n-1} - 25F_ {n-2}$, где $F_0 = 3$ и $F_1 = 17$.

Решение

Характеристическое уравнение рекуррентного соотношения —

$$x ^ 2 - 10x -25 = 0$$

Итак, $(x - 5) ^ 2 = 0$

Следовательно, существует один действительный корень $x_1 = 5$

Поскольку существует единый действительный корень, он имеет вид случая 2

Следовательно, решение —

$F_n = ax_1 ^ n + bnx_1 ^ n$

$3 = F_0 = a.5 ^ 0 + b.0.5 ^ 0 = a$

$17 = F_1 = a.5 ^ 1 + b.1.5 ^ 1 = 5a + 5b$

Решая эти два уравнения, мы получаем $a = 3$ и $b = 2/5$

Следовательно, окончательное решение — $F_n = 3.5 ^ n + (2/5) .n.2 ^ n$

Проблема 3

Решите рекуррентное соотношение $F_n = 2F_ {n-1} - 2F_ {n-2}$, где $F_0 = 1$ и $F_1 = 3$

Решение

Характеристическое уравнение рекуррентного соотношения —

$$x ^ 2 -2x -2 = 0$$

Следовательно, корни —

$x_1 = 1 + i$ и $x_2 = 1 - i$

В полярной форме,

$x_1 = r \ angle \ theta$ и $x_2 = r \ angle (- \ theta),$ где $r = \ sqrt 2$ и $\ theta = \ frac {\ pi} {4}$

Корни воображаемые. Итак, это в форме случая 3.

Следовательно, решение —

$F_n = (\ sqrt 2) ^ n (cos (n. \ Sqcap / 4) + b sin (n. \ Sqcap / 4))$

$1 = F_0 = (\ sqrt 2) ^ 0 (a cos (0. \ Sqcap / 4) + b sin (0. \ Sqcap / 4)) = a$

$3 = F_1 = (\ sqrt 2) ^ 1 (a cos (1. \ Sqcap / 4) + b sin (1. \ Sqcap / 4)) = \ sqrt 2 (a / \ sqrt 2 + b / \ sqrt 2 )$

Решая эти два уравнения, мы получаем $a = 1$ и $b = 2$

Следовательно, окончательное решение —

$F_n = (\ sqrt 2) ^ n (cos (n. \ Pi / 4) + 2 sin (n. \ Pi / 4))$

Неоднородное рекуррентное соотношение и частные решения

Рекуррентное отношение называется неоднородным, если оно имеет вид

$F_n = AF_ {n-1} + BF_ {n-2} + f (n)$, где $f (n) \ ne 0$

Связанное с ним однородное рекуррентное соотношение равно $F_n = AF_ {n – 1} + BF_ {n-2}$

Решение $(a_n)$ неоднородного рекуррентного отношения состоит из двух частей.

Первая часть — это решение $(a_h)$ связанного однородного рекуррентного соотношения, а вторая часть — это частное решение $(a_t)$.

$$a_n = A_H + a_t$$

Решение первой части выполняется с использованием процедур, описанных в предыдущем разделе.

Чтобы найти конкретное решение, мы находим подходящее пробное решение.

Пусть $f (n) = cx ^ n$; пусть $x ^ 2 = Ax + B$ — характеристическое уравнение связанного однородного рекуррентного соотношения, а $x_1$ и $x_2$ — его корни.

• Если $x \ ne x_1$ и $x \ ne x_2$, то $a_t = Ax ^ n$

• Если $x = x_1$, $x \ ne x_2$, то $a_t = Anx ^ n$

• Если $x = x_1 = x_2$, то $a_t = An ^ 2x ^ n$

Если $x \ ne x_1$ и $x \ ne x_2$, то $a_t = Ax ^ n$

Если $x = x_1$, $x \ ne x_2$, то $a_t = Anx ^ n$

Если $x = x_1 = x_2$, то $a_t = An ^ 2x ^ n$

пример

Пусть неоднородное рекуррентное соотношение имеет вид $F_n = AF_ {n – 1} + BF_ {n-2} + f (n)$ с характеристическими корнями $x_1 = 2$ и $x_2 = 5$. Пробные решения для различных возможных значений $f (n)$ следующие:

е (п)	Пробные решения
4
5,2 н	An2 n
8,5 n	An5 n
4 н	A4 н
2n 2 + 3n + 1	Ан 2 + Бн + С

проблема

Решите рекуррентное соотношение $F_n = 3F_ {n-1} + 10F_ {n-2} + 7.5 ^ n$, где $F_0 = 4$ и $F_1 = 3$

Решение

Это линейное неоднородное отношение, где ассоциированное однородное уравнение имеет вид $F_n = 3F_ {n-1} + 10F_ {n-2}$ и $f (n) = 7,5 ^ n$.

Характеристическое уравнение его связанного однородного отношения —

$$x ^ 2 - 3x -10 = 0$$

Или $(x - 5) (x + 2) = 0$

Или $x_1 = 5$ и $x_2 = -2$

Следовательно, $a_h = a.5 ^ n + b. (- 2) ^ n$, где a и b — постоянные.

Поскольку $f (n) = 7,5 ^ n$, то есть в форме $cx ^ n$, разумным пробным решением at будет $Anx ^ n$.

$a_t = Anx ^ n = An5 ^ n$

После помещения решения в рекуррентное соотношение мы получаем —

$An5 ^ n = 3A (n - 1) 5 ^ {n-1} + 10A (n - 2) 5 ^ {n-2} + 7,5 ^ n$

Разделив обе стороны на $5 ^ {n-2}$, получим

$An5 ^ 2 = 3A (n - 1) 5 + 10A (n - 2) 5 ^ 0 + 7,5 ^ 2$

Или $25An = 15An - 15A + 10An - 20A + 175$

Или 35 $​​= 175$

Или $A = 5$

Итак, $F_n = An5 ^ n = 5n5 ^ n = n5 ^ {n + 1}$

Решение рекуррентного отношения можно записать в виде —

$F_n = a_h + a_t$

$= А.5 ^ п + Ь. (- 2) ^ п + n5 ^ {п + 1}$

Положив значения $F_0 = 4$ и $F_1 = 3$, в приведенном выше уравнении получим $a = -2$ и $b = 6$

Следовательно, решение —

$F_n = n5 ^ {n + 1} + 6. (- 2) ^ n -2,5 ^ n$

Генерация функций

Генерирующие функции представляют последовательности, где каждый член последовательности выражается в виде коэффициента переменной x в формальном степенном ряду.

Математически, для бесконечной последовательности, скажем, $a_0, a_1, a_2, \ dots, a_k, \ dots,$ производящая функция будет —

$$G_x = a_0 + a_1x + a_2x ^ 2 + \ dots + a_kx ^ k + \ dots = \ sum_ {k = 0} ^ {\ infty} a_kx ^ k$$

Некоторые области применения

Генерирующие функции могут быть использованы для следующих целей —

• Для решения различных задач подсчета. Например, количество способов внести изменения для рупий. 100 примечание с примечаниями достоинств Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 и Rs.50

• Для решения рекуррентных отношений

• Для доказательства некоторых комбинаторных тождеств

• Для нахождения асимптотических формул для членов последовательностей

Для решения различных задач подсчета. Например, количество способов внести изменения для рупий. 100 примечание с примечаниями достоинств Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 и Rs.50

Для решения рекуррентных отношений

Для доказательства некоторых комбинаторных тождеств

Для нахождения асимптотических формул для членов последовательностей

Проблема 1

Каковы производящие функции для последовательностей $\ lbrace {a_k} \ rbrace$ с $a_k = 2$ и $a_k = 3k$?

Решение

Когда $a_k = 2$, производящая функция, $G (x) = \ sum_ {k = 0} ^ {\ infty} 2x ^ {k} = 2 + 2x + 2x ^ {2} + 2x ^ {3} + \ точки$

Когда $a_ {k} = 3k, G (x) = \ sum_ {k = 0} ^ {\ infty} 3kx ^ {k} = 0 + 3x + 6x ^ {2} + 9x ^ {3} + \ dots \ точки$

Проблема 2

Что является производящей функцией бесконечного ряда; $1, 1, 1, 1, \ dots$?

Решение

Здесь $a_k = 1$ для $0 \ le k \ le \ infty$

Следовательно, $G (x) = 1 + x + x ^ {2} + x ^ {3} + \ dots \ dots = \ frac {1} {(1 - x)}$

Для $a_k = a ^ {k}, G (x) = \ sum_ {k = 0} ^ {\ infty} a ^ {k} x ^ {k} = 1 + ax + a ^ {2} x ^ { 2} + \ dots \ dots \ dots = 1 / (1 - топор)$

Для $a_ {k} = (k + 1) G (x) = \ sum_ {k = 0} ^ {\ infty} (k + 1) x ^ {k} = 1 + 2x + 3x ^ {2} \ dots \ dots \ dots = \ frac {1} {(1 - x) ^ {2}}$

Для $a_ {k} = c_ {k} ^ {n}, G (x) = \ sum_ {k = 0} ^ {\ infty} c_ {k} ^ {n} x ^ {k} = 1 + c_ {1} ^ {n} x + c_ {2} ^ {n} x ^ {2} + \ dots \ dots \ dots + x ^ {2} = (1 + x) ^ {n}$

Для $a_ {k} = \ frac {1} {k!}, G (x) = \ sum_ {k = 0} ^ {\ infty} \ frac {x ^ {k}} {k!} = 1 + x + \ frac {x ^ {2}} {2!} + \ frac {x ^ {3}} {3!} \ dots \ dots \ dots = e ^ {x}$