Числовая последовательность задана рекуррентным способом

Числовая последовательность

п.1. Формулы числовых последовательностей

Запишем несколько первых чётных чисел и пронумеруем их:

Этот ряд бесконечен, но, глядя на таблицу, его легко задать формулой: \begin \mathrm> \end

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

Для обозначения членов последовательности и их индексов можно использовать разные буквы: x₁, x₂, . x_m. ; a₁, a₂, . a_k. ; A₁, A₂, . A_s. и т.д.

Например:
Найти 1й, 3й и 4й члены последовательности, заданной формулой \(\mathrm>\) $$ \mathrm< y_1=\frac<1-1><1+1>=0,\ \ y_3=\frac<3-1><3+1>=\frac12,\ \ y_4=\frac<4-1><4+1>=\frac35 > $$

п.2. Задание последовательностей описанием

Последовательность, заданную формулой y_n=2n, можно задать описанием как «последовательность чётных чисел».

Последовательность, заданную формулой \(\mathrm>\), можно задать описанием как «последовательность дробей, числитель которых на 1 меньше индекса, а знаменатель на 1 больше индекса последовательности».

Кроме того, существуют такие последовательности, которые можно задать только описанием.

Например:
1. Последовательность простых чисел:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …

2. Последовательность десятичных приближений числа \(\mathrm<\sqrt<3>>\) по недостатку:

1; 1,7; 1,73; 1,732; 1,7320; 1,73205; 1,7302050; 1,73020508,…

п.3. Рекуррентные формулы числовых последовательностей

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

Например:
Найти y₅, если y₁ = 1, y_n = 2y_n-1 + 1
Проводим последовательные вычисления:
y₂ = 2y₁ + 1 = 3, y₃ = 2y₂ + 1 = 7, y₄ = 2y₃ + 1 = 15, y₅ = 2y₄ + 1 = 31
Интересно, что, если присмотреться, эту последовательность можно также задать аналитически: y_n = 2 n – 1.

п.4. Свойства числовых последовательностей

Например:
Последовательность квадратов натуральных чисел y_n = n 2 возрастающая:

Например:
Последовательность дробей с индексом в знаменателе \(\mathrm\) – убывающая: $$ 1\gt\frac12\gt\frac13\gt. \gt\frac1n\gt. $$

Например:
Последовательность отрицательных дробей с индексом в знаменателе \(\mathrm\) ограничена сверху числом M = 0: $$ -1\lt 0,\ \ -\frac12\lt 0,\ \ -\frac13\lt 0. \ \ -\frac1n\lt 0, . $$

Например:
Последовательность дробей с индексом в знаменателе \(\mathrm\) ограничена снизу числом M = 0: $$ -1\gt 0,\ \ \frac12\gt 0,\ \ \frac13\gt 0. \ \ \frac1n\gt 0, . $$

Например:
Последовательность дробей с индексом в знаменателе \(\mathrm\) ограничена: $$ 1\gt \frac12\gt \frac13\gt . \gt \frac1n\gt . \gt 0 $$ Верхней границей является M = 1, нижней границей K = 0.

п.5. Примеры

Пример 1. Найдите первые 4 члена последовательности, заданной формулой
a) \(\mathrm<2n-1>>\)

Пример 2. Найдите первые 4 члена последовательности, заданной рекуррентной формулой
a) y₁ = 3, y_n = 3y_n – 1

Пример 3*. Укажите какую-либо формулу для n-го члена числовой последовательности

а) 3, 5, 7, 9, .
Это – последовательность нечётных чисел, для которой:
y_n = 2n + 1

б) 5, -5, 5, -5.
Это – знакопеременная последовательность, для которой модуль всегда равен 5, а знак меняется. Изменение знака можно записать как степень (–1). Учитывая, что нечётные члены последовательности положительные, а чётные – отрицательные, получаем:
y_n = (–1) n+1 · 5

в) \(\mathrm<\frac<1><1\cdot 2>,\ \ \frac<1><2\cdot 3>,\ \ \frac<1><3\cdot 4>. >\)
Это – последовательность дробей, у которых в знаменателе произведение текущего индекса n на следующий индекс (n + 1):
\(\mathrm>\)

г) 2, 5, 10, 17, 26, 37, .
Заметим, что

5 — 2 = 3, 10 — 5 = 5, 17 — 10 = 7, 26 — 17 = 9, .

Каждый последующий член отличается от предыдущего на возрастающее нечётное число. Можем записать рекуррентную формулу:
y₁ = 2, y_n = y_n-1 + (2n –1)

