Как из квадратного уравнения получить рекуррентную последовательность

Представим, что у нас есть квадратное уравнение:
x² — p x — q = 0.
Как из него можно получить рекуррентное соотношение?

Связь между корнями уравнения и рекуррентной последовательностью

Любая линейная рекуррентная последовательность второго порядка задаётся уравнением:
Aₙ₊₂ = p Aₙ₊₁ + q Aₙ.

Если мы предположим, что последовательность Aₙ имеет вид:
Aₙ = αⁿ,
где α — некоторое число, то подставляя это в рекуррентное уравнение, получаем:
αⁿ⁺² = p αⁿ⁺¹ + q αⁿ.

Разделим обе части на αⁿ (при α ≠ 0):
α² = p α + q.

Это и есть характеристическое уравнение последовательности!

Пример: строим рекуррентную последовательность из уравнения

Допустим, нам дано уравнение:
x² — 8x + 5 = 0.

Его корни:
α = 4 + √11, β = 4 — √11.

Мы знаем, что числа 4 + √11 и 4 — √11 являются корнями характеристического уравнения. Значит, последовательность вида:
Aₙ = c₁ αⁿ + c₂ βⁿ
удовлетворяет рекуррентному соотношению:
Aₙ₊₂ = 8 Aₙ₊₁ — 5 Aₙ.

Почему рекуррентная последовательность строится именно так?

✅ Если у нас есть два независимых решения αⁿ и βⁿ, то их линейная комбинация (c₁ αⁿ + c₂ βⁿ) будет также решением.
✅ Любая последовательность, удовлетворяющая линейной рекуррентности, можно выразить через такие корни.
✅ Мы получаем формулу для нахождения любого члена последовательности без необходимости считать все предыдущие!

Итог

📌 Чтобы получить рекуррентное уравнение, нужно взять квадратное уравнение, заменить x на Aₙ₊₂ / Aₙ, и выразить Aₙ₊₂ через Aₙ₊₁ и Aₙ.
📌 Корни этого уравнения дают нам экспоненциальные решения, а их линейная комбинация описывает общую последовательность.

Вот так алгебра и последовательности связаны!