Всем привет. Сейчас разберу задачи шестой недели для курса комбинаторики. Первая задача. Там три пункта. Значит, надо найти формулу для последовательности yn, которая задана рекуррентными соотношениями. Во всех трёх пунктах полагается, что y0 = 0, y1 = 1. Вот давайте все их разберём. Пункт а. Там такое рекуррентное соотношение: yn+2 = 5yn+1 − 6yn. Ну, давайте найдём эту формулу. Для этого мы воспользуемся теоремой, которая была доказана на лекциях. Записываем сначала характеристическое уравнение. Оно записывается так: это будет λ² = 5λ − 6. Ну, или если перенести λ в правую сторону, получим такое квадратное уравнение действительно λ: λ² − 5λ + 6 = 0. Решая это уравнение, получаем, что корни его равны 2 и 3. По теореме, это означает, что последовательность yn имеет следующий вид: это какое-то число C1 * 2 в степени n + какое-то число C2 * 3 в степени n. 2 и 3 — это как раз корни характеристического уравнения. Чтобы найти C1 и C2, мы подставим значения n = 0 и n = 1 и из этих уравнений найдём C1 и C2. Давайте это сделаем. Значит, какое у нас уравнение получается? 0 = y0 = C1 * 2 в нулевой + C2 * 3 в нулевой, то есть это просто C1 + C2. Первое уравнение. Второе уравнение: 1 = y1 = C1 * 2 в первой степени + C2 * 3 в первой степени, то есть это = 2C1 + 3C2. Так, ну и решаем эту систему. Это система двух уравнений с двумя неизвестными. Ну, из первого уравнения видно, что C1 = −C2. Подставляя это во второе уравнение, получаем, что... Значит, если мы поставим вместо C1 −C2, получим, что это равно −2C2 + 3C2 = 1. То есть это равно, и это же равно C2, то есть C2 = 1. Таким образом, у нас C2 = 1, C1 = −1. Таким образом, наша последовательность yn = 3 в степени n − 2 в степени n. Вот ответ в пункте а. Давайте, значит, пункт б. Я перейду к той доске. Значит, в пункте б дана последовательность такая: yn+2 = 3yn+1 − 2yn. Ну, давайте здесь сделаем то же самое. Сначала запишем характеристическое уравнение. Значит, это будет λ² = 3λ − 2. Это то же самое, что λ² − 3λ + 2 = 0. Решая это уравнение, находим корни. Они там равны 1 и 2. Это означает, что yn имеет вид C1 * 1 в степени n + C2 * 2 в степени n. Снова подставляем значение 0 и 1. Получаем уравнение: 0 = y0 = C1 + C2 и 1 = y1 = C1 + 2C2. И решая эту систему, значит, снова получается, что C1 = −C2. Подставляем во второе, получаем, что C2 = 1, а C1 = −1. И ответ: yn = 2 в степени n − 1 в степени n. Итак, первая задача, пункт в. Сейчас я немножко напомню условия. Значит, нам нужно найти формулу для n-ного члена последовательности, создаваемой следующими соотношениями. Значит, у нас есть начальное соотношение y0 = 0, y1 = 1. И в пункте в) есть рекуррентные соотношения yn+2 = yn+1 + yn, ну то есть это числа Фибоначчи. Давайте мы найдём формулу для yn. Для этого мы сначала выпишем характеристическое уравнение. Оно будет иметь вид: λ² = λ + 1. Ну, найдём корни. Значит, перенесём всё в левую часть: λ² − λ − 1 = 0. Корни этого уравнения: λ1,2 вычисляется по формуле корней квадратного уравнения. Это будет 1 ± √ из дискриминанты, который здесь равен 1 + 1 x 4, то есть 5. То есть √5, и всё это пополам. Это означает, что yn записывается в следующем виде: yn = C1 * (1 + √5) пополам в n-нной степени + C2 * (1 − √5) пополам в n-нной степени. Для того чтобы найти C1 и C2, мы подставим начальные значения n, равные 0 и 1. Подставляем n = 0. Получаем, что 0 = y0. Ну и как в предыдущих задачах, это будет просто = C1 + C2, то есть C1 = −C2. Подставляем n = 1. Получаем, что 1 = y1 = C1 * (1 + √5) пополам + C2 * (1 − √5) пополам. Так, подставляем значение C1 = −C2. Давайте для удобства поставим здесь C2 = −C1. Получим, что это = C1, и всё это запишем в одной скобочке, что это будет (1 + √5) пополам − 1 − √5) пополам. Так, ну давайте посмотрим. Значит, 1/2 у нас сокращается, √5/2 + √5/2 будет просто √5. Значит, это всё = просто C1 * √5, то есть C1 = 1/√5. Ну, а C2 значит = −1/√5. Таким образом, формулу для yn можно записать в следующем виде: yn = 1/√5 * (1 +√5) пополам, в n-нной степени +, так, только не +, а −, − 1/√5 * (1 − √5) пополам всё это в n-нной степени. Всё, задача решена.