Главная » Дизайн ванной комнаты » Решить рекуррентное соотношение с начальными условиями. Производящие функции — туда и обратно. Open Library - открытая библиотека учебной информации

Решить рекуррентное соотношение с начальными условиями. Производящие функции — туда и обратно. Open Library - открытая библиотека учебной информации

Размер: px

Начинать показ со страницы:

Транскрипт

1 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Костромской государственный университет имени Н. А. Некрасова Т. Н. Матыцина ДИСКРЕТНАЯ МАТЕМАТИКА РЕШЕНИЕ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ Практикум Кострома 2010

2 ББК я73-5 М348 Печатается по решению редакционно-издательского совета КГУ им. Н. А. Некрасова Рецензент А. В. Чередникова, кандидат физико-математических наук, доцент М348 Матыцина Т. Н. Дискретная математика. Решение рекуррентных соотношений: практикум [Текст] / Т. Н. Матыцина. Кострома: КГУ им. Н. А. Некрасова, с. Практикум содержит индивидуальные задания для студентов и предназначен для обеспечения самостоятельной работы по освоению первой части курса «Дискретная математика». Для студентов 2 3 курсов физико-математического факультета, обучающихся по специальностям «Математика» с дополнительной специальностью «Информатика», «Информатика» с дополнительной специальностью «Математика». ББК я73-5 Т. Н. Матыцина, 2010 КГУ им. Н. А. Некрасова,

3 ОГЛАВЛЕНИЕ Введение Методические рекомендации по решению линейных рекуррентных соотношений Основные понятия и определения рекуррентных (возвратных) последовательностей Алгоритмы решения ЛОРС и ЛРС Примеры решения ЛОРС и ЛРС Задачи для самостоятельного решения Задачи для решения ЛОРС и ЛРС Ответы Заключение Библиографический список

4 ВВЕДЕНИЕ Первая часть курса «Дискретная математика», изучаемая студентами 2 3 курсов физико-математического факультета, обучающихся по специальностям «Информатика» с дополнительной специальностью «Математика» (IV семестр) и «Математика» с дополнительной специальностью «Информатика» (V семестр), предполагает решение рекуррентных соотношений. В настоящее издание включены задачи на вычисление однородных и неоднородных линейных рекуррентных соотношений. Поводом для написания практикума послужило то обстоятельство, что у студентов практически нет навыков решения задач по данному курсу. Одной из причин является отсутствие доступного учебника или сборника задач. Задачи из предлагаемого практикума помогут каждому из студентов (индивидуально) разобраться с основными методами и приемами решения задач. С целью более легкого освоения материала в начале пособия рассмотрены все типы задач, предлагаемых для самостоятельного решения. В конце помещен список рекомендуемой литературы, которая поможет глубже изучить данный предмет. Тема «Рекуррентные соотношения» близка к школьному курсу (арифметические и геометрические прогрессии, последовательность квадратов и кубов натуральных чисел, и т. п.), поэтому не требует от студентов предварительного изучения каких-либо других дисциплин. Основы теории рекуррентных соотношений (возвратных последовательностей) были разработаны и опубликованы в 20-х гг. XVIII в. французским математиком А. Муавром и одним из первых по времени членов Петербургской Академии наук швейцарским математиком Д. Бернулли. Развёрнутую теорию дал крупнейший математик XVIII в. 4

5 петербургский академик Л. Эйлер. Из более поздних работ следует выделить изложение теории возвратных последовательностей в курсах исчисления конечных разностей, читанных знаменитыми русскими математиками академиками П. Л. Чебышевым и А. А. Марковым. Рекуррентные соотношения (от латинского слова recurrere возвращаться) играют большую роль в дискретной математике, являясь по существу в некотором смысле дискретным аналогом дифференциальных уравнений. Кроме того, они позволяют сводить данную задачу от параметров к задаче от 1 параметров, потом к задаче от 2 параметров и т. д. Последовательно уменьшая число параметров, можно дойти до задачи, которую уже легко решить. Понятие рекуррентного соотношения (возвратной последовательности) является широким обобщением понятия арифметической или геометрической прогрессии. Как частные случаи оно охватывает также последовательности квадратов или кубов натуральных чисел, последовательности цифр десятичного разложения рационального числа (и вообще любые периодические последовательности), последовательности коэффициентов частного от деления двух многочленов, расположенных по возрастающим степеням х, и т. д. 5

6 1. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ 1.1. Основные понятия и определения рекуррентных (возвратных) последовательностей Будем записывать последовательности в виде a 1, a 2, a 3, a, (1) или, коротко, {a }. Если существует натуральное число k и числа α 1, α 2, α k (действительные или мнимые), такие, что, начиная с некоторого номера и для всех следующих номеров, a +k = α 1 a +k 1 + α 2 a +k α k a, (k 1), (2) то последовательность (1) называется рекуррентной (возвратной) последовательностью порядка k, а соотношение (2) рекуррентным (возвратным) уравнением порядка k. Таким образом, рекуррентная последовательность характеризуется тем, что каждый её член (начиная с некоторого из них) выражается через одно и то же количество k непосредственно предшествующих ему членов по формуле (2). Само название «рекуррентная» (а также возвратная) употребляется именно потому, что здесь для вычисления последующего члена возвращаются к предшествующим членам. Приведём несколько примеров рекуррентных последовательностей. Пример 1. Геометрическая прогрессия. Пусть имеем геометрическую прогрессию: a 1 = α, a 2 = α q, a 3 = α q 2, a = α q 1, ; (3) для неё уравнение (2) принимает вид: a +1 = q a. (4) 6

7 Здесь k = 1 и α 1 = q. Таким образом, геометрическая прогрессия является рекуррентной последовательностью первого порядка. Пример 2. Арифметическая прогрессия. В случае арифметической прогрессии a 1 = α, a 2 = α + d, a 3 = α + 2d, a = α + (1)d, имеем a +1 = a + d соотношение, не имеющее вида уравнения (2). Однако если мы рассмотрим два соотношения, написанные для двух соседних значений: a +2 = a +1 + d и a +1 = a + d, то получим из них путём почленного вычитания a +2 a +1 = a +1 a, или a +2 = 2a +1 a уравнение вида (2). Здесь k = 2, α 1 = 2, α 2 = 1. Следовательно, арифметическая прогрессия является рекуррентной последовательностью второго порядка. Пример 3. Рассмотрим старинную задачу Фибоначчи 1 о числе кроликов. В ней требуется определить число пар зрелых кроликов, образовавшихся от одной пары в течение года, если известно, что каждая зрелая пара кроликов ежемесячно рождает новую пару, причём новорождённые достигают полной зрелости в течение месяца. В этой задаче интересен отнюдь не результат, получить который совсем нетрудно, но последовательность, члены которой выражают общее число зрелых пар кроликов в начальный момент (a 1) через месяц (a 2), через два месяца (a 3) и, вообще, через месяцев (a +1). Очевидно, что a 1 = 1. Через месяц прибавится пара новорождённых, но число зрелых пар будет прежнее: a 2 = 1. Через два месяца крольчата достигнут зрелости и общее число зрелых пар будет равно двум: a 3 = 2. Пусть мы вычислили уже количество 1 Фибоначчи, или Леонардо Пизанский, итальянский средневековый математик (около 1200 г.) оставил после себя книгу «Об абаке», содержащую обширные арифметические и алгебраические сведения, заимствованные у народов Средней Азии и византийцев и творчески им переработанные и развитые. 7

8 зрелых пар через 1 месяцев a и через месяцев a +1. Так как к этому времени a ранее имевшихся зрелых пар дадут ещё a пар приплода, то через + 1 месяцев общее число зрелых пар будет: a +2 = a +1 + a. (6) Отсюда a 4 = a 3 + a 2 = 3, a 5 = a 4 + a 3 = 5, a 6 = a 5 + a 4 = 8, a 7 = a 6 + a 5 = 13,. Мы получили, таким образом, последовательность a 1 = 1, a 2 = 1, a 3 = 2, a 4 = 3, a 5 = 5, a 6 = 8, a 7 = 13, a 13 = 233, (7) в которой каждый последующий член равен сумме двух предыдущих. Последовательность эта называется последовательностью Фибоначчи, а члены её числами Фибоначчи. Уравнение (6) показывает, что последовательность Фибоначчи есть рекуррентная последовательность второго порядка. Пример 4. В качестве следующего примера рассмотрим последовательность квадратов натуральных чисел: a 1 = 1 2, a 2 = 2 2, a 3 = 3 2, a = 2,. (8) Здесь a +1 = (+ 1) 2 = и, следовательно, a +1 = a (9) Увеличивая на единицу, получим: a +2 = a (10) И, следовательно (вычитая почленно (9) из (10)), a +2 a +1 = a +1 a + 2, или a +2 = 2a +1 a + 2. (11) Увеличивая в равенстве (11) на единицу, будем иметь: a +3 = 2a +2 a ; (12) откуда (вычитая почленно (11) из (12)) a +3 a +2 = 2a +2 3a +1 + a, 8

9 или a +3 = 3a +2 3a +1 + a. (13) Мы получили рекуррентное уравнение третьего порядка. Следовательно, последовательность (8) есть рекуррентная последовательность третьего порядка. Пример 5. Рассмотрим последовательность кубов натуральных чисел: a 1 = 1 3, a 2 = 2 3, a 3 = 3 3, a = 3,. (14) Подобным же образом, как в примере 4, можно убедиться в том, что последовательность кубов натуральных чисел есть рекуррентная последовательность четвёртого порядка. Члены её удовлетворяют уравнению a +4 = 4a +3 6a a +1 a. (15) В случае простейших рекуррентных последовательностей, например арифметической и геометрической прогрессий, последовательности квадратов или кубов натуральных чисел, мы можем находить любой член последовательности, не прибегая к вычислению предшествующих членов. В случае же последовательности чисел Фибоначчи мы, на первый взгляд, не имеем возможности для этого и, чтобы вычислить тринадцатое число Фибоначчи a 13, находим предварительно, один за другим, все предшествующие члены (пользуясь уравнением a +2 = a +1 + a (6)): a 1 = 1, a 2 = 1, a 3 = 2, a 4 = 3, a 5 = 5, a 6 = 8, a 7 = 13, a 8 = 21, a 9 = 34, a 10 = 55, a 11 = 89, a 12 = 144, a 13 = 233. В ходе детального исследования структуры членов рекуррентной последовательности можно получить формулы, позволяющие вычислить в самом общем случае любой член рекуррентной последовательности, не прибегая к вычислению предшествующих членов. Другими словами, следующая задача состоит в том, чтобы отыскать формулу -го члена последовательности, зависящую только от номера. 9

10 Рекуррентное соотношение в общем случае может быть записано в виде a +k = F(, a +k 1, a +k 2, a), где F функция от k + 1 переменной, а число k называют порядком соотношения. Решением рекуррентного соотношения называется числовая последовательность b 1, b 2, b 3, b, для которой выполняется равенство: b +k = F(, b +k 1, b +k 2, b) при любом = 0, 1, 2,. Вообще говоря, произвольное рекуррентное соотношение имеет бесконечно много решений. Например, если рассмотреть рекуррентное соотношение второго порядка a +2 = a +1 + a, то ему, кроме последовательности Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34,..., характеризующейся тем, что здесь a 1 = a 2 = 1, удовлетворяет ещё бесконечное множество других последовательностей, получающихся при различном выборе значений a 1 и a 2. Так, например, при a 1 = 3 и a 2 = 1 получаем последовательность: 3, 1, 2, 1, 3, 4, 7, 11, 18, 29,. Чтобы однозначно определить решение рекуррентного соотношения, необходимо задать начальные условия (начальных условий должно быть ровно столько, каков порядок рекуррентного соотношения). Решить рекуррентное соотношение значит найти формулу -го члена последовательности. К сожалению, не существует общего метода решения произвольных рекуррентных соотношений. Исключением является класс так называемых линейных рекуррентных соотношений с постоянными коэффициентами. Рекуррентное соотношение вида a +k = α 1 a +k 1 + α 2 a +k α k a, где a i некоторые числа, i = 1, 2, k, называется линейным однородным рекуррентным соотношением (ЛОРС) с постоянными коэффициентами порядка k. 10

11 Рекуррентное соотношение вида a +k = α 1 a +k 1 + α 2 a +k α k a + f(), где a i некоторые числа, i = 1, 2, k, f() 0 функция от, называется линейным рекуррентным соотношением (ЛРС) с постоянными коэффициентами порядка k Алгоритмы решения ЛОРС и ЛРС Алгоритм решения ЛОРС. Имеем ЛОРС: a +k = α 1 a +k 1 + α 2 a +k α k a. 1 шаг. Каждому ЛОРС порядка k соответствует алгебраическое уравнение степени k с теми же коэффициентами, и оно называется характеристическим уравнением ЛОРС. Составляем характеристическое уравнение x k = α 1 x k 1 + α 2 x k α k x 0 и находим его корни x i, где i = 1, k. 2 шаг. Если x i корни кратности 1 (т. е. все различны между собой), то общее решение ЛОРС имеет вид: a = c 1 (x 1) + c 2 (x 2) + c 3 (x 3) + + c k (x k) = c i x i Если x i корни кратности r i, то общее решение ЛОРС имеет вид k a = i= 1 (c 1 2 ri 1 i1 + ci2 + ci cir) (например, если корень x кратности 2, то a = (c 1 + c 2) x). i x i k i= 1 3 шаг. Коэффициенты c i находятся с помощью начальных условий. 11

