Дискретная математика - рекуррентное соотношение
В этой главе мы обсудим, как рекурсивные методы могут выводить последовательности и использоваться для решения задач подсчета. Процедура поиска членов последовательности рекурсивным способом называется рекуррентным отношением . Мы изучаем теорию линейных рекуррентных соотношений и их решения. Наконец, мы вводим производящие функции для решения рекуррентных отношений.
Определение
Отношение рекуррентности - это уравнение, которое рекурсивно определяет последовательность, в которой следующий член является функцией предыдущих членов (выражая $ 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 | a 1 = 1, a 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 (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 $
пример
Пусть неоднородное рекуррентное соотношение имеет вид $ 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
Для решения рекуррентных отношений
Для доказательства некоторых комбинаторных тождеств
Для нахождения асимптотических формул для членов последовательностей
Проблема 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} $