Загрузить PDF
Загрузить PDF
Перед тем, как найти формулу некоторой математической последовательности, необходимо найти n-ый член этой последовательности, выраженный через предыдущие члены последовательности (а не как функция от n). Например, было бы неплохо знать функцию для n-го члена последовательности Фибоначчи, но зачастую у вас есть только рекуррентное уравнение, связывающее каждый член последовательности Фибоначчи с двумя предыдущими членами. Эта статья расскажет вам, как решить рекуррентное уравнение.
Шаги
-
Рассмотрим последовательность 5, 8, 11, 14, 17, 20, ....
-
Каждый член этой последовательности больше предыдущего члена на 3, поэтому он может быть выражен рекуррентным уравнением, показанным на рисунке.
-
Рекуррентное уравнение вида a n = a n-1 + d является арифметической прогрессией.
-
Запишите формулу для вычисления n-го члена арифметической прогрессии, как показано на рисунке.
-
Подставьте в формулу значения данной вам последовательности. В нашем примере 5 - это 0-й член последовательности. Тогда формула имеет вид a n = 5 + 3n. Если 5 - это 1-й член последовательности, то формула имеет вид a n =2 + 3n.Реклама
-
Рассмотрим последовательность 3, 6, 12, 24, 48, ....
-
Каждый член этой последовательности больше предыдущего члена в 2 раза, поэтому он может быть выражен рекуррентным уравнением, показанным на рисунке.
-
Рекуррентное уравнение вида a n = r * a n-1 является геометрической прогрессией.
-
Запишите формулу для вычисления n-го члена геометрической прогрессии, как показано на рисунке.
-
Подставьте в формулу значения данной вам последовательности. В нашем примере 3 - это 0-й член последовательности. Тогда формула имеет вид a n = 3*2 n . Если 3 - это 1-й член последовательности, то формула имеет вид a n = 3*2 (n-1) .Реклама
-
Рассмотрим последовательность 5, 0, -8, -17, -25, -30, ... , заданную рекуррентным уравнением, показанным на рисунке.
-
Любое рекуррентное уравнение вида, показанного на рисунке (где р(n) – многчлен от n), имеет многочлен, показатель которого на 1 больше, чем показатель р.
-
Напишите многочлен соответствующего порядка. В нашем примере p имеет второй порядок, поэтому необходимо написать кубический многочлен, чтобы представить последовательность a n .
-
Так как в кубическом многочлене четыре неизвестных коэффициента, запишите систему из четырех уравнений. Подойдут любые четыре, поэтому рассмотрите 0-ой, 1-ый, 2-ый, 3-ый члены. Если хотите, рассмотрите -1-ый член рекуррентного уравнения, чтобы упростить процесс решения (но это не обязательно).
-
Решите полученную систему степень(р)+2 уравнений для степень(р) = 2 неизвестных так, как показано на рисунке.
-
Если a - это один из членов, используемых вами для вычисления коэффициентов, то вы быстро найдете постоянный член многочлена и сможете упростить систему до степень(р)+1 уравнений для степень(р)+1 неизвестных так, как показано на рисунке.
-
Решите систему линейных уравнений и получите c 3 = 1/3, c 2 = -5/2, c 1 = -17/6, c = 5. Запишите формулу для a n в виде многочлена с известными коэффициентами.Реклама
-
Это один из методов решения последовательности Фибоначчи. Однако этот метод можно применять для решения любых рекуррентных уравнений, в которых n-ый член является линейной комбинацией предыдущих k членов. Рассмотрим последовательность 1, 4, 13, 46, 157, ....
-
Напишите характеристический многочлен рекуррентного уравнения. Для этого замените a n на x n и разделите на x (n-k) ; вы получите многочлен степени k и постоянный член, отличный от нуля.
-
Решите характеристический многочлен. В нашем примере он имеет степень 2, поэтому используйте формулу для нахождения корней квадратного уравнения.
-
Любое выражение вида, показанного на рисунке, удовлетворяет рекуррентному уравнению. c i - это любые постоянные, а основания степени – это корни характеристического многочлена (решенного выше).
- Если характеристический многочлен имеет несколько корней, то нужно сделать следующее. Если r - корень кратности m, вместо (c 1 r n ) используйте (c 1 r n + c 2 nr n + c 3 n 2 r n + ... + c m n m-1 r n ). Например, рассмотрим последовательность 5, 0, -4, 16, 144, 640, 2240, ..., удовлетворяющую рекуррентному уравнению a n = 6a n-1 - 12a n-2 + 8a n-3 . Характеристический многочлен имеет три корня, а формула записывается так: a n = 5*2 n - 7*n*2 n + 2*n 2 *2 n .
-
Найдите постоянную c i , удовлетворяющую начальным условиям. Для этого запишите линейную систему уравнений с учетом начальных условий. Поскольку в нашем примере два неизвестных, запишите систему из двух уравнений. Подойдут любые два, поэтому рассмотрите 0-ой и 1-ый члены, чтобы избежать возведения иррационального числа в большую степень.
-
Решите полученную систему уравнений.
-
Найденные постоянные подставьте в формулу.Реклама
-
Рассмотрим последовательность 2, 5, 14, 41, 122 ... , заданную рекуррентным уравнением, показанным на рисунке. Оно не может быть решено с помощью любого из вышеописанных методов, но формула находится через производящие функции.
-
Напишите производящую функцию последовательности. Производящая функция - это формальный степенной ряд, где коэффициент при x n является n-ым членом последовательности.
-
Преобразуйте производящую функцию, как показано на рисунке. Целью этого шага является нахождение уравнения, которое позволит вам решить производящую функцию А (х). Извлеките начальный член. Примените рекуррентное уравнение для оставшихся членов. Разбейте сумму. Извлеките постоянные члены. Используйте определение А (х). Используйте формулу для вычисления суммы геометрической прогрессии.
-
Найдите производящую функцию A(х).
-
Найдите коэффициент при x n в А(х). Методы нахождения коэффициента зависят от вида функции А(х), но на рисунке показан метод элементарных дробей в сочетании с производящей функцией геометрической прогрессии.
-
Запишите формулу для a n , чтобы найти коэффициент при x n в A(x).Реклама
Советы
- Индуктивный метод тоже очень популярен. Зачастую легко доказать (используя индуктивный метод), что некоторая формула удовлетворяет некоторому рекуррентному уравнению, но проблема в том, что требуется заранее угадать формулу.
- Некоторые из описанных методов требуют большого объема вычислений, что может повлечь ошибки. Поэтому проверьте формулу по нескольким известным условиям.
Реклама
Об этой статье
Эту страницу просматривали 39 707 раз.
Реклама