12 Алгоритм решения ЛРС. Имеем ЛРС: a +k = α 1 a +k 1 + α 2 a +k α k a + f(). Функцию f() можно представить в виде R m () λ, где R m () многочлен степени m от переменной. В самом деле, например: f() = 10 3= (10 3)1 = R 1 () 1, или f() = = (2 + 3) 3 = R 2 () 3. Перепишем ЛРС в виде a +k α 1 a +k 1 α 2 a +k 2 α k a = R m () λ. 1 шаг. Выписываем соответствующий ЛОРС: a +k α 1 a +k 1 α 2 a +k 2 α k a = 0 и находим его общее решение. Для этого составляем характеристическое уравнение x k α 1 x k 1 α 2 x k 2 α k x 0 = 0 и находим его корни x i, где i = 1, k. Пусть, например, x i различные корни, тогда общее решение соответствующего ЛОРС имеет вид: a = c 1 (x 1) + c 2 (x 2) + c 3 (x 3) + + c k (x k). 2 шаг. Находим a частное решение ЛРС: а) если λ не корень характеристического уравнения x k α 1 x k 1 α 2 x k 2 α k = 0, то a = Q m () λ, где Q m () многочлен степени m от переменной; б) если λ корень характеристического уравнения x k α 1 x k 1 α 2 x k 2 α k = 0 кратности r, то a = r Q m () λ, где Q m () многочлен степени m от переменной. Далее, подставляем a в исходное ЛРС и находим коэффициенты в многочлене Q m (). 12

13 3 шаг. Находим общее решение ЛРС, оно представляет собой сумму общего решения соответствующего ЛОРС a и частного решения ЛРС a, то есть a = a + a. Коэффициенты c i находятся с помощью начальных условий Примеры решения ЛОРС и ЛРС Пользуясь приведенным алгоритмом нахождения решения ЛОРС и ЛРС, разберём несколько задач. Задача 1. Найти решение линейного однородного рекуррентного соотношения второго порядка: a +2 = 6 a +1 8 a, a 0 = 3, a 1 = Составляем характеристическое уравнение x 2 = 6 x 8 x 0 и находим его корни. x 2 6x + 8 = 0; x 1 = 2, x 2 = 4 корни различные, следовательно, их кратность равна Находим общее решение ЛОРС: a = c 1 (x 1) + c 2 (x 2) = c c Так как заданы начальные условия, то коэффициенты c 1 и c 2 определяются однозначно. a 0 = c c = c 1 + c 2 = 3; a 1 = c c = 2c 1 + 4c 2 = 4. Получили систему: c1 + c2 = 3, 2c1 + 4c2 = 4. Решая её, найдём коэффициенты: c 1 = 8, c 2 = 5. Таким образом, решение ЛОРС имеет вид a = Задача 2. Найти решение линейного однородного рекуррентного соотношения: 13

14 a +2 = 6 a +1 9 a, a 0 = 5, a 1 = Составляем характеристическое уравнение x 2 = 6x 9 и находим его корни. x 2 6x + 9 = 0; (x 3) 2 = 0; x 1 = x 2 = 3 два корня, при этом x 1 и x 2 совпали, следовательно, кратность корня равна Находим общее решение ЛОРС: a = (c 1 + c 2) (x 1) = (c 1 + c 2) С помощью начальных условий определяем коэффициенты c 1 и c 2: a 0 = (c 1 + c 2 0) 3 0 = c 1 = 5; a 1 = (c 1 + c 2 1) 3 1 = (c 1 + c 2) 3 = 6. Получили систему c1 = 5, c1 + c2 = 2. Решая её, найдём коэффициенты c 1 = 5, c 2 = 3. Таким образом, решение ЛОРС имеет вид: a = (5 3) 3. Замечание. Как известно, корнями квадратного уравнения могут служить рациональные, иррациональные, комплексные числа и т. п. Метод решения линейных рекуррентных соотношений с такими корнями решается аналогично. Задача 3. Найти решение линейного однородного рекуррентного соотношения третьего порядка: a +3 = 3 a a +1 8 a, a 0 = 9, a 1 = 9, a 2 = Составляем характеристическое уравнение x 3 = 3 x x 8 и находим его корни. x 3 3x 2 6x + 8 = 0; (x 1)(x + 2)(x 4) = 0; x 1 = 1, x 2 = 2, x 3 = 4 корни различные, следовательно, их кратность равна Находим общее решение ЛОРС: a = c 1 (x 1) + c 2 (x 2) + c 3 (x 3) = c c 2 (2) + c

15 3. С помощью начальных условий, находим коэффициенты c 1, c 2 и c 3. a 0 = c c 2 (2) 0 + c = c 1 + c 2 + c 3 = 9; a 1 = c c 2 (2) 1 + c = c 1 2c 2 + 4c 3 = 9; a 2 = c c 2 (2) 2 + c = c 1 + 4c c 3 = 9. c1 + c2 + ñ3 = 9, Решая систему c1 2c2 + 4c3 = 9, получим c 1 = 7, c 2 = 4, c 3 = 2. Таким c1 + 4c2 + 16c3 = 9, образом, решение ЛОРС имеет вид: a = (2) 2 4. Задача 4. Найти решение линейного однородного рекуррентного соотношения третьего порядка: a +3 = a a +1 3 a, a 0 = 6, a 1 = 15, a 2 = Составляем характеристическое уравнение x 3 = x 2 + 5x 3 и находим его корни. x 3 + x 2 5x + 3 = 0; (x 1) 2 (x + 3) = 0; x 1 = x 2 = 1 корень кратности 2; x 3 = 3 корень кратности Находим общее решение ЛОРС: a = (c 1 + c 2) (x 1) + c 3 (x 3) = (c 1 + c 2) 1 + c 3 (3). 3. С помощью начальных условий находим коэффициенты c 1, c 2 и c 3. a 0 = (c 1 + c 2 0) c 3 (3) 0 = c 1 + c 3 = 6; a 1 = (c 1 + c 2 1) c 3 (3) 1 = c 1 + c 2 3c 3 = 15; a 2 = (c 1 + c 2 2) c 3 (3) 2 = c 1 + 2c 2 + 9c 3 = 8. c1 + ñ3 = 6, Решая систему c1 + c2 3c3 = 15, получим c 1 = 8, c 2 = 1 и c 3 = 2. Таким c1 + 2c2 + 9c3 = 8, образом, решение ЛОРС имеет вид: a = (8 +) 1 2 (3). 15

16 Задача 5. Найти решение линейного рекуррентного соотношения второго порядка: Перепишем ЛРС в виде a +2 = 18 a a + 128, a 0 = 5, a 1 = 2. a a a = () 1. Выписываем соответствующий ЛОРС: a a a = 0. Составляем характеристическое уравнение и находим его корни. x 2 18x + 81 = 0; (x 9) 2 = 0; x 1 = x 2 = 9 корни характеристического уравнения совпали, следовательно, их кратность равна 2. Тогда общее решение a = (c 1 + c 2) (x 1) = (c 1 + c 2) Находим a частное решение ЛРС. По условию f() = R m () λ = = = R 0 () λ, где R 0 () = 128 многочлен нулевой степени от переменной, а λ = 1 не корень характеристического уравнения соответствующего ЛОРС. Следовательно, a = Q m () λ = Q 0 () 1, где Q 0 () многочлен нулевой степени от переменной, в общем виде Q 0 () = с. Таким образом, a = с 1. Далее, подставляем a в исходное ЛРС () и находим коэффициент с в многочлене Q 0 (): с с с 1 = ; с 18с + 81с = 128; 64с = 128; с = 2. Следовательно, получили a = с 1 = 2 1 = 2. 16

17 3. Находим общее решение ЛРС, оно представляет собой сумму общего решения соответствующего ЛОРС a и частного решения ЛРС a, то есть a = a + a = (c 1 + c 2) Осталось с помощью начальных условий найти коэффициенты c 1, и c 2. a 0 = (c 1 + c 2 0) = c = 5; a 1 = (c 1 + c 2 1) = 9c 1 + 9c = 2; Решая систему c1 + 2 = 5, 9c1 + 9c2 + 2 = 2, получим c 1 = 3, c 2 = 3. Таким образом, решение ЛРС имеет вид: a = (3 3) Задача 6. Найти решение линейного рекуррентного соотношения: a +2 = 10 a a , a 0 = 7, a 1 = 50. Перепишем ЛРС в виде a a a = Выписываем соответствующий ЛОРС: a a a = 0; составляем характеристическое уравнение и находим его корни. x 2 10 x + 25 = 0; (x 5) 2 = 0; x 1 = x 2 = 5 корень кратности 2. Тогда общее решение ЛОРС имеет вид: a = (c 1 + c 2) (x 1) = (c 1 + c 2) Находим a частное решение ЛРС. По условию f() = R m () λ = 50 5 = R 0 () λ, где R 0 () = 50 многочлен нулевой степени от переменной, а λ = 5 совпадает с корнем x 1 кратности 2 характеристического уравнения соответствующего ЛОРС. Следовательно, a = r Q m () λ = = 2 Q 0 () 5, где Q 0 () = с многочлен нулевой степени от переменной. Таким образом, a = 2 с 5. Далее, подставляем a в исходное ЛРС и находим коэффициент с: 17

18 с (+ 2) с (+ 1) с 2 5 = 50 5 (разделим на 5 0); 25с (+ 2) 2 50с (+ 1) с 2 = 50; с () 2с () + с 2 = 2; с = 1. Следовательно, a = 2 с 5 = Выписываем общее решение ЛРС: a = a + a = (c 1 + c 2) С помощью начальных условий находим коэффициенты c 1, и c 2: a 0 = (c 1 + c 2 0) = c 1 = 7; a 1 = (c 1 + c 2 1) = 5c 1 + 5c = 50; Решая систему c1 = 7, c1 + c2 + 1 = 10, получим c 1 = 7, c 2 = 2. Таким образом, решение ЛРС имеет вид: a = (7 + 2) = () 5. Задача 7. Найти решение линейного рекуррентного соотношения: a +2 = 6 a +1 8 a , a 0 = 0, a 1 = 11. Перепишем ЛРС в виде a +2 6 a a = Выписываем соответствующий ЛОРС: a +2 6 a a = 0; составляем характеристическое уравнение и находим его корни. x 2 6x + 8 = 0; x 1 = 2, x 2 = 4 корни кратности равной 1. Тогда общее решение ЛОРС имеет вид a = c 1 (x 1) + c 2 (x 2) = c c Находим a частное решение ЛРС. По условию f() = R m () λ = = (3 + 2) 1 = R 1 () λ, где R 1 () = многочлен первой степени от переменной, а λ = 1 не корень характеристического уравнения соответствующего ЛОРС. Следовательно, a = Q m () λ = Q 1 () 1, где Q 1 () многочлен первой степени от переменной, в общем виде Q 1 () = = a + b. Таким образом, a = (a + b) 1. 18

19 a и b: Далее, подставляем a в исходное ЛРС и находим коэффициенты (a (+ 2) + b) (a (+ 1) + b) (a + b) 1 = 3 + 2; 25с (+ 2) 2 50с (+ 1) с 2 = 3 + 2; 3a + (3b 4a) = Таким образом, получили, что два многочлена равны, а тогда равны соответствующие коэффициенты: 3a = 3, a = 1, 3b 4a = 2 b = 2. Следовательно, a = (a + b) 1 = Выписываем общее решение ЛРС: a = a + a = c c (+ 2). С помощью начальных условий находим коэффициенты c 1, и c 2: a 0 = c c (0 + 2) = 0; a 1 = c c (1 + 2) = 11; Решая систему c1 + c2 = 2, 2c1 + 4c2 = 14, получим c 1 = 3, c 2 = 5. Таким образом, решение ЛРС имеет вид: a = Задача 8. Найти решение линейного рекуррентного соотношения: a +2 = 5 a +1 6 a + (10 4) 2, a 0 = 5, a 1 = 12. Перепишем ЛРС в виде a +2 5 a a = (10 4) Выписываем соответствующий ЛОРС: a +2 5 a a = 0; составляем характеристическое уравнение и находим его корни. x 2 5x + 6 = 0; x 1 = 3, x 2 = 2 корни различные кратности 1. Тогда общее решение ЛОРС имеет вид: a = c 1 (x 1) + c 2 (x 2) = c c

20 2. Находим a частное решение ЛРС. По условию имеем, что f() = = R m () λ = (10 4) 2 = R 1 () λ, где R 1 () = (10 4) многочлен первой степени от переменной, а λ = 2, то есть совпадает с корнем характеристического уравнения соответствующего ЛОРС. Следовательно, a = r Q m () λ = 1 Q 1 () 2, где Q 1 () многочлен первой степени от переменной, в общем виде Q 1 () = a + b. Таким образом, получаем a = = (a + b) 2. Далее, подставляем a в исходное соотношение и находим коэффициенты a и b. (+ 2)(a (+ 2) + b) (+ 1) (a (+ 1) + b) (a + b) 2 = = (10 4) 2. Разделим это уравнение на 2 0: 4(+ 2)(a (+ 2) + b) 10(+ 1) (a (+ 1) + b) + 6(a + b) = 10 4; 4a + (6a 2b) = Таким образом, получили, что два многочлена равны, а тогда равны соответствующие коэффициенты: 4a = 4, a = 1, 6a 2b = 10 b = 2. Следовательно, a = (a + b) 2 = (2) Выписываем общее решение ЛРС, то есть a = a + a = c c (2) 2. С помощью начальных условий находим коэффициенты c 1, и c 2. a 0 = c c (0 2) 2 0 = 5; a 1 = c c (1 2) 2 1 = 12. Решая систему c1 + c2 = 5, 3c1 + 2c2 = 14, получим c 1 = 4, c 2 = 1. Таким образом, решение ЛРС имеет вид: a = (2) 2 = () 2. 20

