Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/recurr.doc Дата изменения: Fri Oct 22 16:21:52 2004 Дата индексирования: Sat Dec 22 16:30:05 2007 Кодировка: koi8-r Поисковые слова: п п п п п п

ПОСЛЕДОВАТЕЛЬНОСТИ, ЗАДАННЫЕ РЕКУРРЕНТНО (П.В. Семенов, для школы в
«Менделеево», 20 октября)
Один из способов задать числовую последовательность таков: надо
указать, чему равны несколько первых, подряд идущих членов
последовательности, а затем рассказать, как каждый последующий член
последовательности получается из предыдущих членов. Первая и основная
проблема при таком рекуррентном задании последовательности состоит в том,
чтобы найти явную формулу, которая позволит найти [pic]й член
последовательности [pic] по его номеру [pic]. Некоторые простейшие случаи
известны по школьному курсу «Алгебра 9».
Пример 1. [pic]. Если [pic], то [pic]- арифметическая прогрессия.
Пример 2. [pic]. Если[pic], то [pic]- геометрическая прогрессия.
Пример 3. (Рекуррентность 2-го порядка)[pic], [pic], [pic]. Найти
[pic]? Получаются числа Фибоначчи, а ответ (формула Бине) достаточно
сложен.
Задача 1. Найти [pic], если известно, что: а) [pic];
б)[pic]; в)[pic].
(После решения: самое главное - решить уравнение [pic], т.е. найти
неподвижную точку.)
Задача 2. Над цепью озер летела цепь гусей. На первом озере села половина
всех гусей и еще полгуся. На втором села половина пролетевших и еще
полгуся. И так далее. На семи озерах сели все гуси. Сколько гусей летело?
Решение. К [pic]-ному озеру подлетело [pic] гусей. Тогда [pic]. Так как
[pic], то [pic]. Откуда [pic]. Ответ: 127.
Мы займемся рекуррентностями 1-го порядка, которые заданы не
линейными, как в задаче 1, но дробно-линейными функциями. Итак, вот
основная задача.
|Известно, что [pic] и [pic]. Выразить [pic] через [pic] и [pic]. |

Задача 3. (вспомогательная) а) Дробно-линейная функция[pic]однозначно
задается своими значениями в трех любых точках. б) Дробно-линейная функция
[pic] сохраняет сложное отношение четырех точек [pic]. (Определение:
[pic]). в) Наоборот, если [pic]сохраняет сложное отношение четырех точек,
то [pic] дробно-линейна. г) Неподвижные точки [pic]?
Рассмотрим конкретный пример.
Задача 4. Дано, что [pic]. а) Что получится, если [pic] или [pic]? б)
Пусть [pic]. Тогда [pic] возрастает и стремится к [pic]. в) Пусть [pic].
Тогда [pic] убывает и стремится к [pic]. г) Пусть [pic]. Тогда [pic] не
монотонна, но все равно стремится к [pic]. (Можно и по графику)
Задача 5 (продолжение 3). а) Сравнить [pic] и [pic]. б) Сравнить [pic]
и [pic]. в) Вычислить сложное отношение [pic]. г) Вывести формулу n -го
члена (=выразить [pic] через [pic] и [pic].) д) Найти [pic].
Задача 6. а) Выразить [pic] через [pic], если [pic] и [pic]. б) Найти
[pic].
Определение. Уравнение [pic] называется характеристическим.
Задача 7. Пусть [pic] и [pic] - корни характеристического уравнения. а)
Сравнить [pic] и [pic]. б) Сравнить
[pic] и [pic]. в) Вычислить сложное отношение [pic]. г) Вывести формулу n
-го члена (=выразить [pic] через [pic] и [pic].)
Неприятность состоит в том, что корни характеристического уравнения
могут быть комплексными. Впрочем, тогда сложное отношение вычисляется в
комплексных числах. Удивительно, но ответ все равно получится
действительным(?). По этой причине дробно-линейной рекуррентности иногда
приводят к периодическим последовательностям.
Задача 8. Пусть [pic] и [pic] а) Вывести формулу n -го члена. б)
Доказать периодичность этой последовательности. в) Докажите, что дробно-
линейная рекуррентность периодична, если корни характеристического
уравнения являются корнями из единицы.

Иногда дробно-линейные рекуррентности можно свести к арифметико-
геометрическим прогрессиям, см. задача 1.
Задача 9. а) Для рекуррентности [pic] вывести формулу [pic]го члена,
перейдя к последовательности [pic]. б). Найти формулу [pic]ного члена
последовательности, заданной рекуррентно: [pic]. (Ответ [pic])
Задача 10 (отклонение от дробно-линейности, но идея - переход к обратному).
Найти формулу n-ного члена последовательности, в которой каждый член,
начиная со второго равен среднему гармоническому двух предыдущих членов и
[pic], [pic]. (Ответ [pic] )
Задача 11 . Всесоюзная олимп. (1985)
|Решите уравнение | Прибавив к обеим частям уравнения 2, получим, что |
|[pic]. |левая часть будет записана в виде рекуррентного |
| |соотношения вида [pic] с начальным условием [pic]. |
| |Характеристическое уравнение [pic], одним из корней |
| |будет [pic]. Следовательно, данная последовательность |
| |постоянна. Поэтому, получим уравнение [pic]. Откуда |
| |[pic]. |

Задача 12. Найти общее сопротивления электрической цепи, составленной из
[pic] одинаковых участков, расположенных так, как показано на рисунке
(сопротивление каждого резистора [pic]): [pic]Для сопротивления [pic]цепи:
[pic] и [pic]. Если [pic], то [pic], где [pic]числа Фибоначчи. В
частности, [pic].