Определение возвратной последовательности

Возвратные последовательности

 

Выполнила студентка 4 курса

математического факультета, гр. 405

Волисова Елена Валерьевна

Руководитель:

кандидат физ.-мат. наук, доцент

Баркович Оксана Аркадьевна

 

Минск 2009

Содержание

Введение

Глава 1 (теоретическая часть)

§ 1. Определение возвратной последовательности

§ 2. Обобщение произвольных возвратных последовательностей

§ 3. Изучение и применение возвратных последовательностей в курсе средней школы

§ 4. Формулы вычисления любого члена возвратной последовательности. Базис возвратного уравнения

§ 5. Характеристическое уравнение для возвратного уравнения

§ 6. Возвратные задачи

Глава 2 (практическая часть)

Заключение

Список литературы

 

Введение

 

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

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

Таким образом, возвратные последовательности являются настоящей маленькой теорией, законченной, простой, ясной.

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

В данной курсовой работе также рассмотрены возвратные задачи. В основе решения возвратных задач лежит идея возвратности (или рекуррентности), согласно которой решение всей задачи зависит от решения той же самой задачи меньших размеров.

Глава 1 (теоретическая часть)

Определение возвратной последовательности

 

Будем записывать последовательности в виде

 

u₁, u₂, u₃,..., u_n,..., (1)

 

или, коротко, {u_n}. Если существует натуральное число k и числа a₁, a₂, …, a_k (действительные или мнимые), такие, что, начиная с некоторого номера n и для всех следующих номеров,

 

u_{n + k} == a₁u_{n +k – 1} + a₂u_{n + k – 2} + … + a_ku_n (n m 1), (2)

 

то последовательность (1) называется возвратной последовательностью порядка k, а соотношение (2) – возвратным уравнением порядка k.

Таким образом, возвратная последовательность характеризуется тем, что каждый её член (начиная с некоторого из них) выражается через одно и то же количество k непосредственно предшествующих ему членов по формуле (2).

Само название «возвратная» (а также рекуррентная, от французского recurrente – возвращающаяся к началу) употребляется именно потому, что здесь для вычисления последующего члена возвращаются к предшествующим членам.

Пример 1. Геометрическая прогрессия. Пусть имеем геометрическую прогрессию:

 

u₁ = a, u₂ = aq, u₃ = aq²,..., u_n = aq^{n – 1},..., (3)

 

для неё уравнение (2) принимает вид:

 

u_{n + 1} = qu_n. (4)

 

Здесь k = 1 и a₁ = q. Таким образом, геометрическая прогрессия является возвратной последовательностью первого порядка.

Пример 2. Арифметическая прогрессия. В случае арифметической прогрессии

 

u₁ = a, u₂ = a + d, u₃ = a + 2d,..., u_n = a + (n - 1)d,...,

имеем: u_{n + 1} = u_n + d

 

- соотношение, не имеющее вида уравнения (2). Но если рассмотреть два соотношения, написанные для двух соседних значений n:

 

u_{n + 2} = u_{n + 1} + d и u_{n + 1} = u_n + d,

 

то получим из них, путём почленного вычитания:

 

u_{n + 2} - u_{n + 1} = u_{n + 1} - u_n,

или u_{n + 2}= 2u_{n + 1} - u_n (5)

 

- уравнение вида (2). Здесь k = 2, a₁ = 2, a₂ = -1. Следовательно, арифметическая прогрессия является возвратной последовательностью второго порядка.

Пример 3. Рассмотрим старинную задачу Фибоначчи о числе кроликов. В ней требуется определить число пар зрелых кроликов, образовавшихся от одной пары в течение года, если известно, что каждая зрелая пара кроликов ежемесячно рождает новую пару, причём новорождённые достигают половой зрелости в течение месяца. В этой задаче интересен не результат, а последовательность, члены которой выражают общее число зрелых пар кроликов в начальный момент (u₁), через месяц (u₂), через два месяца (u₃), и через n месяцев (u_n+1). Очевидно, что u₁ = 1. Через месяц прибавится пара новорождённых, но число зрелых пар будет прежнее: u₂ = 1. Через два месяца крольчата достигнут зрелости, и общее число зрелых пар будет равно двум: u₃ = 2.

Пусть вычислили уже количество зрелых пар через n – 1 месяцев – u_n и через n месяцев - u_n+1. Так как к этому времени u_n ранее имевшихся зрелых пар дадут ещё u_n пар приплода, то через n + 1 месяцев общее число зрелых пар будет:

 

u_n+2 = u_n+1 + u_n . (6)

Отсюда u₄ = u₃ + u₂ =3, u₅ = u₄ + u₃ = 5, u₆ = u₅ + u₄ = 8, u₇ = u₆ + u₅ = 13,...

 