21 Задача 9. Найти решение линейного рекуррентного соотношения: a +2 = 8 a a , a 0 = 1, a 1 = 7. Перепишем ЛРС в виде a +2 8 a a = () Выписываем соответствующий ЛОРС: a +2 8 a a = 0; составляем характеристическое уравнение и находим его корни. x 2 8 x + 16 = 0; x 1 = x 2 = 4 корни совпали, следовательно, кратность корня равна 2. Тогда общее решение ЛОРС имеет вид: a = (c 1 + c 2) (x 1) = (c 1 + c 2) Находим a частное решение ЛРС. По условию f() = R m () λ = = () 1 = R 2 () λ, где R 2 () = многочлен второй степени от переменной, а λ = 1 не совпадает с корнем характеристического уравнения соответствующего ЛОРС. Следовательно, a = Q m () λ = Q 2 () 1, где Q 2 () многочлен второй степени от переменной, в общем виде Q 2 () = a 2 + b + c. Таким образом, a = = (a 2 + b + c) 1. Далее, подставляем a в исходное соотношение и находим коэффициенты a, b и c. (a (+ 2) 2 + b (+ 2)+ c) (a (+ 1) 2 + b (+ 1) + c) (a b + c) 1 = () 1 ; a(+ 2) 2 + b(+ 2)+ c 8a(+ 1) 2 8b(+ 1) 8c + 16a b + 16c = = ; 9a 2 12a + 9b 4a 6b + 9c = Таким образом, получили, что два многочлена равны, а тогда равны соответствующие коэффициенты: 9a = 9, 12a + 9b = 6, 4a 6b + 9c = 2 a = 1, b = 2, c = 2. 21

22 Следовательно, a = (a 2 + b + c) 1 = Выписываем общее решение ЛРС, то есть a = a + a = (c 1 + c 2) (). С помощью начальных условий, находим коэффициенты c 1, и c 2. a 0 = (c 1 + c 2 0) () = 1; a 1 = (c 1 + c 2 1) () = 7. Решая систему c1 + 2 = 1, 4c1 + 4c2 + 5 = 7, получим c 1 = 1, c 2 = 2. Таким образом, решение ЛРС имеет вид: a = (1 2)

23 2. ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ 2.1. Задачи для решения ЛОРС и ЛРС Линейные однородные рекуррентные соотношения второго порядка 1. a +2 = 9 a a, a 0 = 2, a 1 = a +2 = 3,5 a +1 2,5 a, a 0 = 3,5, a 1 = a +2 = 8 a a, a 0 = 4, a 1 = a +2 = 2 a a, a 0 = 3, a 1 = i. 5. a +2 = 10 a a, a 0 = 3, a 1 = a +2 = 6 a a, a 0 = 0, a 1 = 2i a +2 = 8 a a, a 0 = 2, a 1 = a +2 = 4 a a, a 0 = 7, a 1 = a +2 = a +1 + a, a 0 = 2, a 1 = a +2 = 8 a a, a 0 = 8, a 1 = a +2 = () a a, a 0 = 7, a 1 = a +2 = 5 a +1 4 a, a 0 = 0, a 1 = a +2 = 2 a +1 5 a, a 0 = 5, a 1 = 6i a +2 = 3 a a, a 0 = 7, a 1 = a +2 = 6 a +1 9 a, a 0 = 8, a 1 = a +2 = 6 a a, a 0 = 3, a 1 = 9 2i. 17. a +2 = a a, a 0 = 4, a 1 = a +2 = 14 a a, a 0 = 5, a 1 = a +2 = 8 a a, a 0 = 2, a 1 = a +2 = 7 a a, a 0 = 5, a 1 = a +2 = 2 a +1 + a, a 0 = 2, a 1 =

24 1 22. a +2 = a +1 a, a 0 = 4, a 1 = a +2 = 4 a +1 a, a 0 = 12, a 1 = a +2 = a a, a 0 = 2, a 1 = a +2 = 2 a a, a 0 = 8, a 1 = a +2 = 6 a +1 9 a, a 0 = 12, a 1 = a +2 = 4 a +1 5 a, a 0 = 5, a 1 = 10 i a +2 = 3 a +1 a, a 0 = 8, a 1 = a +2 = 14 a a, a 0 = 5, a 1 = a +2 = 4 a a, a 0 = 2, a 1 = a +2 = 4 a +1 5 a, a 0 = 3, a 1 = 6 7i. 32. a +2 = a a, a 0 = 5, a 1 = a +2 = 16 a a, a 0 = 7, a 1 = a +2 = 5 a +1 6 a, a 0 = 2, a 1 = a +2 = 10 a a, a 0 = 2, a 1 = 10 4i a +2 = 6 a +1 5 a, a 0 = 11, a 1 = a +2 = 2 a a, a 0 = 11, a 1 = a +2 = 6 a a ; a 0 = 3, a 1 = 0. Линейные однородные рекуррентные соотношения третьего порядка 39. a +3 = 7 a a a, a 0 = 1, a 1 = 3, a 2 = a +3 = 4 a +2 a +1 6 a, a 0 = 4, a 1 = 5, a 2 = a +3 = 6 a a a, a 0 = 5, a 1 = 8, a 2 = a +3 = 8 a a a, a 0 = 4, a 1 = 31, a 2 = a +3 = 5 a +2 3 a +1 9 a, a 0 = 1, a 1 = 3, a 2 = a +3 = 15 a a a, a 0 = 8, a 1 = 40, a 2 =

25 45. a +3 = 27 a a, a 0 = 6, a 1 = 3, a 2 = a +3 = 6 a a a, a 0 = 15, a 1 = 32, a 2 = a +3 = 15 a a a, a 0 = 1, a 1 = 20, a 2 = a +3 = 9 a a a, a 0 = 0, a 1 = 4, a 2 = a +3 = 2 a a +1 6 a, a 0 = 4, a 1 = 5, a 2 = a +3 = 4 a +2 5 a a, a 0 = 2, a 1 = 6, a 2 = a +3 = 6 a +2 5 a a, a 0 = 4, a 1 = 2, a 2 = a +3 = 3 a a a, a 0 = 2, a 1 = 17, a 2 = a +3 = 9 a a a, a 0 = 1, a 1 = 3, a 2 = a +3 = 6 a a +1 6 a, a 0 = 13, a 1 = 31, a 2 = a +3 = 5 a +2 3 a +1 9 a, a 0 = 3, a 1 = 14, a 2 = a +3 = a a +1 4 a, a 0 = 2, a 1 = 1, a 2 = a +3 = 3 a a a, a 0 = 2, a 1 = 3, a 2 = a +3 = 12 a a a, a 0 = 2, a 1 = 16, a 2 = a +3 = 4 a a a, a 0 = 0,2, a 1 = 6, a 2 = a +3 = 8 a a a, a 0 = 3, a 1 = 13, a 2 = a +3 = 4 a a a, a 0 = 3, a 1 = 29, a 2 = a +3 = 5 a +2 7 a a, a 0 = 11, a 1 = 34, a 2 = a +3 = 11 a a a, a 0 = 27, a 1 = 17, a 2 = a +3 = 12 a a a, a 0 = 1, a 1 = 37, a 2 = a +3 = 3 a a a, a 0 = 11, a 1 = 23, a 2 = a +3 = 7 a a a, a 0 = 3, a 1 = 6, a 2 = a +3 = 4 a a a, a 0 = 4, a 1 = 1, a 2 = 4.; 68. a +3 = 7 a a a, a 0 = 1, a 1 = 0, a 2 = a +3 = 5 a a a, a 0 = 6, a 1 = 0, a 2 = a +3 = 5 a +2 3 a a, a 0 = 10, a 1 = 1, a 2 = a +3 = 3 a +2 3 a +1 + a, a 0 = 2, a 1 = 4, a 2 = a +3 = 3 a a a, a 0 = 6, a 1 = 5, a 2 =

26 73. a +3 = 10 a a a, a 0 = 0, a 1 = 1, a 2 = a +3 = 8 a a a, a 0 = 8, a 1 = 23, a 2 = a +3 = 5 a +2 8 a +1 4 a, a 0 = 11, a 1 = 15, a 2 = a +3 = a a a, a 0 = 6, a 1 = 5, a 2 = a +3 = 10 a a a, a 0 = 1, a 1 = 2, a 2 = a +3 = a a a, a 0 = 1, a 1 = 14, a 2 = a +3 = 2 a +2 + a a, a 0 = 10, a 1 = 1, a 2 = a +3 = 5 a +2 8 a a, a 0 = 9, a 1 = 9, a 2 = a +3 = 8i a a +1 10i a, a 0 = 8, a 1 = 14i, a 2 = 38. Линейные рекуррентные соотношения первого порядка 82. a +1 = 4 a + 6, a 0 = a +1 = a + + 1, a 0 = a +1 = 5 a , a 0 = a +1 = 3 a + 5 2, a 0 = a +1 = 3 a + (4) 5 1, a 0 = a +1 = 4 a + 8 4, a 0 = a +1 = 3 a , a 0 = 14. Линейные рекуррентные соотношения второго порядка 89. a +2 = 7 a a + 10, a 0 = 4, a 1 = a +2 = 10 a a + 32, a 0 = 1, a 1 = a +2 = 6 a +1 9 a 2 3, a 0 = 0, a 1 = a +2 = 7 a a , a 0 = 3, a 1 = a +2 = 9 a a + (18 20) 2, a 0 = 6, a 1 = a +2 = 8 a +1 7 a , a 0 = 9, a 1 = a +2 = 4 a +1 9 a , a 0 = 15, a 1 = 27 i a +2 = 12 a a , a 0 = 13, a 1 = 6. 26

