В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 9
Текст из файла (страница 9)
Решение. Для начала найдем, что a0 = 1 и заменим начальные условия на эквивалентные a0 = 1, a1 =cos α. Характеристическим уравнением для последовательности является x2 − 2x cos α + 1 = 0. Оно имеетдва комплексно сопряженных корня α1 = cos α − i sin α и α2 = cos α + i sin α кратности один каждый. Таким образом, общее решение данного линейного однородного рекуррентного соотношения с постояннымикоэффициентами выписывается в виде an = C1 (cos α − i sin α)n +C2 (cos α + i sin α)n . Из начальных условийполучаем, что C1 + C2 = 1, (C1 +C2 ) cos α − (C1 −C2 ) sin α = cos α ⇒ C1 = C2 = 12 . Таким образом, окончательно1e−inα + einαan = ((cos α − i sin α)n + (cos α + i sin α)n ) == cos nα.222.
Вывести общее выражение для определителя трехдиагональной матрицы порядка n. Решение. Трехдиагональная матрица порядка n имеет следующий вид:a b 0 0 ... 0 0 0c a b 0 . . . 0 0 00 c a b . . . 0 0 00 0 c a . . . 0 0 0An = . . . . . . . . . . . . . . . . . . .0 0 0 0 . . . a b 0 0 0 0 0 . . . c a b0 0 0 0 .
. . 0 c a n×n30ГЛАВА 1. КОМБИНАТОРИКАОбозначим det An = ∆n . Начальные условия для нее выписываются достаточно просто:∆0 = 1 (по договоренности),∆1 = det a = a.Далее, для n > 2, используя разложение по первой строке, а затем по первому столбцу легко получить, что ∆n =a∆n−1 − bc∆n−2 ⇔ ∆n+2 − a∆n+1 + bc∆n = 0. Характеристическое уравнение для данного линейного однородногорекуррентного соотношения с постоянными коэффициентами имеет вид x2 − ax + bc = 0.
В зависимости от того,равен или не равен нулю его дискриминант D = a2 − 4bc, возможны два случая:(a) D 6= 0. Тогда∆n = C1!n√a − a2 − 4bc+C22!n√a + a2 − 4bc,2где C1 и C2 определяются из уравнений(C1 +C2 = 0,−C1 +C2 = √a.a2 −4bcРешением являются√a − a2 − 4bcC1 = − √,2a2 − 4bc1√a + a2 − 4bcC2 = √,2a2 − 4bc1где квадратные корни являются алгебраическими и во всех случаях их значения полагаются одинаковыми.Таким образом, в случае некратных корней!n+1!n+1√√11a − a2 − 4bca + a2 − 4bc∆n = − √+√.22a2 − 4bca2 − 4bc(b) D = 0. Тогда∆n = (C1 +C2 n) a n2,где C1 и C2 определяются из уравненийC1 = 1,C1 +C2 = 2.Решением являются C1 = C2 = 1. Таким образом, в случае кратных корней a n∆n = (1 + n).23. Найти общие решения рекуррентных соотношений:(a) an+2 + 3an = 0. Решение.
Характеристическое уравнение для данной√последовательностиx2 + 3 = 0 имеет два комплекс√но сопряженных мнимых корня кратности один: α1 = −i 3 и α2 = i 3. Таким образом, общее решение данного линейного однородного рекуррентного соотношения с постоянными коэффициентами выписывается ввиде √ n √ nnan = C1 −i 3 +C2 i 3 = C1 3 2 (in + (−i)n ) =nnπnπn πnπn − i sin+C2 3 2 cos+ i sin.C1 3 2 cos2222(b) an+2 + 2an+1 + an = 0.
Решение. Характеристическое уравнение для данной последовательности x2 + 2x + 1 = 0 имеет одинвещественный корень α = −1 кратности два. Таким образом, общее решение данного линейного однородного рекуррентного соотношения с постоянными коэффициентами выписывается в виде an =(C1 +C2 n) (−1)n .311.2. ПРОИЗВОДЯЩИЕ ФУНКЦИИ(c) an+3 + 10an+2 + 32an+1 + 32an = 0.
Решение. Характеристическое уравнение для исходной последовательности имеет вид x3 + 10x2 +32x + 32 = 0. Оно имеет вещественный корень α1 = −2 кратности один и вещественный корень α2 =−4 кратности два. Таким образом, общее решение данного линейного однородного рекуррентного соотношения с постоянными коэффициентами выписывается в виде an = C1 (−2)n + (C2 +C3 n) (−4)n =(−2)n (C1 + (C2 +C3 n) 2n ).4.(a) Пусть {an } и {bn } — две последовательности, члены которых связаны соотношениямиan+1 = p1 an + q1 bn ,bn+1 = p2 an + q2 bn ,∆ = p1 q2 − p2 q1 6= 0,где p1 , q1 , p2 , q2 — данные числа.
Найти выражения для an и bn , считая, что a1 и b1 заданы. Решение. Найдем a0 , b0 из системы уравненийa1 = p1 a0 + q1 b0 ,⇐⇒b1 = p2 a0 + q2 b0 ;(1 b1a0 = q2 a1 −q,∆p2 a1 −p1 b1b0 = −.∆и заменим начальные условия на эквивалентные при n = 0. Пусть q1 6= 0. Выражаем из первого уравненияbn =1(an+1 − p1 an ) ,q1bn+1 =1(an+2 − p1 an+1 )q1и подставляем их во второе:11(an+2 − p1 an+1 ) = p2 an + q2 (an+1 − p1 an ) .q1q1Преобразуем последнее равенство и получаемan+2 − (p1 + q2 ) an+1 + ∆an = 0.q21и α2 =Корни этого характеристического уравнения равны α1 = 2 p1 + q2 − (p1 + q2 ) − 4∆q1(p1 + q2 )2 − 4∆ , где корень алгебраический и один и тот же в обоих случаях.
Таким обра2 p1 + q2 +зом, в случае некратных корнейqqnn(p1 + q2 )2 − 4∆p1 + q2 + (p1 + q2 )2 − 4∆ , +C2 an = C1 22qqnnp1 + q2 − (p1 + q2 )2 − 4∆p1 + q2 + (p1 + q2 )2 − 4∆ . +C4 bn = C3 22p1 + q2 −В случае кратных корнейp1 + q2 nan = (C1 +C2 n),2p1 + q2 nbn = (C3 +C4 n).2Подставляя эти выражения в исходную систему, находим зависимость между C1 , C2 , C3 и C4 , оставляющуюдве степени свободы (поскольку система не вырождена).
Затем, подставляем начальные условия a0 , b0 инаходим константы.Если q1 = 0, то проведем те же рассуждения, поменяв a на b и b на a. При этом необходимо p2 6= 0. Если жеp2 = 0 & q1 = 0, то ∆ = 0, что противоречит условию. Таким образом, решение найдено.32ГЛАВА 1. КОМБИНАТОРИКА(b) Найти решение системы рекуррентных соотношенийan+1 = 3an + bn ,bn+1 = −an + bn ,a1 = 14, b1 = −6. Решение. Воспользуемся результатом упражнения 4a (в данном случае корни кратные).an = (C1 +C2 n) 2n ,bn = (C3 +C4 n) 2n .Подставляя в исходную систему, находим C4 = −C2 , C3 = −C1 + 2C2 , то естьan = (C1 +C2 n) 2n ,bn = (−C1 + 2C2 −C2 n) 2n .Далее, учитывая, что a0 = 5, b0 = −1, получаем C1 = 5, C2 = 2.
Таким образом, окончательноan = (5 + 2n) 2n ,bn = (−1 − 2n) 2n .5. Найти решение системы рекуррентных соотношений an+1 = −an + 2bn ,bn+1 = 2an + 2bn ,a0 = 3, b0 = 1. Решение. Решим задачу на языке матриц. Система задается матрицей−1 2A=2 2и начальным вектором 3X0 =1Собственные значения A равны λ1 = −2, λ2 = 3 с собственными векторами соответственно121 2−155собственных векторов составим матрицу Q =⇒Q = 2. Далее,2 −1− 155A = QΛQ−1 ,Yn = Q−1 Xn =⇒ Yn+1 = ΛYn , 12и. Из2−1Yn = ΛnY0 =⇒ Xn = QΛn Q−1 X0 .В то же времяnA=n−1QΛ Q n1 232 −100(−2)n152525− 151=525· 3n + 45 · (−2)n· 3n − 25 · (−2)n2545· 3n − 25 (−2)n.· 3n + 15 (−2)nТаким образом,an = 3n − (−2)n+1 ,bn = 2 · 3n − (−2)n .6.
Решить рекуррентное соотношение an+3 − 6an+2 + 11an+1 − 6an = 4n, a0 = 1, a1 = 3, a2 = 4. Решение. Характеристическое уравнение для решения однородного соотношения последовательности x3 −6x2 + 11x − 6 = 0 имеет три различных вещественных корня кратности один каждый: α1 = 1, α2 = 2, α3 = 3. Такимобразом, общее решение однородного соотношения имеет вид a0n = A · 1n + B · 2n + C · 3n .
Частное решение имеет смысл искать в виде a00n = n (αn + β ) · 1n . Подставляя его в исходное уравнение и приравнивая коэффициентыпри равных степенях, получаем α = 1, β = 2, откуда an = a0n + a00n = A + B · 2n + C · 3n + n (n + 2). Теперь можноопределить константы A, B, C, исходя из начальных условий: A + B +C = 1, A = 1,A + 2B + 3C = 0,B = 1,⇐⇒A + 4B + 9C = −4;C = −1.Итак, окончательно, an = 1 + 2n − 3n + n (n + 2).331.2. ПРОИЗВОДЯЩИЕ ФУНКЦИИ7. Решить рекуррентные соотношения:(a) an+1 − an = n, a1 = 1. Решение.
Легко видеть, что a0 = 1. Заменим начальное условие на эквивалентное a0 = 1. Характеристическое уравнение для однородного соотношения x − 1 = 0 имеет один корень α = 1 кратности один. Такимобразом, общее решение однородного соотношения имеет вид a0n = A. Частное решение имеет смысл искатьв виде a00n = n (β n + γ). Подставляя его в исходное уравнение и приравнивая коэффициенты при равных степенях, получаем β = 12 , γ = − 12 , откуда an = a0n + a00n = A + 12 n (n − 1). Из начальных условий находим, чтоA = 1 и an = 1 + n2 .(b) an+2 + 2an+1 − 8an = 27 · 5n , a1 = −9, a2 = 45.
Решение. Легко видеть, что a0 = 0. Заменим начальные условия на эквивалентные a0 = 0, a1 = −9.Характеристическое уравнение для однородного соотношения x2 + 2x − 8 = 0 имеет два корня кратности один каждый α1 = −4, α2 = 2. Таким образом, общее решение однородного соотношения имеет видa0n = A (−4)n + B · 2n . Частное решение имеет смысл искать в виде a00n = β · 5n .
Подставляя его в исходное уравнение и приравнивая коэффициенты при равных степенях, получаем β = 1, откуда an = a0n + a00n =A (−4)n + B · 2n + 5n . Из начальных условий находим, что A = 2, B = −3 и an = 2 · (−4)n − 3 · 2n + 5n .8. Решить систему линейных рекуррентных соотношений: an+1 = −bn + n,bn+1 = an + 2bn + 1,a0 = 1, b0 = −2. Решение. Заметим предварительно, что b1 = −2. Далее, выражая из второго уравнения bn+2 = an+1 + 2bn+1 + 1и подставляя туда an+1 = −bn + n, получаем линейное рекуррентное соотношение относительно bn : bn+2 − 2bn+1 +bn = n + 1.
Его характеристическое уравнение имеет корень α = 1 кратности два, в связи с чем общим решениемоднородного соотношения является b0n = A + Bn, а частное решение имеет смысл искать в виде b00n = n2 (β n + γ).2Подставляя последнее в уравнение, находим α = 61 , β = 0. Таким образом, bn = b0n + b00n = A + Bn + n6 . Используяначальные условия на bn , получаем A = −2, B = − 61 . Таким образом,bn = −2 −n n3+ ,66an = 2 +7 (n − 1) (n − 6)3211−= 1 + n + n2 − n3 .66326Упражнения.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