Пример 4*. Пифагор изучал последовательность «треугольных» чисел, которые можно задать следующими геометрическими фигурами:

и т.д.
Задайте эту последовательность 1) рекуррентной формулой; 2) аналитической формулой.

1) Запишем последовательность в явном виде, как это следует из чертежа: $$ \mathrm< y_1=1,\ \ y_2=\underbrace<1>_+2=3,\ \ y_3=\underbrace<1+2>_+3=6,\ \ y_4=\underbrace<1+2+3>_+4=10 > $$ Отсюда получаем следующую рекуррентную формулу: y₁ = 1, y_n = y_n-1 + n

2) Для произвольного члена последовательности:

y_n = 1 + 2 + 3 + . + (n — 2) + (n — 1) + n

Найдём эту сумму. Для этого запишем выражение наоборот:

y_n = n + (n — 1) + (n — 2) + . + 3 + 2 + 1

Источник

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

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

Как решать рекуррентные соотношения?

Для решения рекуррентных соотношений применяют один из двух основных способов:

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

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

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

1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен $k$) $$a_ <0>= …, \\ a_ <1>= …, \\ a_ = …, \\ … \\ a_ = …, n\geqslant k$$
2. Домножить каждую строчку на $z$ в соответствующей степени $z^ \cdot a_$ и сложить все выражения для $n \ge 0$. В левой части получится сумма $\displaystyle\sum_^ <\infty>a_nz^n$ — это производящая функция, назовем ее $G(z)$. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее $G(z)$.
3. Решить полученное уравнение относительно $G(z)$.
4. Разложить $G(z)$ в степенной ряд, тогда коэффициент при $z_n$ будет искомым выражением для $a_n$.

Метод характеристических функций

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

1. Записать соответствующее однородное рекуррентное уравнение (РУ): $$ p_ a_ + p_a_ + . + p_n a_n =f \to \\ \to p_ a_ + p_a_ + . + p_n a_n =0. $$
2. Выписать для него характеристическое уравнение и найти его корни $\lambda_i$ $$ p_ \lambda^ + p_\lambda^ + . + p_\lambda + p_n =0. $$
3. Выписать согласно полученным корням $\lambda_1, . \lambda_k$ общее решение однородного рекуррентного соотношения (подробнее теорию см. по ссылке [1] ниже). $$ C_1 \lambda_1^n +. +C_k \lambda_k^n \, \mbox < для случая различных простых корней>, $$ $$ C_1 \lambda_1^n + C_2 n\lambda_1^n +. +C_m n^m \lambda_1^n+. +C_k \lambda_k^n \mbox < для случая корня >\, \lambda_1 \, < кратности >\, m. $$
4. Подобрать частное решение неоднородного рекуррентного соотношения по виду правой части (особенно удобно для правых частей вида $\mu^n*P(n)$, $P(n)$ — многочлен от $n$).
5. Представить общее решение неоднородного РУ как сумму общего решения соответствующего однородного РУ и частного решения неоднородного РУ.
6. Подставить начальные условия $a_0, a_1, . a_$ и получить значения констант $C_1, . C_k$.

Решение для последовательности чисел Фибоначчи

Последовательность чисел Фибоначи — это последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:

$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 , . $$

Числа Фибоначчи растут быстро: $f_<10>=55$, $f_<20>=6765$, а $f_<100>=354224848179261915075$.

Общая формула данной рекуррентной последовательности имеет вид6

Способ 1. Производящяя функция

Начинаем с второго шага алгоритма, домножаем на $z^n$:

$$\begin 1\cdot f_0 &= &0\cdot 1,\\ z\cdot f_1 &= &1\cdot z,\\ z\cdot f_n & = &(f_+f_)\cdot z^n, \quad n\geq2.\\ \end $$

Складываем все строчки:

На третьем шаге алгоритма приводим все суммы к замкнутому виду:

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

Теперь разложим ее в степенной ряд. Для этого сначала разложим знаменатель на множители. Найдем корни уравнения:

Чтобы разложить данные дроби в ряды, используем известное разложение для дроби:

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на $z_1$:

Аналогично (но с делением на $z_2$) действуем со второй дробью:

Преобразуем данное выражение, используя то, что

$$1/z_1=-z_2, \quad 1/z_2 = -z_1, \quad z_1-z_2=\sqrt <5>$$ $$f_n=\frac<1><\sqrt<5>>\left( \biggl( \frac<1+\sqrt<5>> <2>\biggr)^n — \biggl( \frac<1-\sqrt<5>> <2>\biggr)^n \right). $$