А А КИРСАНОВ КОМПЛЕКСНЫЕ ЧИСЛА ПСКОВ ББК 57 К45 Печатается по решению кафедры алгебры и геометрии, и редакционно-издательского совета ПГПИ им СМ Кирова Рецензент: Медведева ИН, кандидат физ мат наук, доцент

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Ухтинский государственный технический университет (УГТУ) ПРЕДЕЛ ФУНКЦИИ Методические

ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ Общие понятия Дифференциальные уравнения имеют многочисленные и самые разнообразные приложения в механике физике астрономии технике и в других разделах высшей математики (например

Министерство образования и науки Российской Федерации Московский физико-технический институт (государственный университет) Заочная физико-техническая школа МАТЕМАТИКА Тождественные преобразования. Решение

Министерство сельского хозяйства Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Пермская государственная сельскохозяйственная академия имени

Министерство образования Российской Федерации Российский государственный университет нефти и газа имени ИМ Губкина ВИ Иванов Методические указания к изучению темы «ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ» (для студентов

СИСТЕМЫ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ С ПОСТОЯННЫМИ КОЭФФИЦИЕНТАМИ Приведение к одному уравнению -го порядка С практической точки зрения очень важны линейные системы с постоянными коэффициентами

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ Интегрирование рациональных дробей Рациональной дробью называется дробь вида P Q, где P и Q многочлены Рациональная дробь называется правильной, если степень многочлена P ниже степени

03 Математика в высшем образовании УДК 54; 5799 СОДЕРЖАНИЕ И ТЕХНОЛОГИИ МАТЕМАТИЧЕСКОГО ОБРАЗОВАНИЯ В ВУЗЕ НЕКОТОРЫЕ МЕТОДЫ СУММИРОВАНИЯ ЧИСЛОВЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ А В Ласунский Новгородский государственный

ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ ПЕР- ВОГО ПОРЯДКА.. Основные понятия Дифференциальным уравнением называется уравнение, в которое неизвестная функция входит под знаком производной или дифференциала.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего образования «ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНО- ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Национальный исследовательский Нижегородский государственный университет им НИ Лобачевского НП Семерикова АА Дубков АА Харчева РЯДЫ АНАЛИТИЧЕСКИХ ФУНКЦИЙ

А. И. Козко В. Г. Чирский Задачи с параметром и другие сложные задачи Москва Издательство МЦНМО 2007 УДК 512 ББК 22.141 К59 К59 Козко А. И., Чирский В. Г. Задачи с параметром и другие сложные задачи. М.:

ЛЕКЦИЯ N Дифференциальные уравнения высших порядков, методы решения Задача Коши Линейные дифференциальные уравнения высших порядков Однородные линейные уравнения Дифференциальные уравнения высших порядков,

КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ ИМ. Н.И.ЛОБАЧЕВСКОГО Кафедра теории и технологий преподавания математики и информатики Фалилеева М.В. Первые шаги в решении уравнений и

Вестник КГУ им НА Некрасова 6 Скибицкий ЭГ Шкабура ОВ Стиль мышления как стратегия решения задач с использованием компьютера // Информатика и образование С 7 Яковлева НО Теоретико-методологические основы

УДК 373:512 ББК 22.14я721 М52 М52 Мерзляк, А.Г. Математика: Новый полный справочник для подготовки к ОГЭ / А.Г. Мерзляк, В.Б. Полонский, М.С. Якир. Москва: АСТ, 2017. 447, с.: ил. ISBN 978-5-17-096816-9

Образовательной программе на 2016-2017 учебный год (7-11 классы), утвержденной приказом МБОУ «Средняя общеобразовательная школа 21» г. Калуги 145/01-08 от 26.08.2016 РАБОЧАЯ ПРОГРАММА Предмета АЛГЕБРА

Тема 14 «Алгебраические уравнения и системы нелинейных уравнений» Многочленом степени n называется многочлен вида P n () a 0 n + a 1 n-1 + + a n-1 + a n, где a 0, a 1, a n-1, a n заданные числа, a 0,

Лекция ИНТЕГРИРОВАНИЕ РАЦИОНАЛЬНЫХ ДРОБЕЙ Рациональные дроби Интегрирование простейших рациональных дробей Разложение рациональной дроби на простейшие дроби Интегрирование рациональных дробей Рациональные

10 класс, базовый уровень Задание 1 Вариант 0 (демонстрационный, с решениями) Заочная математическая школа 009/010 учебный год 1 Представьте выражение в виде многочлена стандартного вида и найдите его

Тема: Общая теория систем линейных уравнений А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для

Муниципальное казенное общеобразовательное учреждение средняя общеобразовательная школа 3 города Пудожа Рассмотрено на заседании МО математики и информатики Протокол 1 от 29.08.2016 Руководитель МО Купцова

57 Рассмотрим интегрирование простейшей рациональной дроби четвертого типа (M N) d () p q p Сделаем замену переменной, положив d. где a p q. Тогда Интеграл M N d p p p q q a, M p N Mp q d M (p q) p

Тема 1-8: Комплексные числа А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для механиков (1 семестр)

Лекции -6 Глава Обыкновенные дифференциальные уравнения Основные понятия Различные задачи техники естествознания экономики приводят к решению уравнений в которых неизвестной является функция одной или

Занятие. Степень с произвольным действительным показателем, её свойства. Степенная функция, её свойства, графики.. Вспомнить свойства степени с рациональным показателем. a a a a a для натурального раз

Муниципальное бюджетное общеобразовательное учреждение средняя общеобразовательная школа 4 г. Балтийска Рабочая программа учебного предмета «Алгебра» 8 класс, базовый уровень Балтийск 2017 год 1 1. Пояснительная

ЭЛЕМЕНТЫ ОПЕРАЦИОННОГО ИСЧИСЛЕНИЯ ИЗДАТЕЛЬСТВО ТГТУ МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ГОУ ВПО «Тамбовский государственный технический университет» ЭЛЕМЕНТЫ ОПЕРАЦИОННОГО ИСЧИСЛЕНИЯ

Рассмотрим первый способ решения СЛУ по правилу Крамера для системы трех уравнений с тремя неизвестными: Ответ рассчитывается по формулам Крамера: D, D1, D2, D3 это определители Определителем третьего

Алгебраические многочлены. 1 Алгебраические многочлены степени n над полем K Определение 1.1 Многочленом степени n, n N {0}, от переменной z над числовым полем K называется выражение вида: fz = a n z n

Модуль Тема Функциональные последовательности и ряды Свойства равномерной сходимости последовательностей и рядов Степенные ряды Лекция Определения функциональных последовательностей и рядов Равномерно

ГАОУ ВПО ДАГЕСТАНСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ НАРОДНОГО ХОЗЯЙСТВА Бабичева ТА Кафедра высшей математики УЧЕБНОЕ ПОСОБИЕ ПО ДИСЦИПЛИНЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ Махачкала УДК 5(75) ББК я 7 Учебное пособие

Теоремы «пифагоровых троек» Мурсеев Михаил Петрович Существует различные методы определения вариантов «пифагоровых треугольников» Иногда их называют «пифагоровы тройки» или «египетские треугольники» К

1. Требования к уровню подготовки учащихся. Учащийся, заканчивающий 9 класс, должен уметь: выполнять арифметические действия, сочетая устные и письменные приёмы; находить значения корня натуральной степени,

Федеральное агентство по образованию Томский государственный университет систем управления и радиоэлектроники Кафедра высшей математики (ВМ) Приходовский М.А. ЛИНЕЙНЫЕ ОПЕРАТОРЫ И КВАДРАТИЧНЫЕ ФОРМЫ Практическое

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СПЕЦИАЛИЗИРОВАННЫЙ УЧЕБНО-НАУЧНЫЙ ЦЕНТР Математика 9 класс СУММИРОВАНИЕ КОНЕЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ Новосибирск

Министерство образования и науки Российской Федерации ФГБОУ ВО «Тверской государственный университет» УТВЕРЖДАЮ Руководитель ООП Цветков ВП 2015г Рабочая программа дисциплины (с аннотацией) Теория чисел

ПРОИЗВОДНАЯ, ЕЕ ГЕОМЕТРИЧЕСКИЙ И ФИЗИЧЕСКИЙ СМЫСЛ Приращением функции = f() называется разность f f, где - приращение аргумента Из рис видно, что g () Рис Производной функции = f() в точке называется конечный

Лекция 2. Свойства биномиальных коэффициентов. Подсчет сумм и метод производящих функций (конечный случай). Полиномиальные коэффициенты. Оценки биномиальных и полиномиальных коэффициентов. Оценки сумм

1. Пояснительная записка. Рабочая программа по предмету «Алгебра» для глухих обучающихся 8, 9, 10, 11 классов, разработана на основе программы общеобразовательных учреждений «Алгебра» 7-9 классы / авторы

ББК 74.262.21 Б94 Б94 Буцко Е.В. Алгебра: 7 класс: методическое пособие / Е.В. Буцко, А.Г. Мерзляк, В.Б. Полонский и др. М. : Вентана-Граф, 2017. 104 с. : ил. ISBN 978-5-360-08673-4 Пособие содержит

Аннотация к рабочей программе по алгебре Класс: 7 Уровень изучения учебного материала: базовый УМК, учебник Рабочая программа по алгебре для 7 класса составлена на основе программы «Алгебра» (Ю.Н. Макарычев,

I вариант 8В класс, 4 октября 007 1 Вставьте пропущенные слова: Определение 1 Арифметическим квадратным корнем из число, которого равен a из числа a (a 0) обозначается так: выражением Действие нахождения

Министерство образования и науки Российской Федерации Федеральное агентство по образованию Пензенский государственный университет Руденко АК, Руденко МН, Семерич ЮС СБОРНИК ЗАДАЧ С РЕШЕНИЯМИ ДЛЯ ПОДГОТОВКИ

ББК.4я7т+.4я7.6 М5 Учебник включён в федеральный перечень Мерзляк А.Г. М5 Алгебра: 9 класс: учебник для учащихся общеобразовательных организаций / А.Г. Мерзляк, В.М. Поляков. М. : Вентана-Граф, 07. 368

Математический анализ Раздел: дифференциальные уравнения Тема: Линейные однородные системы ДУ с постоянными коэффициентами Лектор Пахомова ЕГ 0 г 4 Системы линейных однородных дифференциальных уравнений

Í. Â. Áîãîìîëîâ ÌÀÒÅÌÀÒÈÊÀ ÇÀÄÀ È Ñ ÐÅØÅÍÈßÌÈ àñòü 1 УЧЕБНОЕ ПОСОБИЕ ДЛЯ СПО 2-е издание, исправленное и дополненное Ðåêîìåíäîâàíî Ó åáíî-ìåòîäè åñêèì îòäåëîì ñðåäíåãî ïðîôåññèîíàëüíîãî îáðàçîâàíèÿ â êà

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет прикладной математики и кибернетики Кафедра теории вероятностей и математической статистики ПРЕДЕЛЫ Методическое

Раздел 2 Теория пределов Тема Числовые последовательности Определение числовой последовательности 2 Ограниченные и неограниченные последовательности 3 Монотонные последовательности 4 Бесконечно малые и

ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени Н.Э. Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» À.Í. Êàíàòíèêîâ,

Иррациональные уравнения и неравенства Оглавление Иррациональные уравнения Метод возведения обеих частей уравнения в одну и ту же степень Задание Задание Задание Замена иррационального уравнения смешанной

Об одном обобщении чисел Стирлинга Устинов А. В. Моему учителю, Н. М. Коробову, к его 85 летию В работе вводятся обобщенные числа Стирлинга. Для них доказываются свойства, аналогичные свойствам обычных

А. Н. РУРУКИН ПОУРОЧНЫЕ РАЗРАБОТКИ ПО АЛГЕБРЕ к учебнику Ю.Н. Макарычева и др. (М.: Просвещение) НОВОЕ ИЗДАНИЕ 8 класс МОСКВА «ВАКО» 015 УДК 7:167.1:51 ББК 74.6.1 Р87 Р87 Рурукин А.Н. Поурочные разработки

Математический анализ Раздел: Неопределенный интеграл Тема: Интегрирование рациональных дробей Лектор Пахомова Е.Г. 0 г. 5. Интегрирование рациональных дробей ОПРЕДЕЛЕНИЕ. Рациональной дробью называется

Пояснительная записка Рабочая программа учебного предмета «Алгебра. 8-9 класс» составлена на основе: 1. Федерального компонента государственного стандарта основного общего и среднего (полного) общего образования

Лекция Дифференциальные уравнения -го порядка (ДУ-) Общий вид дифференциального уравнения порядка n запишется: (n) F, = 0 () Уравнение -го порядка (n =) примет вид F(,) = 0 Подобные уравнения

Тема 1-7: Определители А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для механиков (1 семестр) Перестановки

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К РАСЧЕТНЫМ ЗАДАНИЯМ ПО КУРСУ ВЫСШЕЙ МАТЕМАТИКИ «ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ РЯДЫ КРАТНЫЕ ИНТЕГРАЛЫ» ЧАСТЬ III ТЕМА ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ ОГЛАВЛЕНИЕ

Федеральное агентство по образованию Архангельский государственный технический университет строительный факультет РЯДЫ Методические указания к выполнению задания для самостоятельной работы Архангельск

Муниципальное бюджетное общеобразовательное учреждение «Лицей им. академика Б.Н. Петрова» города Смоленска «СОГЛАСОВАНО» Заместитель директора Казанцева Т.В. «29» «08» 206 г. «ПРИНЯТО» педагогическим советом

9., 9. класс Модуль 5 «Последовательности. Степени и корни» В тесте проверяются теоретическая и практическая части. Последовательности Числовые последовательности. Способы задания числовых последовательностей.

Транскрипт

1 РЕШЕНИЕ РЕКУРРЕНТНЫХ УРАВНЕНИЙ Обозначим через значение некоторого выражения при подстановке в него целого числа Тогда зависимость члена последовательности от членов последовательности F F со значениями аргумента меньшими называется рекуррентным уравнением Примером может служить уравнение вида: F Рекуррентное уравнение имеет порядок если оно позволяет выразить член последовательности F через члены F F Таким образом уравнение имеет порядок а уравнение F 3 6 имеет порядок 3 Если задано рекуррентное уравнение -го порядка то ему удовлетворяет бесконечно много последовательностей Но если первые элементов заданы то все остальные определяются однозначно А именно элемент выражается через элемент F через элементы F и тд Алгоритм решения рекуррентного уравнения приведен на Рис Отметим что уравнение описывает так называемую последовательность чисел Фибоначчи: 3 F 4 3 F 5 5 F F 8 Фактически алгоритм решения сводится к тому что на каждом шаге пользуясь начальными членами и заданным уравнением мы вычисляем очередной член последовательности Действуя таким образом мы рано или поздно получим любой член последовательности Однако при этом нам придется вычислять и все предыдущие члены Во многих случаях удобнее иметь явную формулу для -го члена последовательности Будем говорить что некоторая последовательность является решением рекуррентного уравнения если при подстановке ее в уравнение последнее обращается в тождество Например последовательность 4 8 является одним из решений рекуррентного уравнения 3 Действительно общий член этой последовательности имеет вид Но при любом имеет место тождество Значит 3 Таким образом является решением рекуррентного уравнения Решение рекуррентного уравнения называется общим если оно зависит от произвольных постоянных C C и путем подбора этих постоянных можно получить любое решение данного уравнения Например для уравнения 5 6 общим решением будет F C C 3 3 Легко проверить что последовательность 3 обращает в тождество Поэтому достаточно показать что любое решение можно представить в виде 3 Но любое

2 решение однозначно определяется значениями и Поэтому надо показать что для любых чисел и найдутся такие и C что F C C 3C C 3 C Определитель системы равен При любых и система имеет решение Поэтому 3 действительно является решением F; F; I: FFF; FF; FF; F Рис Алгоритм формирования последовательности чисел Фибоначчи

3 ЛИНЕЙНЫЕ РЕКУРРЕНТНЫЕ УРАВНЕНИЯ Для решения произвольных рекуррентных уравнений общих правил не существует Однако есть весьма часто встречающийся класс уравнений решаемый единообразным методом Это рекуррентные уравнения вида f 4 где - некоторые числа постоянные коэффициенты а f - некоторая функция от Такие уравнения называются линейными потому что элементы последовательности F связаны линейной зависимостью Если при этом функция f то уравнения такого вида называются однородными или однородными уравнениями с постоянными коэффициентами В противном случае уравнения называются неоднородными ЛИНЕЙНЫЕ ОДНОРОДНЫЕ РЕКУРРЕНТНЫЕ УРАВНЕНИЯ Линейные однородные рекуррентные уравнения с постоянными коэффициентами имеют вид F 5 где - некоторые числа Очевидно что последовательность всегда будет решением любого однородного уравнения Такое решение называется тривиальным решением Сначала рассмотрим как решаются такие уравнения при то есть изучим уравнения вида F 6 Решение этих уравнений основывается на следующих двух утверждениях: Если F и F являются решениями рекуррентного уравнения 6 то при любых числах A и B последовательность F AF BF также является решением этого уравнения Действительно по условию F F F F Умножим эти равенства на тождества В результате получим: A и F F B соответственно и сложим полученные [ AF BF ] [ AF BF ] AF BF А это означает что F AF BF является решением уравнения 6 Если число является корнем уравнения

4 то последовательность является решением рекуррентного уравнения F Докажем это утверждение Пусть то и Подставляя эти значения в 6 получаем равенство или Оно справедливо так как по условию При имеем тривиальное решение любая последовательность вида где Заметим что наряду с последовательностью { } также является решением уравнения 6 Для доказательства этого факта достаточно использовать утверждение положив в нем A B Из утверждений и вытекает следующее правило решения линейных однородных рекуррентных уравнений второго порядка Пусть дано рекуррентное уравнение 6 F Составим квадратное уравнение 7 которое называется характеристическим уравнением данного рекуррентного уравнения Если это уравнение имеет два различных корня и то общее решение уравнения 6 имеет вид C C Докажем это утверждение Заметим сначала что согласно утверждению последовательности и являются решениями данного рекуррентного F F уравнения А тогда по утверждению и C C является его решением Надо только показать что любое решение уравнения 6 можно записать в этом виде Но любое решение уравнения второго порядка определяется значениями и Поэтому достаточно показать что система уравнений C C C C имеет решение при любых и Очевидно что этими решениями являются При C F C система всегда имеет решение Рассмотрим пример Как уже было сказано последовательность чисел Фибоначчи 3583 можно получить с помощью рекуррентного уравнения F 8 Для него характеристическое уравнение имеет вид Корнями этого квадратного уравнения являются числа

5 5 5 и Поэтому общее решение уравнения Фибоначчи имеет вид 5 5 C C 9 Начальными условиями являются значения F F В соответствии с этими начальными условиями получаем для и C систему уравнений C C C 5 C C Решая эту систему уравнений находим что C C и поэтому F 5 Таким образом это выражение при всех натуральных значениях принимает целые значения СЛУЧАЙ РАВНЫХ КОРНЕЙ ХАРАКТЕРИСТИЧЕСКОГО УРАВНЕНИЯ Рассмотрим случай когда корни характеристического уравнения совпадают: В этом случае выражение C C уже не будет являться общим решением Ведь из-за того что это решение можно записать в виде C C C В результате остается только одна константа C и выбрать ее так чтобы уравнение удовлетворяло двум начальным условиям и вообще говоря невозможно Следовательно необходимо найти какое-нибудь другое решение отличное от Таким решением является В самом деле если квадратное F уравнение имеет два совпадающих корня то по теореме Виета а Поэтому уравнение записывается следующим образом: А тогда рекуррентное уравнение имеет вид Проверим что F тождество F F действительно является его решением Подставляя значения F в уравнение получим очевидное Значит - это решение нашего рекуррентного уравнения Таким образом нам известно уже два решения данного рекуррентного уравнения: и Тогда общее решение можно записать следующим образом: F F C C C C Теперь коэффициенты Cи C можно подобрать так чтобы выполнялись любые два начальные условия для F

6 C C C C Линейные рекуррентные уравнения порядок которых больше двух решаются таким же способом Пусть уравнение имеет вид F Составим характеристическое уравнение Если все корни этого алгебраического уравнения -й степени различны то общее решение уравнения имеет вид F C C C Если же например то этому корню соответствуют решения F F F3 F рекуррентного уравнения В общем решении этому корню соответствует часть C C C Составляя такие выражения для всех корней и складывая их получаем общее решение уравнения s P где - кратность корня s - число различных корней P - полином степени относительно Пример Рассмотрим уравнение F 4 Составим характеристическое уравнение Общее решение рекуррентного уравнения имеет вид C C C C Составляем систему уравнений для нахождения и C: C C C C 4 Решая систему получаем что C и C Таким образом решение рекуррентного уравнения имеет вид

7 ПОИСК КОРНЕЙ МНОГОЧЛЕНА При отыскании корней характеристического уравнения довольно часто приходится решать уравнения степени больше Для решения этой задачи можно использовать метод подбора те брать наугад число и проверять является ли оно корнем данного многочлена При этом можно довольно быстро натолкнуться на корень а можно и никогда его не найти Ведь проверить все числа невозможно так как их бесконечно много Другое дело если бы нам удалось сузить область поиска например знать что искомые корни находятся например среди тридцати указанных чисел А для тридцати чисел можно сделать проверку А в связи с этим важным представляется утверждение Теорема Если несократимая дробь / целые числа является корнем многочлена F x с целыми коэффициентами то старший коэффициент этого многочлена делится на а свободный член на В самом деле если x x x x где - целые числа и / является его корнем то F / те / / / Умножим обе части равенства на получим Отсюда следует что Очевидно что целое число делится на Но / - несократимая дробь те числа и взаимно просты а тогда как известно из теории делимости целых чисел числа и тоже взаимно просты Итак делится на и взаимно просто с значит делится на Аналогично доказывается что делится на Доказанная теорема позволяет значительно сузить область поиска рациональных корней многочлена с целыми коэффициентами Продемонстрируем это на конкретном примере Найдем рациональные корни многочлена 4 3 F x 6x 3x 4x 8x 8 Согласно доказанной теореме рациональные корни этого многочлена находятся среди несократимых дробей вида / где - делитель свободного члена 8 а - делитель старшего коэффициента 6 4 При этом если дробь отрицательная то знак - будем относить к ее числителю Например Значит можно сказать что делитель числа 8 а - положительный делитель числа 6 Так как делители числа 8 это ± 48 а положительными делителями числа 6 будут 36 то рациональные корни рассматриваемого многочлена находятся среди чисел ± / / 3/ 6 / 344 / 388/ 3 Напомним что мы выписали только несократимые дроби Таким образом мы имеем двадцать чисел-«кандидатов» в корни Осталось только проверить каждое из них и отобрать те которые действительно являются корнями Но опять-таки придется сделать довольно много проверок Следующая теорема упрощает эту работу

8 Теорема Если несократимая дробь / является корнем многочлена F x с целыми коэффициентами то F делится на для любого целого числа при условии что Для доказательства этой теоремы разделим F x на x с остатком Получим F x x s x Так как x - многочлен с целыми коэффициентами то таким же является и s x а - целое число Пусть s x b x b x b x b Тогда x x b x b x b x b Положим в этом равенстве x / Учитывая что F / получаем / b b b b Умножим обе части последнего равенства на: b b b b Отсюда следует что целое число делится на Но так как и взаимно просты то и тоже взаимно просты а значит F делится на Теорема доказана Вернемся теперь к нашему примеру и воспользовавшись данной теоремой еще больше сузим круг поиска рациональных корней Применим теорему для значений и те если несократимая дробь является корнем многочлена x то делится на а F делится на Очевидно что в нашем случае F 5 а 5 Заметим что заодно мы исключили из рассмотрения единицу Итак рациональные корни нашего многочлена следует искать среди чисел / / 3 / 6 / / 3 8 8/3 Рассмотрим / / Тогда и F 5 делится на это число Далее 3 и 5 также делится на 3 Значит дробь / остается в числе кандидатов в корни Пусть теперь / / В этом случае 3 и F 5 не делится на -3 Значит дробь / не может быть корнем данного многочлена Выполнив проверку для каждой из выписанных выше дробей получим что искомые корни находятся среди чисел / / 3 4 Таким образом с помощью довольно простого приема удалось значительно сузить область поиска рациональных корней рассматриваемого многочлена Проверив 4 3 оставшиеся кандидаты убедимся что многочлен x 6x 3x 4x 8x 8 имеет два рациональных корня / и / 3 Описанный выше метод позволяет находить лишь рациональные корни многочлена с целыми коэффициентами Между тем многочлен может иметь и иррациональные корни Так например рассмотренный в примере многочлен имеет еще два корня: ± 5 это корни многочлена x x 4 Заметим что при испытании кандидатов в корни с помощью последней теоремы обычно рассматривают случай ± Другими словами если / - кандидат в корни то проверяют делятся ли и F на и соответственно Но может случиться так что например те единица - корень а тогда делится на любое число и наша проверка теряет смысл В этом случае следует разделить x на x те получить x x s x и производить испытания для многочлена sx При этом не следует забывать что один корень x корень x уже найден

9 В некоторых случаях когда характеристическое уравнение относится к уравнениям специального вида его корни могут быть найдены с помощью подстановки К таким уравнениям относятся например симметрические и возвратные уравнения Симметрическим называется уравнение степени - четное вида x bx cx cx bx 3 Симметрические уравнения являются частным случаем возвратных К возвратным относятся уравнения вида x bx cx / c x / / b x где - некоторый коэффициент Рассмотрим например решение симметрических и возвратных уравнений четвертой степени Пусть дано симметрическое уравнение 4 x 3 bx cx bx Сначала понизим его степень разделив обе части на x Получим уравнение x bx c b / x / x 4 Произведем следующую подстановку: t x / x 5 Тогда учитывая что t x / x выражение 4 можно записать как t bt c 6 Решив уравнение 6 как обычное квадратное уравнение получим два корня t и t Теперь подставляя поочередно корни t и t в уравнение 5 получим два квадратных уравнения x tx x t x 7 Решение уравнений 7 дает нам все четыре корня исходного уравнения 3 Таким образом решение симметрического уравнения четвертой степени сводится к решению трех квадратных уравнений Аналогично решаются и возвратные уравнения Если уравнение четвертой степени можно представить в виде 4 x 3 bx cx bx 8 то его решение может быть получено с помощью подстановки t x / x 9 Также как и в предыдущем случае понизим степень уравнения поделив обе части на x Для получившегося уравнения x bx c b / x / x воспользуемся подстановкой 9 Тогда уравнение можно переписать в виде t bt c Так же как и в предыдущем примере решим уравнение и получим два корня t и t Теперь подставляя поочередно корни t и t в уравнение 9 получим два квадратных уравнения x tx x t x Решив систему уравнений получим четыре корня исходного уравнения 8 Таким образом решение возвратного уравнения четвертой степени также сводится к решению трех квадратных уравнений

10 РЕШЕНИЕ НЕОДНОРОДНЫХ ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ УРАВНЕНИЙ Линейное рекуррентное уравнение называется неоднородным если его можно представить в следующем виде: f 3 где f - некоторая функция от Введем однородное линейное рекуррентное уравнение ОЛРУ соответствующее неоднородному линейному рекуррентному уравнению НЛРУ 3 F 4 а его общее решение обозначим через FO По аналогии с методами решения дифференциальных уравнений вначале пренебрежем начальными условиями и предположим что одно решение уравнения 3 уже найдено Назовем это решение частным и обозначим его через Будем искать общее решение НЛРУ в виде суммы F его частного решения и общего решения соответствующего ему ОЛРУ F 5 3 O Покажем что 5 действительно является решением НЛРУ 3 Подставим 5 в F F F F O O F F F F f O O но это уравнение является тождеством так как FO FO F O F F F F f где первое уравнение в системе есть общее решение ОЛРУ а второе частное решение НЛРУ Пусть НЛРУ имеет вид РЕШЕНИЕ НЛРУ ПРИ ФУНКЦИИ-КОНСТАНТЕ 6 b где b - целое число константа Будем искать частное решение уравнения 6 в виде константы F c 7 то есть c - также целое число Подставим 7 в 6 c c c c b b c 8 Константа будет частным решением уравнения 6 при условии неравенства нулю знаменателя формулы 8 Введем характеристический полином для НЛРУ 6 Если h h то очевидно что уравнение 6 имеет частное решение

11 b F h Обозначим формальную производную характеристического полинома Тогда h h через h 9 h 3 Пусть h но h Будем искать решение 6 в виде F c 3 Подставляя 3 в 6 имеем c c c c b c b c h h b но h а h и b c h Итак если h то уравнение 6 имеет частное решение b F h Обозначим -ю производную h через h По определению будем считать h h Из курса алгебры известно что если число α является -кратным корнем многочлена h то h α Теперь частное решение 6 можно записать в виде b F 3 h где - кратность корня характеристического многочлена h Пример Решить уравнение 5 при F 35 Составляем ОЛРУ F Составляем характеристическое уравнение h 3 Решаем характеристическое уравнение 4 Записываем общее решение ОЛРУ F C C C C 5 Находим частное решение НЛРУ 5 F 5 h так как h 6 Записываем общее решение НЛРУ F F C C 5 7 С учетом начальных условий находим коэффициенты в решении НЛРУ

12 C C 5 C C 5 35 получаем C C 8 Записываем решение НЛРУ F 5 Итак мы получили явную формулу для вычисления -го члена последовательности В заключение вычислим саму последовательность: Будем искать частное решение НЛРУ РЕШЕНИЕ НЛРУ ПРИ ФУНКЦИИ-МНОГОЧЛЕНЕ F b 33 в виде многочлена той же степени что и в правой части F c 34 Подставляя 34 в 33 получим правило вычисления коэффициентов многочлена j c j b 35 j Приравнивая коэффициенты в левой и правой части при членах содержащих получаем Остальные коэффициенты c c b b c при h h находятся аналогично путем приравнивания коэффициентов при в 35 Если является корнем характеристического уравнения h кратности то частное решение НЛРУ следует искать в виде F c РЕШЕНИЕ НЛРУ ПРИ ФУНКЦИИ-ЭКСПОНЕНТЕ Будем искать частное решение НЛРУ F bα 37 в виде 36 Подставляя 38 в 37 имеем То есть F cα cα bα 38

13 bα F h α если α не является корнем характеристического уравнения h Если же α является корнем характеристического уравнения кратности то частное решение 37 следует искать в виде F dα где d - некоторая константа Пример При решении одной задачи теории кодирования установлена рекуррентная зависимость числа умножений M от числа итераций при построении проверочной матрицы кода M M 4 3 при M 7 Запишем ОЛРУ M M Тогда имеем характеристическое уравнение h и общее решение ОЛРУ M C Будем искать частное решение в виде M d e Подставляя его в исходное уравнение имеем e 4 3 Левая часть уравнения не содержит d и следовательно предлагаемое частное решение определено неверно так как корень характеристического уравнения Теперь изменим вид частного решения на M d e Подставляя его в исходное уравнение имеем e 3 d Таким образом M C 3 и учитывая начальные условия C 3 Итак решение исходного уравнения M 3 3 РЕКУРРЕНТНЫЕ УРАВНЕНИЯ ОБЩЕГО ВИДА Рекуррентные уравнения отличные от линейных рекуррентных уравнений с постоянными коэффициентами не имеют общего метода решения Они могут решаться например методом проб и ошибок Рассмотрим нелинейное уравнение F F b при F b 39 Вычислим значение при подстановке в 39 некоторых констант F b b b при; F F b b b при;

14 b b b F F при 3 Теперь можно предположить что решением уравнения 39 является 4 og b F где Подставляя 4 в 39 имеем og og og b b b b b b F F og og j j b b Таким образом 4 действительно является решением уравнения 39

Тема 7 Ранг матрицы Базисный минор Теорема о ранге матрицы и ее следствия Системы m линейных уравнений с неизвестными Теорема Кронекера- Капелли Фундаментальная система решений однородной системы линейных

СПРАВОЧНИК ПО МАТЕМАТИКЕ 5 9 классы МОСКВА «ВАКО» 201 УДК 32.851 ББК 4.262.22 С4 6+ Издание допущено к использованию в образовательном процессе на основании приказа Министерства образования и науки РФ

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 1 / 78 Часть I Конечные поля или поля Галуа. II ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 2 / 78 Поля вычетов по модулю

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа). II 1 / 78 Часть I Конечные поля (поля Галуа). II ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа). II 2 / 78 Поля вычетов по модулю простого

Лекция 7 2 Уравнения Фредгольма 2го рода с вырожденными ядрами Этот случай отличается тем, что решение интегрального уравнения сводится к решению линейной алгебраической системы и может быть легко получено

8 ЛИНЕЙНЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ ВТОРОГО ПОРЯДКА С ПЕРЕМЕННЫМИ КОЭФФИЦИЕНТАМИ 8 Основные понятия Линейным дифференциальным уравнением -го порядка с переменными коэффициентами называется уравнение

Лекция. Элементы теории многочленов. Многочлен (некоторые сведения справочного характера) Функция вида: 1 P (x) a0x a1x... a 1x a = + + + + (1) где натуральное число a i (i = 01...) постоянные коэффициенты

Занятие 4 Интегрирование рациональных функций (продолжение) Рациональной функцией (или, по-просту, дробью) называется отношение двух многочленов, то есть функция вида R() = f() g() = a 0 m + a m +...+

Министерство образования и науки Российской Федерации Санкт-Петербургский государственный архитектурно-строительный университет В Б СМИРНОВА, Л Е МОРОЗОВА ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ Учебное

Федеральное агентство по образованию ГОУ ВПО «Уральский государственный технический университет УПИ» НМ Кравченко Дифференциальные уравнения и ряды Учебно-методическое пособие Научный редактор доц, канд

Тема 2-19: Билинейные и квадратичные формы А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для механиков

Тема Неопределенный интеграл Основные методы интегрирования Интегрирование по частям Пусть u и v две дифференцируемые функции одного и того же аргумента Известно, что d(u v) udv vdu (77) Возьмем от обеих

Тема 4. ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ -1- Тема 4. ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ 4.0. Постановка задачи Задача нахождения корней нелинейного уравнения вида y=f() часто встречается в научных

Научно-исследовательская работа Тема работы «Разложение многочлена пятой степени на квадратичные множители с помощью интерполяционного многочлена Лагранжа» Выполнил: Шабуневич Эдуард Олегович учащийся

~ ~ Дифференциальные уравнения Общие сведения о дифференциальных уравнений Задача на составление дифференциальных уравнений Определение: дифференциальным уравнением называется такое уравнение, которое

Глава Неопределенный интеграл Непосредственное интегрирование Функцию F() называют первообразной для функции f(), если выполняется равенство F"() f() Совокупность всех первообразных данной функции f()

МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ РЯЗАНСКАЯ ГОСУДАРСТВЕННАЯ РАДИОТЕХНИЧЕСКАЯ АКАДЕМИЯ ГС ЛУКЬЯНОВА АИНОВИКОВ РАЦИОНАЛЬНЫЕ И ИРРАЦИОНАЛЬНЫЕ УРАВНЕНИЯ И НЕРАВЕНСТВА Рязань Министерство

Лекция 9 Линеаризация диффе6ренциальных уравнений Линейные дифференциальные уравнения высших порядков Однородные уравнения свойства их решений Свойства решений неоднородных уравнений Определение 9 Линейным

Лекция 3 Экстремум функции нескольких переменных Пусть функция нескольких переменных u = f (x, x) определена в области D, и точка x (x, x) = принадлежит данной области Функция u = f (x, x) имеет

Решения задач шестой студенческой олимпиады по алгебре Задача 1 Докажите, что если все элементы действительной квадратной матрицы порядка больше двух отличны от нуля, то их можно умножить на положительные

Тема 1 Действительные числа и действия над ними 4 часа 11 Развитие понятия о числе 1 Первоначально под числами понимали лишь натуральные числа, которых достаточно для счета отдельных предметов Множество

95 Билинейные и квадратичные функции Билинейная функция Определение Билинейной функцией (билинейной формой) на линейном пространстве L называется функция от двух векторов из L линейная по каждому из своих

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Новосибирский национальный исследовательский государственный университет» СИСТЕМЫ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ

СПРАВОЧНИК Некоторые признаки делимости натуральных чисел Натуральные числа это числа, используемые для счёта:, Натуральные числа образуют множество, называемое множеством натуральных чисел Множество

1 УДК 517 96 1. Решение уравнения Риккати и его применение к линейным уравнениям второго порядка Чочиев Тимофей Захарович, кандидат физико-математических наук, старший научный сотрудник Южный Математический

Системы дифференциальных уравнений Введение Также как и обыкновенные дифференциальные уравнения системы дифференциальных уравнений применяются для описания многих процессов реальной действительности В

Министерство общего и профессионального образования Российской Федерации РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Е. Я. Файн МЕТОДИЧЕСКОЕ ПОСОБИЕ по курсу ЭЛЕМЕНТАРНАЯ МАТЕМАТИКА для студентов первого курса

ЛЕКЦИЯ 2 СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ ОПРЕДЕЛИТЕЛИ МАЛЫХ ПОРЯД- КОВ 1 ЭКВИВАЛЕНТНОСТЬ ЛИНЕЙНЫХ СИСТЕМ Пусть нам дана еще одна линейная система того же размера a 11x 1 + a 12x 2 + + a 1nx n = b 1, a 21x 1

{ общие понятия - теорема Коши - линейный дифференциальный оператор - основные теоремы - линейная независимость решений - определитель Вронского - вронскиан однородного линейного дифференциального уравнения

Глава ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ Основные понятия и определения Дифференциальным уравнением называется уравнение связывающее независимую переменную х искомую функцию (у f (х и производные искомой функции

Метод разделения переменных (метод Фурье) Общие принципы метода разделения переменных Для простейшего уравнения с частными производными разделение переменных это поиски решений вида только от t. u (x,t

О РЕШЕНИИ В НАТУРАЛЬНЫХ ЧИСЛАХ УРАВНЕНИЙ ВИДА В диофантовом анализе уравнения вида относятся к трудно разрешимым. В настоящее время неизвестен общий метод полного решения даже простейших уравнений этого

Алгебра: 7 класс. Урок 2. Числовые выражения. Выражения с переменными Добрый день, ребята! На прошлом уроке мы повторили темы, изученные в 6 классе. Вспомнили, как выполнять действия с обыкновенными и

Г л а в а 2 ВЕКТОРНЫЕ ПРОСТРАНСТВА 9 Векторное пространство над полем 91 Аксиоматика Пусть задано поле P, элементы которого будем называть скалярами и некоторое множество V, элементы которого будем называть

Цепные дроби Конечные цепные дроби Определение Выражение вида a 0 + a + a + + a m где a 0 Z a a m N a m N/{} называется цепной дробью а m - длиной цепной дроби a 0 a a m будем называть коэффициентами цепной

Содержание Элеметарная теория погрешностей. Решение СЛАУ. 4. Нормы в конечномерных пространствах... 4. Обусловленность СЛАУ............ 5.3 Итерационные методы решения линейных систем......................

Министерство образования и науки РФ Уральский государственный экономический университет Ю. Б. Мельников Поле. Расширения полей Раздел электронного учебника для сопровождения лекции Изд. 4-е, испр. и доп.

Министерство образования и науки Российской Федерации НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ Кафедра прикладной механики и математики ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ

Глава 7 Понятие об асимптотических методах Лекция Регулярно и сингулярно возмущенные задачи При построении математических моделей физических объектов, характеризующихся различными масштабами по пространству,

Числа Фибоначчи.

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

Отсюда видно, что всегда может быть сведён к факториалу от меньшего числа.

Хорошей иллюстрацией к построению рекуррентных соотношений является задача Фибоначчи. В своей книге в 1202 ᴦ. итальянский математик Фибоначчи привел следующую задачу. Пара кроликов приносит приплод раз в месяц двух крольчат (самку и самца), причём новорождённые крольчата через два месяца после рождения сами приносят приплод. Сколько кроликов появится через год, если в начале была одна пара кроликов.

Из условия задачи следует, что через месяц будет две пары кроликов, через два месяца приплод даст только первая пара кроликов, появившихся два месяца назад, в связи с этим всего будет 3 пары кроликов. Ещё через месяц будет уже 5 пар. И так далее.

Обозначим через количество пар кроликов по истечении месяцев с начала года. Тогда через месяц количество пар кроликов можно найти по формуле:

Эта зависимость принято называть рекуррентным соотношением . Слово «рекурсия» означает возврат назад (в нашем случае – возврат к предыдущим результатам).

По условию, и , тогда по соотношению имеем: , , и т.д., .

Определение 1: Числа называются числами Фибоначчи . Это – известная в математике последовательность чисел:

1, 1, 2, 3, 5, 8, 13, 21, ...

В этой последовательности каждое последующее число является суммой двух предыдущих чисел. И в рекуррентном соотношении также последующий член находится как сумма двух предыдущих членов.

Установим связь между числами Фибоначчи и комбинаторной задачей. Пусть требуется найти число - последовательностей, состоящих из нулей и единиц, в которых никакие две единицы не стоят подряд.

Возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар «предков» данной пары (включая и исходную), а нулями – все остальные месяцы. К примеру, последовательность устанавливает такую «генеалогию» – сама пара появилась в конце 11-го месяца, ее родители в конце 7-го месяца, «дед» – в конце 5-го месяца, и «прадед» в конце 2-го месяца. Первоначальная пара шифруется последовательностью . Ни в одной последовательности две единицы не могут стоять подряд – только что появившаяся пара не может принести приплод через месяц. Очевидно, различным последовательностям отвечают различные пары и обратно.

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, число последовательностей с указанными свойствами, равно .

Теорема 1: Число находится как сумма биномиальных коэффициентов:. В случае если – нечетно, то . В случае если – четно, то . Иначе: – целая часть числа .

Доказательство: В самом деле, - число всех последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число таких последовательностей, содержащих ровно единиц и нулей, равно , при этом , тогда изменяется от 0 до . Применяя правило суммы, получаем данную сумму.

Это равенство можно доказать иначе. Обозначим:

Из равенства , следует, что . Кроме этого, ясно, что и . Так как обе последовательности и удовлетворяют рекуррентному соотношению , то , и .

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

К примеру, – рекуррентное соотношение второго порядка, а рекуррентное соотношение 3-го порядка. Соотношение Фибоначчи является соотношением второго порядка.

Определение 3:Решением рекуррентного соотношения является последовательность, удовлетворяющая этому соотношению.

В случае если задано рекуррентное соотношение ‑ го порядка, то ему удовлетворяют бесконечно много последовательностей, т.к. первые элементов можно задать произвольно. Но если первые элементов заданы, то остальные члены определяются однозначно.

К примеру, соотношению Фибоначчи кроме рассмотренной выше последовательности 1, 1, 2, 3, 5, 8, 13, 21, ..., могут удовлетворять также и другие последовательности. К примеру, последовательность 2, 2, 4, 8, 12,... строится по тому же принципу. Но если задать начальные члены (их в последовательности Фибоначчи - 2), то решение определяется однозначно. Начальных членов берут столько, каков порядок соотношения.

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

Мы будем говорить, что некоторая последовательность является решением данного рекуррентного соотношения, если при подстановке этой последовательности соотношение тождественно выполняется.

К примеру, последовательность является одним из решений соотношения: . Это легко проверить обычной подстановкой.

Определение 4: Решение рекуррентного соотношения ‑ го порядка принято называть общим , если оно зависит от произвольных постоянных , меняя которые, можно получить любое решение данного соотношения.

К примеру, для соотношения общим решение будет .

В самом деле, легко проверяется, что оно будет решением нашего соотношения. Покажем, что любое решение можно получить в таком виде. Пусть и – произвольны.

Тогда найдутся такие и , что

Очевидно, для любых , система уравнений имеет единственное решение.

Определение 5: Рекуррентное соотношение принято называть линейным , если оно записывается в виде:

где - числовые коэффициенты.

Для решения произвольных рекуррентных соотношений общих правил, вообще говоря, нет. При этом для решения линейных рекуррентных соотношений есть общие правила решения.

Рассмотрим сначала соотношение 2-го порядка .

Решение этого соотношения основано на следующих утверждениях.

Теорема 2: В случае если и - являются решением данного рекуррентного соотношения 2-го порядка, то для любых чисел и последовательность также является решением этого соотношения.

Теорема 3: В случае если число является корнем квадратного уравнения , то последовательность является решением рекуррентного соотношения .

Из теорем 2, 3 вытекает следующее правило решения линейных рекуррентных соотношений 2-го порядка.

Пусть дано рекуррентное соотношение .

1) Составим квадратное уравнение , ĸᴏᴛᴏᴩᴏᴇ принято называть характеристическим для данного соотношения. Найдём все корни этого уравнения (даже кратные и комплексные).

2) Составим общее решение рекуррентного соотношения. Его структура зависит от вида корней (одинаковые они или различные).

а) В случае если это соотношение имеет два различных корня и , то общее решение соотношения имеет вид .

Действительно, из теорем 2, 3 следует, что - решение и система уравнений

Имеет единое решение, т.к. при условии .

К примеру, для чисел Фибоначчи, имеем . Характеристическое уравнение имеет вид: . Решая последнее уравнение, получим корни.

Последовательность удовлетворяет следующему соотношению где - некоторые числа. При заданных значениях формула (1) полностью определяет последовательность; каждый ее элемент, начиная с к-го, является линейной комбинацией предыдущих к элементов с коэффициентами поэтому формулу (1) называют линейным рекуррентным соотношением к-го порядка. Если положить можно переписать в виде ИЛИ Решение линейных рекуррентных уравнений Поставим задачу - перейти от рекуррентного задания последовательности к формуле, выражающей зависимость общего члена последовательности хп от его номера п. Для решения этой задачи введем в рассмотрение: - производящую функцию последовательности - характеристический многочлен - многочлен Отметим следующую связь между многочленами: при. Докажем, что F(t) является дробно-рациональной функцией. Действительно, где коэффициенты Cm определяются по коэффициентам а^ и первым к членам последовательности Итак,) - многочлен степени не выше к- 1; поэтому F(t) = - правильная рациональная дробь. Дальнейший ход наших выкладок будет следующим: мы представим F(t) в виде суммы простейших дробей, запишем разложения простейших дробей по степеням переменной t, после чего по виду полученного ряда для F(t) будет ясен характер зависимости хп от п. Пусть характеристический многочлен /(А) имеет s различных (комплексных) корней: Aj кратности Г|, ..., Ха кратности rs: Как известно из алгебры, разложение правильной рациональной дроби со знаменателем g(t) на простейшие дроби имеет вид где некоторые константы. Применив биномиальное разложение, получим Таким образом, или, поскольку - многочлен от п степени (при фиксированном j)> где - некоторый многочлен степени не выше Мы доказали, что обший член последовательности, удовлетворяющей линейному рекуррентному соотношению fc-ro порядка, имеет вид где для число - корень кратности г, характеристического многочлена рекуррентного соотношения, Р*(я) - многочлен степени, не превосходящей г, - 1. Конкретный вид указанных многочленов определяется первыми к членами последовательности: В частности, если все корни характеристи- ческого многочлена - простые (т.е. кратности 1), то последовательность (ж„) представима в виде суммы геометрических прогрессий: где Ci - некоторые константы. Рассмотрим несколько примеров. Пример 1. Последовательность чисел Фибоначчи задается соотношениями Составим характеристическое уравнение: формула общего члена: Коэффициенты С\ и Cj определим из -начальных условий»: . Решив систему двухуравнений с двумя неизвестными, получим окончательный результат: Пример 2. Найдем все последовательности, удовлетворяющие условию Характеристическое уравнение А2 - 2А4- 1 =0 имеет двукратный корень: Au = 1, поэтому общий член последовательности имеет вид: где константы о и 6 определяются первыми двумя членами последовательности. Таким образом, (х„) - арифметическая прогрессия. Этот результат можно было предвидеть, заметив, что соотношение (3) является характеристическим для арифметической прогрессии: каждый член последовательности, начиная со второго, есть среднее арифметическое его соседних членов. ПримерЗ. Найдем последовательность (z„), задаваемую соотношениями Разложим характеристический многочлен на множители: Вид n-го члена последовательности:. Константы а, Ь, с найдем из системы уравнений Ответ: Упражнения Решение линейных рекуррентных уравнений Правило произведения 1. Из города А в город Б ведут 5 дорог, а из города Б в город В - 7 дорог. Сколько есть различных маршрутов из города А в В через Б? 2. В меню столовой 3 первых, 5 вторых и 3 третьих блюда. Сколькими способами можно выбрать обед из трех блюд (первое, второе и третье)? 3. Сколько есть двузначных чисел, не содержащих цифр 4. Сколько есть двузначных чисел, не содержащих цифр Номер автомашины состоит из трех букв латинского алфавита (содержащего 26 букв) и трех цифр. Сколько можно составить различных номеров автомашин? 6. У рояля 88 клавиш. Сколькими способами можно извлечь последовательно 6 звуков? 7. Сколько натуральных делителей имеет число 8. Сколько натуральных делителей имеет число 9. Сколько есть пятизначных чисел, 1) оканчивающихся двумя семерками? 2) начинающихся с двух одинаковых цифр? 3) в каждом из которых нет одинаковых цифр? 4) в каждом из которых соседние цифры различны? 5) делящихся на 4 и не содержащих цифр 6) в записи которых есть одинаковые цифры? 7) в записи которых есть хотя бы одна четная цифра? Решение линейных рекуррентных уравнений 10. Сколько есть перестановок цифр в которых 1) цифра 3 занимает третье место, а цифра 5 - пятое? 2) цифра 1 следует непосредственно за цифрой 0? 3) цифра 0 занимает одно из первых трех мест, а цифра 1 - одно из последних четырех мест? 4) цифра 0 занимает одно из первых пяти мест, а цифра 1 - одно из первых трех мест? 5) между цифрами 0 и 1 стоят ровно три цифры? 6) цифра 0 расположена левее цифры 1? 7) цифра 1 расположена между цифрами 0 и 2? 8) хотя бы одна из первых трех цифр делится на 3? 11. Сколькими способами можно рассадить за десятью партами 10 мальчиков и 10 девочек так, чтобы за каждой партой сидели а) мальчик слева, а девочка справа? б) мальчик и девочка? 12. Сколькими способами можно прочитать слово ПАРУС, двигаясь вправо или вниз по каждой из следующих таблиц? Сколькими способами можно расставить на шахматной доске 8 одинаковых ладей так, чтобы никакие две из них не били друг друга? 14. Сколькими способами можно расставить на шахматной доске 8 одинаковых ладей так, чтобы они били все поля? Сочетания 15. Вычислить: 16. Найти число подмножеств X множества обладающих следующими свойствами: 5) множество X состоит из трех четных и двух нечетных чисел; 17. На окружности последовательно отмечены точки Сколько существует 1) хорд с концами в отмеченных точках; 2) треугольников с вершинами в отмеченных точках; 3) выпуклых четырехугольников с вершинами в отмеченных точках; 4) треугольников с вершинами в отмеченных точках, не имеющих обших точек с прямой А2Ая; 5) треугольников с вершинами в отмеченных точках, имеющих общие точки с прямой AiA}? 18. На окружности отмечено п точек. Точки соединяются всевозможными хордами; известно, что никакие три из них не пересекаются в одной точке внутри круга. Найти: 1) число точек пересечения хорд внутри круга; 2) количество частей, на которые хорды делят круг. 19. На прямой I отмечено 8 точек, а на параллельной ей прямой m точек. Сколько существует 1) треугольников с вершинами в отмеченных точках; 2) выпуклых четырехугольников с вершинами в отмеченных точках? 20. Две команды играют в волейбол до 4 побед. Сколько существует разных вариантов изменения счета в игре по партиям? 21. Сколькими способами можно разложить 4 белых и 3 черных шара по 6 различным ящикам? 22. Решить предыдущую задачу при дополнительном условии: ни один яшик не должен быть пустым. 23. Сколькими способами можно разложить 20 одинаковых шаров по 5 различным яшикам так, чтобы 1) в каждом ящике оказалось не менее двух шаров; 2) в каждом ящике оказалось не более 5 шаров; 3) оказалось не более двух пустых яшиков? 24. Найти коэффициент при г100 в разложении многочлена Дан квадрат. Каждая его сторона разбита на п равных частей. Через точки деления проведены прямые, параллельные сторонам. Сколько существует 1) прямоугольников; 2) квадратов, ограниченных проведенными линиями? 26. В правлении банка 7 человек. Каково должна быть минимальное число замков от сейфа и как следует распределить ключи меж^у членами правления (каждый член правления может получить ключи от нескольких замков), чтобы любое большинство сейф могло открыть, а любое меньшинство - не могло? 27. Каким числом способов можно прочитать слово «абракадабра», двигаясь вправо или вниз по таблице (с. 76)? На клетчатой бумаге нарисован прямоугольник ABCD, стороны которого лежат на линиях сетки, причем длина отрезка AD в к раз больше длины отрезка АВ (к - натуральное число). Рассматриваются всевозможные пути, проходящие по линиям сетки и кратчайшим образом ведущие из А в С. Доказать, что среди этих путей в к раз больше тех, у которых первое звено лежит на AD, чем тех, у которых первое звено лежит на АВ. 29. Изучите поведение последовательности (о*), где ак = С* (при фиксированном п), с точки зрения возрастания-убывания. 30. Имеется карточная колода из 52 карт. Каким числом способов можно раздать по 13 карт четырем игрокам? Полиномиальная формула 31. Найти коэффициент при хк в разложении многочленов: Комбинаторные тождества 32. С помощью формулы бинома Ньютона Решение линейных рекуррентных уравнений доказать следующие тождества: 33. С помощью комбинаторных рассуждений доказать: Формула яключения-исключения 34. На кафедре лингвистики работают 13 человек, причем каждый из них знает хотя бы один иностранный язык. Десять человек знают английский язык, семеро немецкий, шестеро - французский. Пятеро знают английский и немецкий, четверо - английский и французский, трое - немецкий и французский. Сколько человек знают 1) все три языка; 2) ровно два языка; 3) только английский язык? 35. 1) Показать, что количество натуральных чисел, делящихся на п и не превосходящих положительного числа х, равно 2) Сколько есть чисел, не превосходящих и не делящихся ни на ни на, ни на 3) Сколько есть четырехзначных чисел, не делящихся ни на, ни на, ни на 4) Сколько есть чисел, не превосходящих и не делящихся ни на одно из чисел 5) Показать, что если п = 30т, то количество натуральных чисел, не превосходящих п и не делящихся ни на одно из чисел равно. 36. Пусть. Показать, что простых чисел в множестве не больше восьми. 37. На каждой стороне треугольника А ВС отмечено по п точек, разбивающих ее на п + 1 равных частей. Рассмотрим всевозможные треугольники с вершинами в отмеченных точках (по одной на каждой стороне). Сколько среди этих треугольников таких, у которых ни одна из сторон не параллельна стороне треугольника ABC? 38. Сколько существует б-значных номеров (первые цифры могут быть и нулями) с суммой цифр 27? 39. В кошельке лежит по 20 монет достоинством в рублей. Сколькими способами можно из этих 60 монет выбрать к монет (к ^ 60)? Задача о беспорядках и встречах 40. С помощью рекуррентных соотношений найти число беспорядков Dn для 42. Сколькими способами можно расставить на шахматной доске 8 одинаковых ладей так, чтобы никакие две из них не били друг друга и чтобы ни одна ладья не стояла на главной диагонали? 43. Сколькими способами можно раскрасить клетки шахматной доски 8 х 8 в 8 цветов так, чтобы клетки, имеющие обшую сторону, были бы окрашены в разные цвета и чтобы в каждом горизонтальном ряду встречались все 8 цветов? 44. Две колоды карт, содержащие по 52 карты, тщательно тасуются, после чего сравниваются карта за картой. Какова вероятность того, что не будет ни одной пары совпадающих карт? 45. Для числа перестановок п элементов с А: встречами Dn,k доказать тождества: Случайным образом выбирается перестановка чисел 1,2..., п. Пусть £ - количество элементов, остающихся на своих местах. Найти математическое ожидание и дисперсию случайной величины 47. Секретарше нужно отправить п различных писем по п различным адресам. Она подписывает конверты и случайным образом вкладывает письма в конверты. Сколько в среднем писем дойдет до своего адресата? Производящие функции Найти производящие функции следующих последовательностей: Пусть - последовательности, - соответствующие производящие функции. Выразить А(х) через В(х) при следующих соотношениях между последовательностями: Пусть an = С?Ък. Доказать, что bn = Рекуррентные соотношения 64. Последовательность (a„) удовлетворяет соотношению уравнение имеет два различных ненулевых корня х, и х2. Доказать, что имеет место тождество для некоторых С| и с2, однозначно определяемых Найти формулу общего члена последовательности: 66. Найти количество n-значных чисел, состоящих из цифр, в которых первая и последняя, а также любые две соседние цифры различны. 67. Сколько существует раскрасок вершин n-угольника, если соседние вершины должны быть разного цвета, а всего имеется к цветов? 68. Пусть n-й член последовательности задается формулой. Доказать, что для последовательности имеет место рекуррентное соотношение а, где 69. Найти а, если 70. Найти число двоичных последовательностей длины 11, не содержащих единиц ни в каких трех соседних позициях. 71. Найти обшие решения рекуррентных соотношений: 72. Найти ап по рекуррентным соотношениям и начальным условиям: 1) Каждая точка пересечения хорд однозначно задается (неупорядоченной) четверкой точек - концов этих хорд. Будем последовательно проводить хорды. Пусть kt - число точек пересечения t"-й хорды с ранее проведенными. Этими точками «-я хорда делится на fc, + 1 отрезков, каждый из которых, в свою очередь, делит одну «старую» часть разбиения круга на две «новые». Изначально имелась одна часть. После проведения всех N хорд количество частей равно Осталось заметить, что N = а обшее количество точек пересечения хорд Решение линейных рекуррентных уравнений (согласно первому пункту данной задачи). Интересен ответ к задаче при Он "гаков: Физик из известного анекдота на основании первых пяти результатов заявил бы, что общий ответ - 2я"а число 31 возникло в результате погрешности эксперимента. . Составьте отношение. Подсчитайте двумя способами сумму мощностей всех подмножеств п-элементного множества. 3 при нечетном при четном п. . Решение. Пусть U - множество последовательностей (составленных из шести неотрицательных целых чисел с суммой 27; а для каждого i множество Ai С U состоит из таких последовательностей, в которых Для решения -Заметим,что | а пересечение трех и большего числа множеств Ai пусто. 41. Используйте оценку остаточного члена ряда из признака Лейбница. Указание. Обозначим через о„ число двоичных последовательностей длины п, удовлетворяющих условию задачи. Найдите начальные условия и рекуррентное соотношение для последовательности (оп).

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

