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

Линейные рекуррентности

Последовательность определена рекуррентно: a(n) выражается через a(n−1), ..., a(n−k).

Числа Фибоначчи: F(n) = F(n−1) + F(n−2), F(0)=0, F(1)=1.

Характеристическое уравнение: x² = x + 1. Корни: φ = (1+√5)/2 (золотое сечение), ψ = (1−√5)/2.

Формула Бине: F(n) = (φⁿ − ψⁿ)/√5.

Общий метод

Для однородной линейной рекуррентности a(n) = c₁a(n−1) + ... + cₖa(n−k):

1. Характеристическое уравнение: xᵏ = c₁xᵏ⁻¹ + ... + cₖ.
2. Если корни x₁,...,xₖ различны: a(n) = α₁x₁ⁿ + ... + αₖxₖⁿ.
3. Коэффициенты из начальных условий.

При кратных корнях xᵢ кратности mᵢ: слагаемое xᵢⁿ·(α₀ + α₁n + ... + α_{mᵢ-1}nᵐⁱ⁻¹).

Мастер-теорема

Для T(n) = aT(n/b) + f(n) (рекуррентности «разделяй и властвуй»):

Если f(n) = O(n^{log_b a - ε}) → T(n) = Θ(n^{log_b a}). Если f(n) = Θ(n^{log_b a}) → T(n) = Θ(n^{log_b a} log n). Если f(n) = Ω(n^{log_b a + ε}) → T(n) = Θ(f(n)).

Применение: MergeSort T(n) = 2T(n/2) + Θ(n): a=2, b=2, log_b a = 1, f(n) = Θ(n) → T(n) = Θ(n log n).

Линейные рекуррентности с нечёткими корнями

Когда характеристическое уравнение имеет кратные корни, формула решения усложняется. Например, для a(n) = 4a(n−1) − 4a(n−2) характеристическое уравнение x² − 4x + 4 = (x−2)² = 0 имеет корень x=2 кратности 2. Решение: a(n) = (C₁ + C₂n)·2ⁿ. Общий принцип: корень rᵢ кратности mᵢ даёт слагаемые rᵢⁿ·p(n), где p — многочлен степени mᵢ−1.

Для неоднородных рекуррентностей a(n) = f(a(n−1),...) + g(n) используется метод вариации постоянных или подбора частного решения. Если g(n) = bⁿ·p(n), частное решение имеет вид bⁿ·q(n) (или nᵏ·bⁿ·q(n), если b — корень характеристического уравнения кратности k).

Рекуррентности и комбинаторные интерпретации

Числа Каталана: Cₙ = C(2n,n)/(n+1). Рекуррентность: C₀=1, Cₙ = Σₖ₌₀ⁿ⁻¹ CₖCₙ₋₁₋ₖ. Производящая функция: C(x) = (1−√(1−4x))/(2x). Числа Каталана считают: правильные скобочные последовательности, нетреугольные разбиения n-угольника, полные бинарные деревья, маршруты Дика.

Числа Стирлинга первого рода s(n,k) — число перестановок n элементов с ровно k циклами. Рекуррентность: s(n,k) = (n−1)·s(n−1,k) + s(n−1,k−1). Связь с производящими функциями: Σₖ s(n,k)xᵏ = x(x−1)...(x−n+1) (падающий факториал).

Мастер-теорема: граничные случаи и обобщения

Стандартная мастер-теорема не применима в точности к логарифмическим факторам. Обобщённая мастер-теорема (Акра-Бааз): Для T(n) = Σ aᵢT(n/bᵢ) + f(n): находим p из Σ aᵢ/bᵢᵖ = 1, тогда T(n) = Θ(nᵖ·(1 + ∫₁ⁿ f(t)/(tᵖ⁺¹)dt)). Это покрывает неравномерное деление.

Граничный случай: T(n) = 2T(n/2) + n·log n — второй случай мастер-теоремы с логарифмом: T(n) = Θ(n·log²n). Применяется в анализе алгоритмов сортировки слиянием с дополнительным логарифмическим множителем в слиянии.

Важные алгоритмы и их сложности через рекуррентности: Strassen (умножение матриц) T(n)=7T(n/2)+Θ(n²) → O(n^{log₂7}) ≈ O(n^{2.81}). Binary search T(n)=T(n/2)+O(1) → O(log n). Karatsuba (умножение чисел) T(n)=3T(n/2)+Θ(n) → O(n^{log₂3}) ≈ O(n^{1.585}).