Способ 2. Характеристическое уравнение

Запишем характеристический многочлен для $f_n=f_+f_$, и найдем его корни:

Тогда общее решение однородного рекуррентного уравнения имеет вид:

Осталось найти значения произвольных постоянных $C_1, C_2$ из начальных условий $f_0=0, f_1=1$.

Решая систему, найдем

Итоговое выражение для последовательности чисел Фибоначчи:

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

Примеры решений

Задача 1. Решить рекуррентное соотношение $f(n+2)=-6f(n+1)+7f(n)+n-3$ с начальными условиями $f(0)=2$ и $f(1)=4$, сделать проверку

Задача 2. Решить рекуррентное соотношение $f(n+2)=-2f(n+1)+3f(n)-3^n$ с начальными условиями $f(0)=1$, $f(1)=3$ и сделать проверку

Задача 3. 1. Решить рекуррентное соотношение $f(n+2) =-5f(n+1) -4f(n) + 3n^2$ с начальными условиями $f(0) = 2$, $f(1) = 3$.
2. Проверить, удовлетворяет ли найденное решение начальным условиям и обращает ли оно рекуррентное соотношение в справедливое тождество.

Задача 4. Найти последовательность $$, удовлетворяющую рекуррентному соотношению $a_ + 4 a_ + 3 a_ = 0$ и начальным условиям $a_1=2$, $a_2=4$.

Источник

Конспект урока «Рекуррентное задание числовых последовательностей» (9 класс)

Выбранный для просмотра документ Открытый урок Рекуррентное задание числовой последовательности.docx

ТЕМА: Рекуррентное задание числовых последовательностей

Цель урока : познакомить учащихся с рекуррентным способом задания числовой последовательности на примере чисел Фибоначчи и разобрать задачи на преобразование одного задания последовательности в другое.

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

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

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

Учебник, компьютер (проектор).

Учащиеся получат представление рекуррентных соотношениях.

Узнают о способе перехода от аналитического задания к рекуррентному.

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

Проверка домашнего задания.

Актуализация темы «Способы задания функции»

Изучение нового материала (работа с презентацией).

Определение рекуррентного соотношения.

Различия аналитического и рекуррентного способа задания.

Определение последовательности Фибоначчи

Онтологическая интерпретация чисел Фибоначчи.

Свойства последовательности Фибоначчи.

Решение заданий из учебника

Приветствие, проверка присутствующих. Объявление темы урока, объяснение хода урока.

2. Проверка домашнего задания: № 16.6, 15.41.

3. Актуализация темы «Способы задания функции»

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

4. Изложение нового материала.

1. Определение рекуррентного соотношения

Опр. ( презентация ) Говорят, что последовательность задана рекуррентным соотношением, если указана формула, в одной части которой находится только n — ый член последовательности, а в другой — буквенное выражение, содержащее предыдущие члены последовательности, в котором аргумент не участвует в вычислениях значения функции.

2. Различия аналитического и рекуррентного способа задания .

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

3. Определение последовательности Фибоначчи

Опр. ( презентация ) Последовательностью Фибоначчи называется числовая последовательность, у которой заданы изначально первый и второй члены, а n — ый член вычисляется как сумма ( n —1)- го и ( n —2)- го членов.

4. Онтологическая интерпретация чисел Фибоначчи.

На Западе впервые эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Liber Abaci» (1202). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, предполагая что: изначально есть новорожденная пара кроликов (самец и самка), со второго месяца после своего рождения кролики начинают спариваться и каждый месяц производить новую пару кроликов, кролики никогда не умирают. Сколько пар кроликов будет через год? ( презентация )

В начале первого месяца есть только одна новорожденная пара (1).

В конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся (1)

В конце второго месяца первая пара рождает новую пару и опять спаривается (2)

В конце третьего месяца первая пара рождает еще одну новую пару и спаривается, вторая пара только спаривается (3)

В конце четвертого месяца первая пара рождает еще одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается (5)

5. Свойства последовательности Фибоначчи .

Если числа Фибоначчи заданы следующим образом:

тогда справедливы следующие свойства ( презентация ):

5. Решение заданий из учебника

Решение учителем № 15.37, 15.31, 15.20 (а, б), 15.32, 15.21.

Решение учащимися № 15.37, 15.31, 15.20, 15.32, 15.21 (а, б).

Заключительный опрос по изученному материалу:

1) Приведите примеры рекуррентного соотношения

2) Приведите пример последовательности Фибоначчи

3) Запишите рекуррентно арифметическую прогрессию

Источник