Введение

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

Идея производящих функций достаточно проста: сопоставим некоторой последовательности - дискретному объекту, степенной ряд g 0 + g 1 z + g 2 z 2 +… + g n z n +… - объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.

История возникновения производящих функций

Известно, что начало методу производящих функций положил английский математик Абрахам де Муавр, а дальнейшему развитию и продолжению данного метода мы обязаны великому математику, имя которого Леонард Эйлер.

В 50-х годах XVIII века Эйлер решал следующую задачу: какие грузы можно взвесить с помощью гирь в 2 0 , 2 1 , 2 2 ,..., 2 n грамм и сколькими способами? При решении этой задачи он использовал никому неизвестный на то время метод производящих функций , которому и посвящена данная статья. К этой задаче мы вернёмся немного позже, после того как разберёмся более подробно с устройством производящих функций.

Метод производящих функций

Изучение этого мощного механизма позволяющего решать многие задачи, мы начнём с простенькой задачи: сколькими способами можно расположить в линию чёрные и белые шары, общее количество которых равно n?

Обозначим белый шар символом ○, чёрный - ●, T n - искомое количество расположений шаров. Символом Ø - обозначим нулевое количество шаров. Как и любое решение комбинаторной задачи начнём с тривиальных случаев:

Если n=1, то очевидно имеется 2 способа - взять либо белый шар ○, либо взять чёрный шар ●, таким образом, T 2 = 2.

