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

Рекуррентным соотношением , рекуррентным уравнением или рекуррентной формулой называется соотношение вида , которое позволяет вычислять все члены последовательности
, если заданы ее первые k членов.

1. Формула
задает арифметическую прогрессию.

2. Формула
определяет геометрическую прогрессию.

3. Формула
задает последовательность чисел Фибоначчи .⁫

В случае, когда рекуррентное соотношение линейно и однородно, т. е. выполняется соотношение вида

(p =const), последовательность
называется возвратной . Многочлен

называется характеристическим для возвратной последовательности
. Корни многочлена
называются характеристическими .

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

Описание общего уравнения соотношения (1) имеет аналоги с описанием решения обыкновенного дифференциального уравнения с постоянными коэффициентами.

Теорема 1. 1. Пусть - корень характеристического многочлена (2). Тогда последовательность
, где c – произвольная константа, удовлетворяет соотношению (1).

2. Если
- простые корни характеристического многочлена (2), то общее решение рекуррентного соотношения (1) имеет вид , где
- произвольные константы.

3. Если - корень кратности
характеристического многочлена (2), то общее решение рекуррентного соотношения (1) имеет вид
, где - произвольные константы.

Зная общее решение рекуррентного уравнения (1), по начальным условиям,
можно найти неопределенные постоянные и те самым получить решение уравнения (1) с данными начальными условиями.

Пример 2. Найти последовательность
, удовлетворяющую рекуррентному соотношению
и начальным условиям
.

Корням характеристического многочлена
являются числа
. Следовательно, по теореме 3.1. общее решение имеет вид
. Используя начальные условия, получаем систему

решая которую, находим
и
. Таким образом,
.⁫

Рассмотрим неоднородное линейное рекуррентное уравнение

Пусть
- общее решение однородного уравнения (1), а
- частное (конкретное) решение неоднородного уравнения (3). Тогда последовательность
образует общее решение уравнения (3), и тем самым справедлива.

Теорема 2. Общее решение неоднородного линейного рекуррентного уравнения представляется в виде суммы общего решения соответствующего однородного линейного рекуррентного уравнения и некоторого частного решения неоднородного уравнения.

Таким образом, в силу теоремы 1. задача нахождения общего решения рекуррентного уравнения (3) сводится к нахождению некоторого частного решения.

В отдельных случаях имеются общие рецепты нахождения общего решения.

Если
(где ) не является характеристическим корнем, то, подставляя
в (3), получаем и отсюда
, т. е. частное решение можно задать формулой
.

Пусть
- многочлен степени r от переменной n , и число 1 не является характеристическим корнем. Тогда и частное решение следует искать в виде
. Подставляя многочлены в формулу (3), получаем

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

Пример. Найти решение уравнения

(4)

с начальным условием
.

Рассмотрим характеристический многочлен
. Так как
и правая часть
уравнения (3) равна n +1, то частное решение будем искать в виде
. Подставляя в уравнение (4), получаем . Приравнивая коэффициенты в левой и правой частях последнего равенства, получаем систему

откуда находим
. Таким образом, частное решение уравнения (4) имеет вид
. По теореме 3.1. общее решение однородного уравнения
задается формулой
, и по теореме 3.2. получаем общее решение уравнения (4):
. Из начального условия
находим
, т. е. . Таким образом,
.

Рекуррентное соотношение имеет порядок k , если оно позволяет выразить f(n+k) через f(n), f(n+1), …, f(n+k-1).

Пример.

f(n+2)=f(n)f(n+1)-3f 2 (n+1)+1 – рекуррентное соотношение второго порядка.

f(n+3)=6f(n)f(n+2)+f(n+1) – рекуррентное соотношение третьего порядка.

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

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

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

Пример . Последовательность 2, 4, 8, …, 2 n является решением для соотношения f(n+2)=3∙f(n+1) – 2∙f(n).

Доказательство . Общий член последовательности имеет вид f(n)=2 n . Значит, f(n+2)= 2 n+2, f(n+1)= 2n+1 . При любом n имеет место тождество 2 n+2 =3∙2 n+1 – 2∙2 n . Следовательно, при подстановке последовательности 2 n в формулу f(n+2)=3f(n+1) – 2f(n) соотношение выполняется тождественно. Значит, 2 n является решением указанного соотношения.

Решение рекуррентного соотношения k-го порядка называется общим , если оно зависит от k произвольных постоянных α 1 , α 2 , … α k и путем подбора этих постоянных можно получить любое решение данного соотношения.

Пример . Дано рекуррентное соотношение: f(n+2)=5f(n+1)-6f(n). Докажем, что его общее решение имеет вид: f(n)= α 2 n + β3 n .

1. Сначала докажем, что последовательность f(n)=α 2 n + β3 n является решением рекуррентного соотношения. Подставим данную последовательность в рекуррентное соотношение.

f(n)= α 2 n + β 3 n , значит, f(n+1)= (α 2 n+1 + β 3 n +1), f(n+2)= α 2 n+2 + β 3 n +2 , тогда