Таким образом, получили последовательность

 

u₁ = 1, u₂ = 1, u₃ = 2, u₄ = 3, u₅ = 5, u₆ = 8, u₇ = 13,..., (7)

 

в которой каждый последующий член равен сумме двух предыдущих. Эта последовательность называется последовательностью Фибоначчи, а её члены – числами Фибоначчи.

Пример 4. Рассмотрим последовательность квадратов натуральных чисел:

 

u₁ = 1², u₂ = 2², u₃ = 3²,..., u_n = n²,... (8)

Здесь u_{n + 1} = (n + 1)² = n² + 2n + 1 и, следовательно,

u_{n + 1} = u_n + 2n + 1. (9)

 

Увеличивая n на единицу, получим:

 

u_{n + 2} = u_{n + 1} + 2n + 3. (10)

 

Вычитая почленно (9) из (10), получим:

 

u_{n + 2} - u_{n + 1} = u_{n + 1} - u_n + 2, или u_{n + 2} = 2u_{n + 1} - u_n + 2. (11)

 

Увеличивая в равенстве (11) n на единицу, будем иметь:

 

u_{n + 3} = 2u_{n + 2} - u_{n + 1} + 2, (12)

 

откуда (вычитая почленно (11) из (12))

 

u_{n + 3} - u_{n + 2} = 2u_{n + 2} - 2u_{n + 1} + u_n,

или u_{n + 3} = 3u_{n + 2} - 3u_{n + 1} + u_n . (13)

 

Получили возвратное уравнение третьего порядка. Следовательно, последовательность (8) есть возвратная последовательность третьего порядка.

Пример 5. К возвратным относятся все периодические последовательности. Рассмотрим последовательность цифр десятичного разложения числа

 

= 0,57132132132…

Здесь u₁ = 5, u₂ = 7, u₃ = 1, u₄ = 3, u₅ = 2, u₆ = 1, u₇ = 3,..., (14)

Очевидно, что u_{n + 3} = u_n (n ≥ 3). (15)

 

Чтобы представить это уравнение в виде (2), перепишем его следующим образом:

 

u_{n + 3} = 0•u_{n + 2} + 0•u_{n + 1} + 1•u_n.

 

Отсюда видно, что это возвратное уравнение третьего порядка (k = 1, a₁ = 0, a₂ = 0, a₃ = 0). Значит последовательность (14) является возвратной последовательностью третьего порядка.

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

 

P (x) = A₀ + A₁x +... + A_lx^l

Q (x) = B₀ + B₁x +... + B_kx^k (B₀ ≠ 0).

 

Будем делить P (x) на Q (x). Если P (x) не делится на Q (x) без остатка, то деление можно продолжать неограниченно. В частном один за другим будут получаться члены:

 

D₀ + D₁x + D₂x² + D₃x³ +... + D_nxⁿ +...

 

Рассмотрим последовательность

 

u₁ = D₀, u₂ = D₁,..., u_n = D_{n - 1},... (16)

 

и докажем, что она является возвратной порядка k (k – степень делителя). Фиксируем произвольное натуральное число n, удовлетворяющее единственному условию n ≥ l – k + 1, и остановимся в процессе деления на члене частного, содержащем x^{n + k} . Тогда в остатке получится некоторый многочлен R (x), содержащий x в степенях выше, чем n + k. Записывая соотношение между делимым, делителем, частным и остатком, получим следующее тождество:

 

A₀+A₁x+…+A_lx^l=(B₀+B₁x+...+B_kx^k)•(D₀+D₁x+D₂x²+D₃x³+...+D_n+kx^n+k)+R(x)

 

Найдём коэффициенты при x^{n + k} в левой и правой частях этого тождества и приравняем их между собой. Так как n + k ≥ l + 1, то коэффициент при x^{n + k} в левой части равен нулю. Поэтому должен равняться нулю и коэффициент при x^{n + k} в правой части. Но члены с x^{n + k} содержатся здесь только в произведении

 

(B₀ + B₁x +... + B_kx^k ) • (D₀ + D₁x + D₂x² + D₃x³ +... + D_{n + k}x^{n + k} )

 

(остаток R (x) содержит x в более высоких степенях). Поэтому искомый коэффициент есть

 

D_{n + k}B₀ + D_{n + k - 1}B₁ +... + D_nB_k. (17)

 

По предыдущему он должен равняться нулю:

 

D_{n + k}B₀ + D_{n + k - 1}B₁ +... + D_nB_k = 0, откуда (B₀ ≠ 0)

D_{n + k} = - D_{n + k – 1} -... - D_n (n ≥ l – k + 1). (18)

 

Это возвратное уравнение порядка k, откуда следует. Что последовательность (16) есть возвратная последовательность порядка k.