Если n=2, то имеется 4 способа расположений: ○○, ○●, ●○, ●●.

Рассмотрим случай для n=3. Мы можем начать белым шаром и продолжить 4-мя комбинациями, описанными выше ○○○, ○○●, ○●○, ○●●, или же мы можем начать чёрным шаром и аналогично продолжить 4-мя шарами ●○○, ●○●, ●●○, ●●●.

В итоге количество шаров удвоилось, то есть T 3 = 2T 2 . Аналогично T 4 = 2T 3 , то есть, обобщая для всех n, получаем рекуррентное уравнение T n = 2T n-1 которое и является решением для данной задачи. Решение такого уравнения можно легко угадать - T n = 2 n (так как 2⋅2 n-1 = 2 n).

А что если у нас плохо с угадыванием? И что делать, если уравнение будет сложнее? А вообще причём здесь производящие функции?

«Просуммируем» все возможные комбинации расположений шаров:

G = Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ○○○ + ○○● + ○●○ + ○●● + ●○○ + ●○● + ●●○ + ●●● +…

Вопрос о допустимости такой нелепой на первый взгляд суммы опустим. Будем складывать и умножать последовательности шаров. Со сложением всё понятно, но что значит умножить одну последовательность шаров на другую? Перемножив ○● на ●○ мы получим не что иное как ○●●○. Заметим, однако, что произведение шаров в отличие от произведения чисел не является коммутативным, так как ○●⋅●○ ≠ ●○⋅○●. Символ Ø - в произведении играет роль мультипликативной единицы, то есть Ø ⋅ ○○● = ○○● ⋅ Ø = ○○● и коммутирует с любой последовательностью шаров.