5f(n+1)-6f(n)=5∙(α 2 n+1 + β 3 n +1)-6∙(α 2 n + β 3 n)= α (5 2 n+1 –6 2 n)+ β (5 3 n +1 –6 3 n)= =α2 n ∙(10–6)+ β 3 n ∙(15 – 6)= α 2 n+2 + β 3 n +2 = f(n+2).

Рекуррентное соотношение выполняется, следовательно, α 2 n + β 3 n является решением данного рекуррентного соотношения.

2. Докажем, что любое решение соотношения f(n+2)=5f(n+1)–6f(n) можно записать в виде f(n)= α 2 n + β 3 n . Но любое решение рекуррентного соотношения второго порядка однозначно определяется значениями первых двух членов последовательности. Поэтому достаточно показать, что для любых а=f(1) и b=f(2) найдутся α и β такие, что 2 α +3 β =а и 4 α +9 β =b. Легко видеть, что система уравнений имеет решение для любых значений а и b.

Таким образом, f(n)= α 2 n + β 3 n является общим решением рекуррентного соотношения f(n+2)=5f(n+1)–6f(n).

Линейные рекуррентные соотношения с постоянными коэффициентами

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

f(n+k)=c 1 f(n+k-1)+c 2 f(n+k-2)+…+c k f(n).

Найдем решение общего линейного рекуррентного соотношения с постоянными коэффициентами первого порядка.

Линейное рекуррентное соотношение с постоянными коэффициентами первого порядка имеет вид: f(n+1)=c f(n).

Пусть f(1)=а, тогда f(2)=c∙f(1)=c∙a, f(3)=c∙f(2)=c 2 ∙a, аналогично f(4)=c 3 ∙a и так далее, заметим, что f(n)=c n -1 ∙f(1).

Докажем, что последовательность c n -1 ∙f(1) является решением рекуррентного соотношения первого порядка. f(n)=c n -1 ∙f(1), значит, f(n+1)=c n f(1). Подставляя это выражение в соотношение, получим тождество c n f(1)=с∙ c n -1 ∙f(1).

Рассмотрим теперь подробнее линейные рекуррентные соотношения с постоянными коэффициентами второго порядка , то есть соотношения вида

f(n+2)=C 1 ∙f(n+1)+C 2 ∙f(n). (*).

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

Свойства решений :

1) Если последовательность x n является решением (*), то и последовательность a∙x n тоже является решением.

Доказательство.

x n является решением (*), следовательно, выполняется тождество x n +2 =C 1 x n +1 +C 2 x n . Домножим обе части равенства на a. Получим a∙x n +2 =a∙(С 1 ∙x n +1 +С 2 ∙x n)= С 1 ∙a∙x n +1 +С 2 ∙a∙x n . Это означает, что ax n является решением (*).

2) Если последовательности x n и y n являются решениями (*), то и последовательность x n +y n тоже является решением.

Доказательство.

x n и y n являются решениями, следовательно, выполняются следующие тождества:

x n +2 =C 1 x n +1 +C 2 x n .

y n +2 =C 1 y n +1 +C 2 y n .

Выполним почленное сложение двух равенств:

x n +2 +y n +2 =С 1 ∙x n +1 +С 2 ∙x n + С 1 ∙y n +1 +С 2 ∙y n = С 1 ∙(x n +1 + y n +1)+С 2 ∙(x n +y n). Это означает, что x n +y n является решением (*).

3) Если r 1 является решением квадратного уравнения r 2 =С 1 r+С 2 , то последовательность (r 1) n является решением для соотношения (*).

r 1 является решением квадратного уравнения r 2 =С 1 r+С 2 , значит, (r 1) 2 =C 1 r 1 +C 2 . Помножим обе части равенства на (r 1) n . Получим

r 1 2 r 1 n =(С 1 r 1 +С 2) r n .

r 1 n +2 =С 1 r 1 n +1 +С 2 r 1 n .

Это означает, что последовательность (r 1) n является решением (*).

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

1. Составим характеристическое (квадратное) уравнение r 2 =С 1 r+С 2 . Найдём его корни r 1, r 2. Если корни различны, то общее решение имеет вид f(n)= ar 1 n +βr 2 n .

2. Найдём коэффициенты a и β. Пусть f(0)=a, f(1)=b. Система уравнений

имеет решение при любых а и b. Этими решениями являются

Задача. Найдем формулу для общего члена последовательности Фибоначчи.

Решение. Характеристическое уравнение имеет вид х 2 =х+1 или х 2 -х-1=0, его корнями являются числа , значит, общее решение имеет вид f(n)= . Как нетрудно видеть, из начальных условий f(0)=0, f(1)=1 вытекает, что a=-b=1/Ö5, и, следовательно, общее решение последовательности Фибоначчи имеет вид:

Что удивительно, это выражение при всех натуральных значениях n принимает целые значения.

Размер: 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 «Последовательности. Степени и корни» В тесте проверяются теоретическая и практическая части. Последовательности Числовые последовательности. Способы задания числовых последовательностей.

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

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

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

Хорошей иллюстрацией к построению рекуррентных соотношений является задача Фибоначчи. В своей книге в 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) Составим общее решение рекуррентного соотношения. Его структура зависит от вида корней (одинаковые они или различные).

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