Как решить рекуррентное уравнение

Перед тем, как найти формулу некоторой математической последовательности, необходимо найти n-ый член этой последовательности, выраженный через предыдущие члены последовательности (а не как функция от n). Например, было бы неплохо знать функцию для n-го члена последовательности Фибоначчи, но зачастую у вас есть только рекуррентное уравнение, связывающее каждый член последовательности Фибоначчи с двумя предыдущими членами. Эта статья расскажет вам, как решить рекуррентное уравнение.

Метод 1

Метод 1 из 5:

Арифметическая прогрессия

Загрузить PDF

Каждый член этой последовательности больше предыдущего члена на 3, поэтому он может быть выражен рекуррентным уравнением, показанным на рисунке.
Рекуррентное уравнение вида a_n = a_n-1 + d является арифметической прогрессией.
Запишите формулу для вычисления n-го члена арифметической прогрессии, как показано на рисунке.
В нашем примере 5 - это 0-й член последовательности. Тогда формула имеет вид a_n = 5 + 3n. Если 5 - это 1-й член последовательности, то формула имеет вид a_n =2 + 3n.
Реклама

Метод 2

Метод 2 из 5:

Геометрическая прогрессия

Загрузить PDF

Каждый член этой последовательности больше предыдущего члена в 2 раза, поэтому он может быть выражен рекуррентным уравнением, показанным на рисунке.
Рекуррентное уравнение вида a_n = r * a_n-1 является геометрической прогрессией.
Запишите формулу для вычисления n-го члена геометрической прогрессии, как показано на рисунке.
В нашем примере 3 - это 0-й член последовательности. Тогда формула имеет вид a_n = 3*2ⁿ. Если 3 - это 1-й член последовательности, то формула имеет вид a_n = 3*2^(n-1).
Реклама

Метод 3

Метод 3 из 5:

Многочлен

Загрузить PDF

, заданную рекуррентным уравнением, показанным на рисунке.
Любое рекуррентное уравнение вида, показанного на рисунке (где р(n) – многчлен от n), имеет многочлен, показатель которого на 1 больше, чем показатель р.
В нашем примере p имеет второй порядок, поэтому необходимо написать кубический многочлен, чтобы представить последовательность a_n.
Так как в кубическом многочлене четыре неизвестных коэффициента, запишите систему из четырех уравнений. Подойдут любые четыре, поэтому рассмотрите 0-ой, 1-ый, 2-ый, 3-ый члены. Если хотите, рассмотрите -1-ый член рекуррентного уравнения, чтобы упростить процесс решения (но это не обязательно).
Решите полученную систему степень(р)+2 уравнений для степень(р) = 2 неизвестных так, как показано на рисунке.
Если a - это один из членов, используемых вами для вычисления коэффициентов, то вы быстро найдете постоянный член многочлена и сможете упростить систему до степень(р)+1 уравнений для степень(р)+1 неизвестных так, как показано на рисунке.
Решите систему линейных уравнений и получите c₃ = 1/3, c₂ = -5/2, c₁ = -17/6, c = 5. Запишите формулу для a_n в виде многочлена с известными коэффициентами.
Реклама

Метод 4

Метод 4 из 5:

Линейные рекуррентные уравнения

Загрузить PDF

Однако этот метод можно применять для решения любых рекуррентных уравнений, в которых n-ый член является линейной комбинацией предыдущих k членов. Рассмотрим последовательность 1, 4, 13, 46, 157, ....
Для этого замените a_n на xⁿ и разделите на x^(n-k); вы получите многочлен степени k и постоянный член, отличный от нуля.
В нашем примере он имеет степень 2, поэтому используйте формулу для нахождения корней квадратного уравнения.
4
Любое выражение вида, показанного на рисунке, удовлетворяет рекуррентному уравнению. c_i - это любые постоянные, а основания степени – это корни характеристического многочлена (решенного выше).
- Если характеристический многочлен имеет несколько корней, то нужно сделать следующее. Если r - корень кратности m, вместо (c₁rⁿ) используйте (c₁rⁿ + c₂nrⁿ + c₃n²rⁿ + ... + c_mn^m-1rⁿ). Например, рассмотрим последовательность 5, 0, -4, 16, 144, 640, 2240, ..., удовлетворяющую рекуррентному уравнению a_n = 6a_n-1 - 12a_n-2 + 8a_n-3. Характеристический многочлен имеет три корня, а формула записывается так: a_n = 5*2ⁿ - 7*n*2ⁿ + 2*n²*2ⁿ.
Для этого запишите линейную систему уравнений с учетом начальных условий. Поскольку в нашем примере два неизвестных, запишите систему из двух уравнений. Подойдут любые два, поэтому рассмотрите 0-ой и 1-ый члены, чтобы избежать возведения иррационального числа в большую степень.
Реклама

Метод 5

Метод 5 из 5:

Производящие функции

Загрузить PDF

, заданную рекуррентным уравнением, показанным на рисунке. Оно не может быть решено с помощью любого из вышеописанных методов, но формула находится через производящие функции.
Производящая функция - это формальный степенной ряд, где коэффициент при xⁿ является n-ым членом последовательности.
Целью этого шага является нахождение уравнения, которое позволит вам решить производящую функцию А (х). Извлеките начальный член. Примените рекуррентное уравнение для оставшихся членов. Разбейте сумму. Извлеките постоянные члены. Используйте определение А (х). Используйте формулу для вычисления суммы геометрической прогрессии.
Методы нахождения коэффициента зависят от вида функции А(х), но на рисунке показан метод элементарных дробей в сочетании с производящей функцией геометрической прогрессии.
Реклама

Советы

Индуктивный метод тоже очень популярен. Зачастую легко доказать (используя индуктивный метод), что некоторая формула удовлетворяет некоторому рекуррентному уравнению, но проблема в том, что требуется заранее угадать формулу.
Некоторые из описанных методов требуют большого объема вычислений, что может повлечь ошибки. Поэтому проверьте формулу по нескольким известным условиям.