Производя с рядом G последовательность манипуляций, а именно вынося за скобки левый белый и чёрный шары

G = Ø + ○ (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) + ● (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) = Ø + ○G +●G

Получим уравнение G = Ø + ○G +●G.

Несмотря на то, что умножение некоммутативно, и мы фактически не различаем левое и правое деление, попробуем всё же «решить» это уравнение, на свой страх и риск. Получим,

Учитывая формулу суммы геометрической прогрессии , имеем

В этой сумме так же учтены все возможные варианты разбиения в точности по одному разу. Далее воспользуемся формулой бинома Ньютона: , где - число сочетаний из n по k. Тогда с учетом этого имеем:

Коэффициент при ○ k ● n-k равный числу сочетаний из n по k, показывает общее количество последовательностей из n шаров содержащих ○ шары в количеств k штук и ● шары в количестве n-k штук. Таким образом, общее количество расположений n шаров есть сумма по всем возможным значениям k. Как известно .

Эту формулу можно было получить непосредственно из заменив Ø на 1, а ○ и ● на z (в виду их равнозначности). Получим то есть коэффициент при z n равен 2 n .

Обсуждение метода

Так что же позволяет данному методу быть работоспособным при решении различных задач?

Алгоритм решения задачи можно описать примерно следующим образом: рассматривается некоторая бесконечная сумма, которая в конечном итоге представляет собой формальный степенной ряд G(z) = g 0 + g 1 z + g 2 z 2 +… + g n z n +… причем коэффициенты g k (не заданные в явном виде) - являются ключом к решению исходной задачи. То, что ряд является формальным, говорит о том, что z - является просто символом, то есть вместо него может быть любой объект: число, шар, кость домино и т.д. В отличие от степенных рядов в анализе формальным степенным рядам не придается числовых значений и, соответственно, нет смысла говорить о сходимости таких рядов для числовых аргументов.

