МАЛЫЙ МЕХМАТ МГУ

Кружок 9-11 классов

Руководители А. В. Антропов, М. А. Лимонов и А. Ю. Шапцев
2010/2011 учебный год

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

19 февраля 2011 года

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

1.
Выведите формулу общего члена и суммы первых n членов следующих последовательностей:
a)
(арифметическая прогрессия) xn+1 = xn + a;
b)
(геометрическая прогрессия) xn+1 = a · xn.
2.
Выведите формулу общего члена и суммы первых n членов следующей рекуррентной последовательности xn+1 = a · xn + b (такая последовательность называется арифметико-геометрической).
3.
Рассмотрим последовательность {rn}, удовлетворяющую соотношению rn+2 = 5 · rn+1 − 6 · rn (назовем это соотношение (1)).
a)
Докажите, что для любого числа α последовательность {α·rn} также удовлетворяет этому соотношению;
b)
Докажите, что если две последовательности {rn} и {sn} удовлетворяют (1), то и последовательность {rn + sn} ему также удовлетворяет;
c)
Найдите геометрическую прогрессию, удовлетворяющую соотношению (1). Сколько различных таких прогрессий?
d)
Используя результаты предыдущих пунктов этой задачи, напишите формулу с двумя произвольными параметрами c1 и c2, являющуюся формулой n-го члена для последовательностей, удовлетворяющих (1);
e)
Докажите, что ваша формула исчерпывает все последовательности, удовлетворяющие (1) (обратите внимание, что каждая такая последовательность однозначно задается своими двумя первыми членами).
4.
Проделайте аналогичные операции и найдите формулу n-го члена последовательности Фибоначчи: F1 = F2 = 1, Fn+2 = Fn+1 + xn.
5.
Полученная явная формула для чисел Фибоначчи называется формулой Бине. Не верится, что она задает целочисленную последовательность, но это так. Впрочем, если вспомнить про бином Ньютона, то это становится очевидным. Докажите целочисленность этой формулы при каждом натуральном n через бином Ньютона.
Напоминание: Под биномом Ньютона понимается следующая формула:
6.
На первой клетке полоски 1×n стоит шашка. За один ход разрешается передвинуть шашку вправо на одну или две клетки. Обозначим через fn число различных способов переместить шашку из первой клетки в n-ую. Найдите реккурентную зависимость fn от fn − 1 и fn − 2.
7.
Найдите сумму n чисел 1 + 11 + 111 + ... + 11...11.
8.
Сколькими способами можно разбить число N на слагаемые, каждое из которых равно одному из натуральных чисел 1, 2, 3, ..., n? Порядок слагаемых не важен.

26 февраля 2011 года

8.
Последовательность {an}, состоящая из натуральных чисел, такова, что a1 > a0 и an+1 = 3·an − 2·an−1. Докажите, что a100 ≥ 2100.
9.
Дана последовательность {xn}. Известно, что x1 = x2010 = 2010 и xn = −xn−1 + 2·xn−2. Докажите, что xn = 2010 для всякого n.
10.
Найдите количество способов раскрасить полоску 1×n в три цвета: красный, синий и зеленый — так, что за красным цветом не следует зеленый (но при этом может ему предшествовать).

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! Rambler's Top100
liveinternet.ru
Apache
PHP
HTML 4.01
CSS