Первого порядка. Соотношение x₍n + 1) = qx_n + d (q ≠ 0) называется линейным рекуррентным соотношением первого порядка; при q = 1 это арифметическая прогрессия, при d = 0 — геометрическая, в общем случае последовательность называют арифметико-геометрической прогрессией. Пример: 1; 5; 13; 29; … — x₍n + 1) = 2x_n + 3.
Общий член. Возьмём y_n = x_n + α и подберём α так, чтобы (y_n) была геометрической прогрессией: y₍n + 1) = qy_n + α(1 - q) + d, нужно α = d/(q - 1) (q ≠ 1). Тогда x_n + α = (x₁ + α)q⁽n - 1), то есть
x_n = (x₁ + d/(q - 1))q⁽n - 1) - d/(q - 1).
Пример: x₍n + 1) = -3x_n + 1, x₁ = 5: α = -1/4, x_n = 19/4(-3)⁽n - 1) + 1/4.
Второго порядка. x₍n + 2) = px₍n + 1) + qx_n. Ищем решения вида λⁿ: λ² - pλ - q = 0 — характеристическое уравнение. Если у него два различных корня λ₁, λ₂, то x_n = C₁λ₁ⁿ + C₂λ₂ⁿ, а C₁, C₂ находят из x₁ и x₂. Так получается формула Бине для чисел Фибоначчи: F_n = 1/√5(((1 + √5)/2)ⁿ - ((1 - √5)/2)ⁿ).