G(z) = g 0 + g 1 z + g 2 z 2 +… + g n z n +… - называется производящей функцией для последовательности . Заметим, однако, что хотя G(z) - функция, это всё таки формальная запись, то есть мы не можем подставить вместо z любое значение z = z 0 , за исключением z = 0, так как G(0) = g 0 .

Затем производя различные преобразования с бесконечной суммой G(z) мы преобразуем её к замкнутому (компактному) виду. То есть у производящей функции есть 2 представления: бесконечное и замкнутое и, как правило, для решения задачи необходимо бесконечный вид преобразовать к замкнутому, а затем замкнутый вид разложить в степенной ряд, и тем самым получить значения для коэффициентов g k .

Отвечая на поставленный вначале вопрос можно сказать так: успех данного метода связан с возможностью записать производящую функцию в замкнутом виде. Так, например, производящая функция для последовательности <1, 1, 1, ..., 1> в бесконечном виде представляется как 1 + x + x 2 + x 3 + ..., а в замкнутом .

А теперь вооружившись знаниями, вернемся к задаче, которую решал Эйлер.

Итак, задача звучит следующим образом: какие грузы можно взвесить с помощью гирь в 2 0 , 2 1 , 2 2 ,..., 2 n грамм и сколькими способам?

Я не знаю, как долго Эйлер придумывал решение для этой задачи, но оно поражает своей неожиданностью. Посудите сами. Эйлер рассматривает произведение G(z) = (1+z)(1+z 2)(1+z 4)… которое после раскрытия скобок представляется в виде бесконечного ряда G(z) = 1 + g 1 z + g 2 z 2 + g 3 z 3 +….

Что же из себя представляют коэффициенты g k ? Каждый g k - это коэффициент при z k , а z k - получается как произведение каких-то одночленов z 2m , то есть g k - это в точности число разных представлений числа k в виде суммы некоторых из чисел 1, 2, 2 2 , 2 3 ,..., 2 m ,…. Другими словами g k - это число способов взвешивания груза в k грамм заданными гирями. Как раз то, что мы искали!

Следующий шаг Эйлера поражает не менее предыдущего. Он умножает обе части равенства на (1-z).

(1-z)G(z) = (1-z)(1+z)(1+z 2)(1+z 4)(1+z 8)…
(1-z)G(z) = (1-z2)(1+z 2)(1+z 4)(1+z 8)…
(1-z)G(z) = (1-z 4)(1+z 4)(1+z 8)…
(1-z)G(z) = 1

С одной стороны G(z) = 1 + g 1 z + g 2 z 2 + g 3 z 3 +… с другой стороны мы только что получили . Последнее равенство есть не что иное, как сумма геометрической прогрессии, которая равна . Сопоставляя эти два равенства, получаем g 1 = g 2 = g 3 =… = 1, то есть любой груз в k грамм можно взвесить гирями в 1, 2, 4, 8,… грамм притом единственным способом.

Решение рекуррентных соотношений

Производящие функции подходят для решения не только комбинаторных задач. Оказывается, с их помощью можно решать рекуррентные соотношения.

Начнем со всеми знакомой последовательностью чисел Фибоначчи. Каждый из нас знает её рекуррентный вид: F 0 = 0, F 1 = 1, F n = F n-1 + F n-2 , n ≥ 2. Однако не каждый знает вид этой формулы в замкнутом виде и это не удивительно, ведь она содержит иррациональное число(«золотое сечение») в своём составе.

Итак, имеем

F 0 = 0,
F 1 = 1,
F n = F n-1 + F n-2 , n ≥ 2

Умножим каждую строчку на z 0 , z 1 , ..., z n соответственно:

Z 0 ⋅ F 0 = 0,
z 1 ⋅ F 1 = z,
z n ⋅ F n = z n ⋅ F n-1 + z n ⋅ F n-2 , n ≥ 2

Просуммируем эти равенства:

Обозначим левую часть

Рассмотрим каждое из слагаемых в правой части:

Имеем следующее уравнение G(z) = z + z G(z) + z 2 G(z) решая которое относительно G(z) находим

Производящая функция для последовательности чисел Фибоначчи.

Разложим её на сумму простейших дробей, для этого найдем корни уравнения . Решая это простое квадратное уравнение, получаем: . Тогда нашу производящую функцию можно разложить следующим образом:

Следующим шагом является нахождение коэффициентов a и b. Для этого умножим дроби на общий знаменатель:

Подставляя в это уравнение значение z = z 1 и z = z 2 , находим

Напоследок немного преобразуем выражение для производящей функции

Теперь каждая из дробей представляет собой сумму геометрической прогрессии.

По формуле находим

Но ведь мы искали G(z) в виде . Отсюда делаем вывод, что

Эту формулу можно переписать в другом виде не используя «золотое сечение»:

Что достаточно трудно было ожидать, учитывая красивое рекуррентное уравнение.

Давайте запишем общий алгоритм решения рекуррентных уравнений, используя производящие функции. Он записывается в 4 шага:

Причина, по которой данный метод работает, заключается в том, что единая функция G(z) представляет всю последовательность g n и это представление допускает многие преобразования.

Прежде чем переходить к следующему примеру, рассмотрим 2 операции, совершаемые над производящими функциями, которые часто оказываются полезными.

Дифференцирование и интегрирование производящих функций

Для производящих функций обычное определение производной можно записать следующим образом.

Пусть G = G(z) – производящая функция. Производной этой функции называется функция . Дифференцирование, очевидно, линейная операция, поэтому для того, чтобы понять, как оно действует на производящих функциях, достаточно посмотреть на его действие, на степенях переменной. Имеем

Тем самым, действие дифференцирования на произвольной производящей функции
G (z) = g 0 + g 1 z + g 2 z 2 + g 3 z 3 +… дает G΄(z) = g 1 + 2g 2 z + 3g 3 z 2 + 4g 4 z 3 +….

Интегралом называется функция

Операция дифференцирования обратна операции интегрирования:

Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, отличается от исходной функции,

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

Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:

G 0 = 1,
g 1 = 1,
g n = g n-1 + 2g n-2 + (-1) n

Будем следовать вышеописанному алгоритму. Первое условие алгоритма выполнено. Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

Z 0 ⋅ g 0 = 1,
z 1 ⋅ g 1 = z,
z n ⋅ g n = z n ⋅ g n-1 + 2z n ⋅ g n-2 + (-1) n ⋅ z n

Левая часть представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через G(z). Рассмотрим каждое слагаемое:

Составляем уравнение:

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений z), получаем:

Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

С одной стороны мы искали G(z) в виде , с другой стороны .

Значит, .

Вместо заключения

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