Решение линейных рекуррентностей: алгебраический взгляд

Рассмотрим пространство последовательностей, удовлетворяющих рекуррентности Lₖ(aₙ) = 0 (гомогенный случай). Это линейное пространство, его базис — элементарные решения rⁿ и nʲrⁿ (при кратных корнях). Формально: оператор сдвига E: (aₙ) → (aₙ₊₁), тогда рекуррентность a(n) = c₁a(n−1) + ... + cₖa(n−k) записывается как (Eᵏ − c₁Eᵏ⁻¹ − ... − cₖ)aₙ = 0. Ядро этого оператора порождается базисными решениями.

Для системы рекуррентностей aₙ = M·aₙ₋₁ (где aₙ — вектор, M — матрица): aₙ = Mⁿ·a₀. Быстрое возведение в степень: Mⁿ за O(k³ log n) операций (k — размерность). Для чисел Фибоначчи: (Fₙ, Fₙ₋₁) = [[1,1],[1,0]]ⁿ · (F₁, F₀). Это даёт Fₙ за O(log n) умножений целых чисел.

Рекуррентности в анализе алгоритмов: тонкости

Рекуррентности динамического программирования имеют другую структуру. Задача о рюкзаке 0/1: dp[i][w] = max(dp[i−1][w], dp[i−1][w−wᵢ]+vᵢ). Время: O(nW), не полиномиальное по размеру входа (W может быть экспоненциально большим) — «псевдополиномиальный» алгоритм. Longest Common Subsequence: dp[i][j] = (если s[i]=t[j]): 1 + dp[i−1][j−1]; (иначе): max(dp[i−1][j], dp[i][j−1]). Решение за O(nm) — квадратичное.

Рекуррентности в разделяй-и-властвуй часто имеют полное решение через мастер-теорему, но рекуррентности ДП — через таблицу. Это разграничение важно: в разделяй-и-властвуй каждый подуровень обрабатывает непересекающиеся части, а в ДП подзадачи перекрываются — вот почему мемоизация/таблица ДП экономит время.

Динамическое программирование: вероятностные расширения

Вероятностная рекуррентность: Задача: E[минимальная стоимость] при случайных переходах → стохастическое ДП. Уравнение Беллмана для MDP: V*(s) = max_a {R(s,a) + γ·Σ P(s'|s,a)·V*(s')}. Решается итерацией значений (value iteration) или итерацией политик. В ДП на DAG: задача кратчайшего пути с вероятностными рёбрами — ожидаемая длина пути.

Перечислительная комбинаторика: принцип включений-исключений

|A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + ... + (−1)^{n+1}|A₁∩...∩Aₙ|. Применения: задача о беспорядках (derangements) D(n) = n!·Σ(−1)ᵏ/k! ≈ n!/e; число сюръекций n→m: Σ(−1)ᵏC(m,k)(m−k)ⁿ. Мобиусова функция на частично упорядоченных множествах — обобщение ВИИ.

Численный пример: решение линейной рекуррентности

Задача: Решить: aₙ=5aₙ₋₁−6aₙ₋₂ при a₀=0, a₁=1.

Шаг 1: Характеристическое уравнение: r²−5r+6=0. Дискриминант: 25−24=1. Корни: r₁=2, r₂=3.

Шаг 2: Общее решение: aₙ=C₁·2ⁿ+C₂·3ⁿ. Начальные условия: a₀=C₁+C₂=0 → C₂=−C₁. a₁=2C₁+3C₂=2C₁−3C₁=−C₁=1 → C₁=−1, C₂=1.

Шаг 3: Решение: aₙ=3ⁿ−2ⁿ. Проверки: a₂=9−4=5=5·1−6·0 ✓; a₃=27−8=19=5·5−6·1 ✓.

Шаг 4: ОПФ: A(x)=x/(1−5x+6x²)=x/((1−2x)(1−3x))=−1/(1−2x)+1/(1−3x) → aₙ=3ⁿ−2ⁿ ✓. Асимптотика: aₙ~3ⁿ (доминирует больший корень). Функция Мёбиуса удовлетворяет μ*1=ε (рекуррентность на делителях) — прямое обобщение ВИИ через формулу обращения Мёбиуса: если g(n)=Σ_{d|n}f(d), то f(n)=Σ_{d|n}μ(n/d)g(d).