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

  • 5 мин чтения
  • Послушать — 3 мин
  • 13 карточек

Алгебра, 9 класс · Л. Г. Петерсон, Н. Х. Агаханов, А. Ю. Петрович, О. К. Подлипский, М. В. Рогатова, Б. В. Трушин

Первого порядка. Соотношение 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)ⁿ).

Определение

1 / 13

Соотношение первого порядка

x₍n + 1) = qx_n + d (q ≠ 0)

— линейное рекуррентное соотношение первого порядка.

q = 1 — арифметическая прогрессия, d = 0 — геометрическая; в общем случае — арифметико-геометрическая прогрессия.

Проверь себя

2 / 13

Пятый член

1; 5; 13; 29; … — x₍n + 1) = 2x_n + 3

Чему равен x₅?

613229
Ответ и объяснение

x₅ = 2 · 29 + 3 = 61.

Правило

3 / 13

Сдвиг к геометрической

Возьмём y_n = x_n + α и подберём α так, чтобы (y_n) была геометрической прогрессией:

y₍n + 1) = qy_n + α(1 - q) + d.

Нужно α(1 - q) + d = 0:

α = d/(q - 1) (q ≠ 1)

Формула

4 / 13

Общий член

x_n + α = (x₁ + α)q⁽n - 1)

где α = d/(q - 1), то есть

x_n = (x₁ + d/(q - 1))q⁽n - 1) - d/(q - 1).

Разбор

5 / 13

Разбор примера

Найди общий член:

x₍n + 1) = -3x_n + 1, x₁ = 5

  1. Сдвиг

    α = 1/(-3 - 1) = -1/4.

  2. Прогрессия

    x_n - 1/4 = (5 - 1/4)(-3)⁽n - 1).

  3. Ответ

    x_n = 19/4(-3)⁽n - 1) + 1/4.

Проверь себя

6 / 13

Подбери сдвиг

x₍n + 1) = 3x_n - 4

Чему равно α?

-22-4/3
Ответ и объяснение

α = (-4)/(3 - 1) = -2: x_n - 2 — геометрическая прогрессия.

Частая ошибка

7 / 13

Когда q = 1

x₍n + 1) = x_n + 2: «α = 2/(1 - 1)». Неверно! — деление на нуль.

При q = 1 это арифметическая прогрессия: x_n = x₁ + 2(n - 1).

Проверка при x₁ = 1: 1; 3; 5 и 1 + 2 · 2 = 5.

Определение

8 / 13

Второго порядка

x₍n + 2) = px₍n + 1) + qx_n

Ищем решения вида λⁿ: λ⁽n + 2) = pλ⁽n + 1) + qλⁿ, то есть

λ² - pλ - q = 0 — характеристическое уравнение.

Проверь себя

9 / 13

Характеристическое уравнение

x₍n + 2) = x₍n + 1) + 2x_n

Уравнение … = 0:

λ² + λ + 2λ² - λ - 2λ² - 2λ - 1
Ответ и объяснение

p = 1, q = 2: λ² - λ - 2 = 0, корни 2 и -1.

Правило

10 / 13

Два различных корня

Если λ₁ ≠ λ₂ — корни характеристического уравнения, то

x_n = C₁λ₁ⁿ + C₂λ₂ⁿ

C₁ и C₂ находят из x₁ и x₂.

Разбор

11 / 13

Второй порядок

Найди общий член:

x₍n + 2) = x₍n + 1) + 6x_n

x₁ = 1, x₂ = 13.

  1. Корни

    λ² - λ - 6 = 0: λ₁ = 3, λ₂ = -2.

  2. Система

    x_n = C₁ · 3ⁿ + C₂(-2)ⁿ: 3C₁ - 2C₂ = 1, 9C₁ + 4C₂ = 13.

  3. Ответ

    C₁ = C₂ = 1: x_n = 3ⁿ + (-2)ⁿ.

Пример

12 / 13

Формула Бине

Фибоначчи: x₍n + 2) = x₍n + 1) + x_n, λ² - λ - 1 = 0, λ₁,2 = (1 ± √5)/2.

F_n = (λ₁ⁿ - λ₂ⁿ)/√5

F₁ = √5/√5 = 1.

Главное

13 / 13

Главное

  • x₍n + 1) = qx_n + d, q ≠ 1: x_n + α = (x₁ + α)q⁽n - 1), α = d/(q - 1).
  • q = 1 — арифметическая, d = 0 — геометрическая.
  • x₍n + 2) = px₍n + 1) + qx_n: λ² - pλ - q = 0.
  • x_n = C₁λ₁ⁿ + C₂λ₂ⁿ; C₁, C₂ — из x₁, x₂.

Проверь себя: тест по теме

Несколько заданий по этой теме из того же учебника. Каждый ответ проверяется сразу, а начать можно без регистрации.

  • Задания из этого учебника
  • Ответ проверяется сразу
  • Без регистрации
Начать тест