Элементы дискретной математики. К. Д. Ушинского Элементы дискретной математики Ярославль, 2005 па. Корнилов, ни. Никулина, Семенова О. Г. Элементы дискретной математики. Учебное пособие
 Скачать 0.81 Mb.
|
|
0<=P(A)<=1. 2. Любое событие может либо произойти, либо не произойти. Это означает, что сумма вероятностей некоторого события Аи события, ему противоположного, равна 1. Р(А)+Р( A )=1 ( где A противоположное событие или условие, по отношению к А. Часто для вычисления вероятностей используют переход к противоположному событию Р(А)=1–Р( A ). Задача В некоторой детской игре для начала игры участнику нужно обязательно выбросить пятерку. Поскольку граней на косточке всего шесть, то кажется, что уж в шести бросках пятерка выпадет наверняка. Найдите вероятность этого события. Решение. Р(хоть один раз из шести выпадет “5”)=1–Р(ни разу из шести не выпадет “5”)= 6651 0 ) 6 1 1 ( 1 6 ) 1 6 ( 1 6 6 6 6 6 6 5 5 5 5 5 5 1 6 6 6 = − − = − − = ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ − 3. Иногда разбивают сложный благоприятный исход на простейшие или стандартные. Р(А или В)=Р(А)+Р(В)-Р(А и В – вероятность того, что произойдет событие А или событие В, равна сумме вероятностей этих событий минус вероятность того, что события Аи В произойдут одновременно. Задача. Игральную кость подбрасывают один раз. Какова вероятность выпадения либо четного числа очков, либо числа, кратного трем Решение. Введем обозначения А – выпадения либо четного числа очков, либо числа, кратного трем В – выпадения четного числа очков С – выпадения числа, кратного трем. Р(А)=Р(В или С)=Р(А)+Р(В)-Р(В и С. Задача. Игральную кость подбрасывают один раз. Найти вероятность, что выпадет число очков не менее пяти Решение. Р(выпадение числа очков не менее пяти)=Р(выпадение «5»)+Р(выпадение «6») = =1/6+1/6 =1/3. Бином Ньютона Правила и формулы комбинаторики часто используют при решении различных задач математики. Комбинаторные доказательства отличаются простотой и особой изысканностью. Рассмотрим применение комбинаторики к доказательству формулы бинома Ньютона. Биномом Ньютона называют формулу для вычисления выражения (а для натуральных n. Теорема Доказательство. Данную формулу можно доказать методом математической индукции. Ниже представлено комбинаторное доказательство. Запишем (a+b) n в виде произведения (a+b) n =(a+b) ⋅ (a+b) ⋅ …⋅ (a+b). Раскроем скобки в правой части этого равенства и запишем все слагаемые в виде произведения n сомножителей аи в том порядке, в котором они появляются. Например, (a+b) 2 запишется в виде (a+b) 2 =(a+b) ⋅ (a+b)=aa+ab+ba+bb, а (a+b) 3 – в виде (a+b) 3 =(a+b) ⋅(a+b)⋅(a+b) =aaa+aab+aba+abb+baa+bab+bba+bbb. Видно, что в обе формулы входят все размещения с повторениями, составленные из буква и b по две (три) буквы в каждом. В общем случае – после раскрытия скобок получим всевозможные размещения с повторениями буква и b, состоящие из n элементов. Используя коммутативность, приведем подобные члены. Подобными будут члены, содержащие одинаковое количество буква (тогда и букв b в них будет одинаковое количество. Членов, в которые входит k букв a и, следовательно, (n–k) букв b ровно Р, n–k)= k n C . Отсюда вытекает, что после приведения подобных членов выражение a k b n-k войдет с коэффициентом k n C , поэтому формула примет вид Задача. Раскрыть скобки и привести подобные члены в выражении (3х+2у) 4 , используя формулу бинома Ньютона. Решение. 4 3 2 2 3 4 4 3 2 2 3 4 0 4 4 4 1 3 3 4 2 2 2 4 3 1 1 4 4 0 0 4 4 81 216 216 96 16 81 2 27 4 4 9 6 8 3 4 16 ) 2 ( ) 3 ( ) 2 ( ) 3 ( ) 2 ( ) 3 ( ) 2 ( ) 3 ( ) 2 ( ) 3 ( ) 2 Задача. Найти коэффициент при х в разложении (2х+3) 6 Решение. В данной задаче требуется найти коэффициент только при х, поэтому нет необходимости раскрывать все выражение по формуле бинома Ньютона. Достаточно рассмотреть только одно слагаемое 30 2 2 4 2 2 6 2 2 6 4860 81 4 15 3 4 ! 4 ! 2 ! 6 Таким образом, х в разложении (х будет иметь коэффициент 4 860. Числа k n C называют биномиальными коэффициентами. С помощью бинома Ньютона легко доказать свойства биномиальных коэффициентов (чисел k n C ). Свойства биномиальных коэффициентов. Симметричность биномиальных коэффициентов Это свойство следует из тождества (a+b) n =(b+a) n . Разложим обе части равенства по биному Ньютона и рассмотрим коэффициенты при a k ⋅b n-k . Справа коэффициент равен, а слева Основное свойство биномиальных коэффициентов Если в формуле бинома Ньютона положить ах то получим, (1+x) n = n n n k k n n n n x C x C x C x C C ⋅ + + ⋅ + + ⋅ + ⋅ + 2 2 1 Если положить n равным n-1 то верно равенство (1+x) n-1 = 1 1 1 1 2 2 1 1 1 Умножим обе части этого равенства на (х, получим (1+x) n = ) 1 ( ) ( 1 1 1 1 2 2 1 1 1 Выражение в левой части равенства снова разложим по формуле бинома Ньютона. Рассмотрим коэффициент при х k . Слева он будет равен k n C . В правой части член содержащий х k появится дважды приумножении на 1 и приумножении на х. Поэтому коэффициент в правой части при х k имеет вид k n k n C C 1 1 1 − − − + . Слева и справа стоит один и тот же многочлен, поэтому коэффициенты при х k слева и справа должны быть одинаковыми. Поэтому k n k n k n C C C 1 Сумма биномиальных коэффициентов n n n k n n n C C C C 2 Воспользуемся формулой бинома Ньютона, в которой положим аи. Тогда n n n k n n n C C C C ) 1 1 ( 1 Знакопеременная сумма биномиальных коэффициентов 0 ) 1 ( ) 1 ( 2 Воспользуемся формулой бинома Ньютона в которой положим аи. Сумма квадратов биномиальных коэффициентов n n n n k n n n C C C C C 2 2 2 2 1 2 0 ) ( ) ( ) ( ) ( = + + + + + . Как и при доказательстве основного свойства, используем равенство (1+x) n = n n n k k n n n n x C x C x C x C C ⋅ + + ⋅ + + ⋅ + ⋅ + 2 2 1 Умножим обе части этого равенства на (х (1+x) 2n = × ⋅ + ⋅ + + ⋅ + + ⋅ + ⋅ + − − ) ( 1 1 2 2 1 0 n n n n n n k k n n n n x C x C x C x C x C C ) ( 1 1 1 1 1 2 2 Выражение в левой части равенства снова разложим по формуле бинома Ньютона. Рассмотрим коэффициент при х n . Слева он будет равен n n C 2 . В правой части член, содержащий х n , появится n раз приумножении на 0 n C , приумножении на x C n ⋅ 1 , итак далее. Используем свойство симметричности биномиальных коэффициентов, получим коэффициент при х n в правой части равенства 2 2 2 1 2 Так как слева и справа стоит один и тот же многочлен, то коэффициенты при х n слева и справа должны быть одинаковыми. Поэтому n n n n k n n n C C C C C 2 2 2 2 1 Треугольник Паскаля. Другая, известная как треугольник Паскаля, интерпретация для биномиальных коэффициентов получается, если рассмотреть на бесконечной шашечной доске количество различных путей шашки отданной клетки до всех клеток доски. Возьмем шахматную доску, ограниченную только с одной стороны, и поставим на поле A (черного цвета) нулевой горизонтали шашку. Двигаясь по правилам игры в шашки, она может попасть на любое поле черного цвета из области, ограниченной прямыми AB и AC. Напишем на каждом поле число способов, которыми можно попасть на данное поле. Получим А 1 1 1 1 2 1 1 3 3 1 В С Эти числа обычно изображают в виде треугольника, при этом каждое число равно сумме двух элементов предыдущей строки, между которыми оно находится. Этот треугольник часто называют треугольником Паскаля или арифметическим треугольником. 32 Арифметический треугольник можно записать ив таком виде 0 1 2 3 4 0 1 0 0 0 0 1 1 1 0 0 0 2 1 2 1 0 0 3 1 3 3 1 0 4 1 4 6 4 1 В данном треугольнике, в каждой клетке хранится количество способов попасть в эту клетку из клетки (0, 0) , если ходить разрешается только вниз и по диагонали вправо. Каждое число треугольника равно сумме числа, стоящего выше него, и числа, расположенного наискосок влево. На пересечение й вертикали и й горизонтали можно попасть за n шагов, k из которых будут по диагонали, n – k по вертикали. Поэтому количество способов попасть в клетку с координатами (n, k) равно k n C . Отметим еще следующие особенности арифметического треугольника все элементы, расположенные выше главной диагонали, равны нулю, а нулевой столбец состоит из единиц Числа, стоящие в й строке, являются коэффициентами в разложении бинома (1+x) n по степеням x. Поэтому их называют также биноминальными коэффициентами Задача. Раскрыть скобки и привести подобные члены в выражении (х+у) 5 Решение. Пятая строка треугольника Паскаля имеет вид 1 5 10 10 5 1. Поэтому (х+у) 5 =1x 0 y 5 +5x 1 y 4 +10x 2 y 3 +10x 3 y 2 +5x 4 y 1 +1x 5 y 0 С помощью треугольника Паскаля можно доказать свойства биномиальных коэффициентов. (Смотри упражнения) Полиномиальная формула Полиномом называют выражение вида (x 1 +x 2 +…x Полиномиальной формулой называют формулу для вычисления значения выражений (x 1 +x 2 +…x k ) n для различного числа слагаемых и различных натуральных степеней n. Теорема ∑ ∑ ∑ = + + + = + + + = = = ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ n k k k n k k k k m k k m k m k k m n m i i m m m m x x x k k k n x x x k k k P x 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 Доказательство. Формула доказывается аналогично формуле бинома Ньютона Запишем (x 1 +x 2 +…x k ) n в виде произведения n сомножителей (x 1 +x 2 +…x k )·(x 1 +x 2 +…x k )·…·(x 1 +x 2 +…x Раскроем скобки в правой части этого равенства и запишем все слагаемые в виде произведения n сомножителей x 1 , x 2 ,…,x k в том порядке, в котором они появляются. Получим всевозможные размещения с повторениями букв x 1 , x 2 ,…,x k , состоящие из n элементов. Используем коммутативность и приведем подобные члены. Подобными будут члены, содержащие одинаковое количество множителей x 1 , x 2 ,…,x k . Членов, в которые входит k 1 множителей х, k 2 множителей хи так далее k m множителей х m , ровно Р m ). Отсюда вытекает, что после приведения подобных членов выражение m k m k k x x x 2 1 2 1 ⋅ ⋅ войдет с коэффициентом ) ,..., , ( 2 1 m k k k P . Поэтому формула примет вид ∑ ∑ = + + + = = ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ n k k k k m k k m n m i i m m x x x k k k P x 2 1 2 1 1 2 1 Свойства чисел Р) 1. ∑ = + + + = n k k k n m m m k k k P 2 1 2 Доказательство. Если в полиномиальной формуле положить х 1 =х 2 =…=х m =1, то получим требуемое равенство. 2. ) 1 ,..., , ( ) ,..., 1 , ( ) ,..., , 1 ( ) ,..., , ( 2 1 2 1 2 1 2 Доказательство. Умножим обе части равенства ∑ ∑ − = + + + − = = ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ 1 2 1 2 1 1 1 2 1 2 1 ) ,..., , ( n k k k k m k k m n m i i m m x x x k k k P x на (х 1 +х 2 +…+х m ). Получим ) )( ) ,..., , ( ( 2 1 1 2 1 2 1 1 2 1 2 Применим клевой части полиномиальную формулу, а в правой части раскроем скобки и рассмотрим коэффициент при m k m k k x x x 2 1 2 1 ⋅ ⋅ . Слева он будет равен ) ,..., , ( 2 1 m k k k P . В правой части член, содержащий m k m k k x x x 2 1 2 1 ⋅ ⋅ , появится m раз приумножении на х, приумножении на хи так далее коэффициент прибудет равен ) 1 ,..., , ( ) ,..., 1 , ( ) ,..., , 1 ( 2 1 2 1 2 1 − + + − + − m m m k k k P k k k P k k k P . Слева и справа стоит один и тот же многочлен, следовательно, коэффициенты при m k m k k x x x 2 1 2 1 ⋅ ⋅ слева и справа должны быть равны. Поэтому ) 1 ,..., , ( ) ,..., 1 , ( ) ,..., , 1 ( ) ,..., , ( 2 1 2 1 2 1 2 Задача. Раскрыть скобки и привести подобные члены в выражении (x+y+z) 4 , используя полиномиальную формулу. Решение. Ясно, что коэффициенты при x 2 yz и xy 2 z равны. Поэтому достаточно найти коэффициенты для таких разбиений n=k 1 +k 2 +…k m , что k 1 ≥ k 2 ≥ … ≥ k m , а потом переставлять показатели всеми возможными способами. Для нашего примера имеем 4=4+0+0; 4=3+1+0; 4=2+2+0; 4=2+1+1; Р Р Р Р. (x+y+z) 4 = Задача. Найти коэффициенты при х после раскрытия скобок и приведения подобных членов в выражении (2+х 2 -х 3 ) 9 Решение. В задаче нас интересует только коэффициент при х, поэтому нет необходимости искать все коэффициенты. Член, содержащий х, появится только один раз как слагаемое вида 2 7 (х 2 ) 1 (-х 3 ) 1 , коэффициент при этом члене согласно полиномиальной формуле будет равен Р, 1, 1)=72. Следовательно, коэффициент при х равен (–1) ⋅ 2 7 ⋅ 72 =–9 216. Задача. Найти коэффициенты при х после раскрытия скобок и приведения подобных членов в выражении (1+х 2 +х 5 ) 8 Решение. Данная задача отличается от предыдущей тем, что член, содержащий х, появится два раза как слагаемое видах хи (х (х. В первом случае коэффициент будет равен Р, 6, 0)=28, во втором – Р, 1, 2)=168. Следовательно, коэффициент при х равен 28+168=196. Рекуррентные соотношения. Задача. Сколькими способами можно замостить прямоугольную доску размером 2 х 7 костями домино, если все кости считать одинаковыми и учитывать только положение кости горизонтальное или вертикальное Решение. Обозначим через Ф) количество способов замостить костями домино прямоугольную доску размером 2 х k. Угловая клетка может быть закрыта одним из двух способов либо костью, которая лежит вертикально, тогда оставшуюся k–1 кость можно положить Ф) способами, либо костью, которая лежит горизонтально, тогда еще одну кость можем положить только горизонтально, а оставшиеся k–2 кости можно уложить Ф) способами. Используя правило суммы, приходим к соотношению Ф(к)=Ф(к–1)+Ф(к–2). Учитывая, что Ф(0)=Ф(1)=1, можем для любого значения k найти ответ Ф, Ф, Ф, Ф, Ф, Ф. Имеем 21 способ замостить костями домино прямоугольную доску размером 2 х 7. При решении многих комбинаторных (и не только) задач часто встречается способ, когда задачу с заданными значениями параметров сводят к аналогичной задаче, но уже с меньшими значениями параметров. Таким образом, можно довести задачу до простой. Данный метод решения задач носит название метода рекуррентных соотношений. (От латинского слова recurrere – возвращаться. Пример. Используя метод рекуррентных соотношений, можно по-новому вывести формулу для вычисления числа перестановок из k предметов. Обозначим за Р) количество перестановок из элементов k типов. В перестановке на первом месте может быть любой из k предметов, а оставшиеся k–1 предмет можно в каждом из этих случаев переставить Р) способами. По правилу произведения получаем формулу Р(k)=k·Р(k-1). Далее замечаем, что Р, и получаем, что Р Числа Фибоначчи Формула, которую мы получили при решении задачи о домино, впервые была опубликована в книге “Liber Abaci”, появившейся в 1202 году, где итальянский математик Фибоначчи среди многих других задач привел следующую Пара кроликов приносит разв месяц приплод из двух крольчат (самки и самца, причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если вначале года была одна пара кроликов Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. А еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов. Обозначим через F(n) количество пар кроликов по истечении n месяцев сначала года. Мы видим, что через n+1 месяцев будут эти F(n) пари еще столько новорожденных пар кроликов, сколько было в конце месяца n—1, то есть еще F(n–1) пар кроликов. Иными словами, имеет место рекуррентное соотношение F(n+1)=F(n)+F(n-1). Так как, по условию, F(0)=1 и F(1)=2, то последовательно находим F(2)=3, F(3)=5 F(4)=8 и т. д. Полученные числа называют числами Фибоначчи. Чтобы найти F(12), нам придется последовательно вычислить F(3), F(4), … F(11), что достаточно долго. А если нам необходимо было бы вычислить F(100), то это займет еще больше времени. Попробуем выразить закономерность последовательности Фибоначчи с помощью расчетной формулы (вместо неявного рекуррентного соотношения. Для этого присвоим двоичный номер каждой паре кроликов. Единицам соответствуют месяцы появления на свет одной из пар предков данной пары (включая и исходную, а нулями – все остальные месяцы. Например, последовательность 010010100010 устанавливает такую генеалогию – сама пара появилась в конце го месяца, ее родители – в конце го месяца, дед – в конце го месяца, прадед – в конце второго месяца. Исходная пара кроликов зашифровывается при этом последовательностью 000000000000. в последовательности не могут идти подряд две единицы, так как кролики приносят приплод только на второй месяц после рождения. Тем самым устанавливается связь между числами Фибоначчи и следующей комбинаторной задачей найти число последовательностей, состоящих из нулей и единиц, в которых никакие две единицы не идут подряд. Число таких последовательностей, в которые входит ровно k единиц и n—k нулей, равно k k n C 1 + − . Так как при этом должно выполняться неравенство k<=n–k+1, то k изменяется от 0 до целой части числа (n+1)/2. Применяя правило суммы, получаем F(n)= p p n n n n C C C C 1 2 1 1 0 1 + − − + + + + + , где p – целая часть числа (n+1)/2. К сожалению, задачу нельзя считать решенной, так как, хотя получено выражение, зависящее от n, его вычисление оказывается даже сложнее рекуррентных расчетов. Желаемую формулу можно получить совсем другим способом. Решение рекуррентных соотношений Рекуррентное соотношение имеет порядок k, если оно позволяет выразить f(n+k) через f(n), f(n+1), …, f(n+k-1). Пример. f(n+2)=f(n)f(n+1)-3f 2 (n+1)+1 – рекуррентное соотношение второго порядка. f(n+3)=6f(n)f(n+2)+f(n+1) – рекуррентное соотношение третьего порядка. Если задано рекуррентное соотношение го порядка, то ему могут удовлетворять бесконечно много последовательностей, так как первые k элементов последовательности можно задать произвольно – между ними нет никаких соотношений. Но если первые k членов заданы, то все остальные элементы определяются однозначно. Пользуясь рекуррентным соотношением и начальными членами, можно один за другим выписывать члены последовательности, при этом рано или поздно мы получим любой её член. Однако если необходимо узнать только один определенный член последовательности, то нерационально вычислять все предыдущие. В этом случае удобнее иметь формулу для вычисления го члена. Решением рекуррентного соотношения называется любая последовательность, для которой данное соотношение выполнено тождественно. Пример. Последовательность 2, 4, 8, …, 2n является решением для соотношения f(n+2)=3·f(n+1) – 2·f(n). Доказательство Общий член последовательности имеет вид f(n)=2 n . Значит, f(n+2)= 2 n+2 , f(n+1)= При любом n имеет место тождество 2 n+2 =3·2 n+1 – 2·2 n . Следовательно, при подстановке последовательности 2 n в формулу f(n+2)=3f(n+1) – 2f(n) соотношение выполняется тождественно. Значит, 2 n является решением указанного соотношения. Решение рекуррентного соотношения го порядка называется общим, если оно зависит от k произвольных постоянных α 1 , α 2 , … α k и путем подбора этих постоянных можно получить любое решение данного соотношения. Пример. Дано рекуррентное соотношение f(n+2)=5f(n+1)-6f(n). Докажем, что его общее решение имеет вид f(n)= α 2 n + β3 n 38 1. Сначала докажем, что последовательность f(n)=α 2 n + β3 n является решением рекуррентного соотношения. Подставим данную последовательность в рекуррентное соотношение. f(n)= α 2 n + β 3 n , значит, f(n+1)= (α 2 n+1 + β 3 n+1 ), f(n+2)= α 2 n+2 + β 3 n+2 , тогда 5f(n+1)-6f(n)=5·( α 2 n+1 + β 3 n+1 )-6·( α 2 n + β 3 n )= α (5 2 n+1 –6 2 n )+ β (5 3 n+1 –6 3 n )= =α2 n ·(10–6)+ β 3 n ·(15 – 6)= α 2 n+2 + β 3 n+2 = f(n+2). Рекуррентное соотношение выполняется, следовательно, α 2 n + β 3 n является решением данного рекуррентного соотношения. 2. Докажем, что любое решение соотношения f(n+2)=5f(n+1)–6f(n) можно записать в виде f(n)= α 2 n + β 3 n . Но любое решение рекуррентного соотношения второго порядка однозначно определяется значениями первых двух членов последовательности. Поэтому достаточно показать, что для любых аи) найдутся α и β такие, что 2 α +3 β аи. Легко видеть, что система уравнений имеет решение для любых значений аи. Таким образом, f(n)= α 2 n + β 3 n является общим решением рекуррентного соотношения f(n+2)=5f(n+1)–6f(n). Линейные рекуррентные соотношения с постоянными коэффициентами Для решения рекуррентных соотношений общих правил нет, но существует часто встречающийся класс рекуррентных соотношений, для которых известен алгоритм их решения. Это – линейные рекуррентные соотношения с постоянными коэффициентами, те. соотношения вида f(n+k)=c 1 f(n+k-1)+c 2 f(n+k-2)+…+c k f(n). Найдем решение общего линейного рекуррентного соотношения с постоянными коэффициентами первого порядка. Линейное рекуррентное соотношение с постоянными коэффициентами первого порядка имеет вид f(n+1)=c f(n). Пусть а, тогда f(2)=c·f(1)=c·a, f(3)=c·f(2)=c 2 ·a, аналогично f(4)=c 3 ·a итак далее, заметим, что f(n)=c n-1 ·f(1). Докажем, что последовательность c n-1 ·f(1) является решением рекуррентного соотношения первого порядка. f(n)=c n-1 ·f(1), значит, f(n+1)=c n f(1). Подставляя это выражение в соотношение, получим тождество c n с c n-1 ·f(1). Рассмотрим теперь подробнее линейные рекуррентные соотношения с постоянными коэффициентами второго порядка, то есть соотношения вида 39 f(n+2)=C 1 ·f(n+1)+C 2 ·f(n). (*). Заметим, что все рассуждения сохраняются и для соотношений более высокого порядка. Свойства решений 1) Если последовательность x n является решением (*), то и последовательность α·x n тоже является решением. Доказательство. x n является решением (*), следовательно, выполняется тождество x n+2 =C 1 x n+1 +C 2 x n. Домножим обе части равенства на α. Получим α·x n+2 С С n )= С С Это означает, что αx n является решением (*). 2) Если последовательности x n и y n являются решениями (*), то и последовательность x n +y тоже является решением. Доказательство. x n и y n являются решениями, следовательно, выполняются следующие тождества x n+2 =C 1 x n+1 +C 2 x n y n+2 =C 1 y n+1 +C 2 y Выполним почленное сложение двух равенств x n+2 +y С С n + С С n = С n+1 + y С n +y n ). Это означает, что x n +y является решением (*). 3) Если r 1 является решением квадратного уравнения r 2 =С 1 r+С 2 , то последовательность (r 1 ) n является решением для соотношения (*). r 1 является решением квадратного уравнения r 2 =С 1 r+С 2 , значит, (r 1 ) 2 =C 1 Помножим обе части равенства на (r 1 ) n . Получим r 1 2 С С) r n r 1 n+2 С С Это означает, что последовательность (r 1 ) n является решением (*). Из этих свойств вытекает способ решения линейных рекуррентных соотношений с постоянными коэффициентами второго порядка 40 1. Составим характеристическое (квадратное) уравнение С С. Найдём его корни r 1, r 2. Если корни различны, то общее решение имеет вид f(n)= αr 1 n +βr 2 n 2. Найдём коэффициенты α и β. Пусть f(0)=a, f(1)=b. Система уравнений α + β а α·r 1 + β·r 2 =b имеет решение при любых аи. Этими решениями являются α=(b-a·r 2 )/(r 1 -r 2 ). β =(a·r 1 -b)/(r 1 -r 2 ). Задача. Найдем формулу для общего члена последовательности Фибоначчи. Решение. Характеристическое уравнение имеет вид х 2 =х+1 или х 2 -х-1=0, его корнями являются числа 2 5 1 ± , значит, общее решение имеет вид f(n)= n n ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ − + ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ + 2 5 1 2 5 1 β α . Как нетрудно видеть, изначальных условий f(0)=0, f(1)=1 вытекает, что α=−β=1/√5, и, следовательно, общее решение последовательности Фибоначчи имеет вид ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ − − ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ + = n n n f 2 5 1 2 5 1 5 Что удивительно, это выражение при всех натуральных значениях n принимает целые значения. Случай равных корней характеристического многочлена. Если характеристическое уравнение имеет два равных корня, то общее решение имеет вид |