Перейдём от уравнения (где все члены перенесены в левую часть) к системе. Обозначим через g(n) вектор-столбец из последовательных членов (f(n), f(n-1), ..., f(n-k))^T, где k = количество членов в рекуррентном соотношении минус два. Например, для соотношения Фибоначчи это (f(n), f(n-1))^T. В результате получим, что g(n+1) = A g(n), где в матрице A первая строка — это коэффициенты уравнения, а последующие — (0… 1… 0) — единица в i cтроке стоит на i-1 месте, остальные нули.
Тогда g(n) = A^n g(0). Переходим к собственному базису, A=T^{-1}BT, и всё сводится к возведению в степерь Жордановых клеток.
Эту конструкцию вы могли видеть в решении линейных дифференциальных уравнений с постоянными коэффициентами. Практически всё дословно перенеосится на дискретный случай.
Итого, общее решение можно найти таким образом. Решаем то самое «уравнение для потенциального предела». Пусть a, b, c… — его корни. Тогда общий член выглядит как Aa^n + Bb^n + Cc^n +… Если корни простые, то A, B, C — константы. Для кратных корней это будут многочлены от n степени на единицу меньше кратности. В случае комплексных корней лучше разбить их на пары сопряженных и от экспонент (a+bi)^n, (a-bi)^n перейти к r^n sin(n phi), r^n cos(n phi). Все коэффициенты находятся из начальных условий.
Теперь по поводу «формула для произвольного n». Лень разбираться, но я сильно сомневаюсь, что корни для произвольного n будут выражаться в радикалах. Можно поставить вопрос иначе — как будут распределяться корни при росте стпени. Тут ответа не знаю, увы. Можете спросить на dxdy.ru, там люди подкованные.
Ещё несколько соображений.
Существование предела можно доказать, если работает один из таких подходов.
1. Последовательность x(n) будет, например, монотонно возрастать и при этом все x(n) не превышают x (единственно возможный кандидат в пределы).
2. Монотонности может и не быть, x(n) «прыгает» вокруг x, но всё же можно сравнить |x(n+1) — x| с |x(n) — x| и окажется, например, что их частное не превышает какого-нибудь у<1 или наличие другой оценки гарантирующей сходимость (тут придётся вспоминать матанализ). Для примера можете посмотреть на итеративный процесс для вычисления корня t(n+1) = (t(n) + a/t(n))/2 и обоснование его сходимости.
И есть сильное подозрение, что если рекуррентное соотношение «короткое», коэффициенты и начальные значения «небольшие», то расчёт вручную нескольких сотен первых членов будет достаточным основание для сходимости. Но доказательство (если утверждение вообще верно) со всеми выкладками и обоснованиями, включая точные оценки для «короткое», «небольшие» и «несколько сотен» займёт приличный размер.
Для тех, кто знает, как выглядит общее решение
Отсутствие предела и при этом малое изменение x(n) говорит о том, что доминирующим членом в f(n) будет a^n sin(bn +c) при очень малом b. Само a не может быть большим (по предположениям на коэффициенты), поэтому при слишком малом b свободный член уравнения забьёт остальные.
А вот при больших степенях могут оказаться близкие комплексные корни и здесь можно серьёзно завязнуть в оценках.
Куда удобнее просто получить явную формулу для f(n), тогда поведение частного сразу станет очевидным.
Автору спасибо за интерес к математике. Надеюсь, он не исчезнет после небольшого холодного душа.
Во первых, существование предела нужно доказывать. Если кто-то думает, что можно обойтись, пусть поинтересуется парадоксом Перрона.
Во вторых, даже постановка «найдите отношение соседних членов» может оказать некорректной. Поясню.
Возьмём соотношение f(n+1) = 2f(n) — 2f(n-1), f(1) = 1, f(2) = 1.
Не поленитесь посчитать пару десятков следующих членов. Сюрприз — будут нули, причём их бесконечно много.
Можете взять другие начальные условия. Например, f(1) = 1, f(2) = 3. Сюрприз номер два — отношение будет принимать значения 3, 4/3, 1/2, -2 и дальше по кругу. Предела опять нет.
А у последовательности f(n+1) = 2f(n) — 3f(n-1) отношение будет прыгать без никакого намёка на предел.
Логичный вопрос — а что же тогда делать? Ответ — то, что вы можете обосновать. Допустим (допустим, а не постулирем!), у отношения f(n+1)/f(n) существует существует предел x. Тогда у f(n+2)/f(n) = (f(n+2)/f(n+1))/(f(n+1)/f(n)) тоже есть предел и он равен x^2. Аналогично для f(n+3)/f(n) стремится к x^3.
Для примера возьмём последнее уравнение. Поделив обе части на f(i), получим, что предел должен быть корнем уравнения x^4 — x^3 — x^2 — x — 1 = 0. Или предела нет, ещё ничего не доказано. Это и есть граница того, что можно доказать совсем на пальцах.
Между прочим, коэффициенты будут теми же самыми, что и в рекуррентном соотношении, и это неспроста. Собственно, найдя решения уравнения можно получить явную формулу для общего члена последовательности. Знакомые с линейной алгеброй могут попробовать разобраться самостоятельно.
Мораль 1. Баги бывают не только в наших программах, но и в рассуждениях.
Мораль 2. Если решаете математическую задачу, отвлекитесь от программистского подхода «сейчас машина всё нам посчитает».
Тогда g(n) = A^n g(0). Переходим к собственному базису, A=T^{-1}BT, и всё сводится к возведению в степерь Жордановых клеток.
Эту конструкцию вы могли видеть в решении линейных дифференциальных уравнений с постоянными коэффициентами. Практически всё дословно перенеосится на дискретный случай.
Итого, общее решение можно найти таким образом. Решаем то самое «уравнение для потенциального предела». Пусть a, b, c… — его корни. Тогда общий член выглядит как Aa^n + Bb^n + Cc^n +… Если корни простые, то A, B, C — константы. Для кратных корней это будут многочлены от n степени на единицу меньше кратности. В случае комплексных корней лучше разбить их на пары сопряженных и от экспонент (a+bi)^n, (a-bi)^n перейти к r^n sin(n phi), r^n cos(n phi). Все коэффициенты находятся из начальных условий.
Теперь по поводу «формула для произвольного n». Лень разбираться, но я сильно сомневаюсь, что корни для произвольного n будут выражаться в радикалах. Можно поставить вопрос иначе — как будут распределяться корни при росте стпени. Тут ответа не знаю, увы. Можете спросить на dxdy.ru, там люди подкованные.
Существование предела можно доказать, если работает один из таких подходов.
1. Последовательность x(n) будет, например, монотонно возрастать и при этом все x(n) не превышают x (единственно возможный кандидат в пределы).
2. Монотонности может и не быть, x(n) «прыгает» вокруг x, но всё же можно сравнить |x(n+1) — x| с |x(n) — x| и окажется, например, что их частное не превышает какого-нибудь у<1 или наличие другой оценки гарантирующей сходимость (тут придётся вспоминать матанализ). Для примера можете посмотреть на итеративный процесс для вычисления корня t(n+1) = (t(n) + a/t(n))/2 и обоснование его сходимости.
И есть сильное подозрение, что если рекуррентное соотношение «короткое», коэффициенты и начальные значения «небольшие», то расчёт вручную нескольких сотен первых членов будет достаточным основание для сходимости. Но доказательство (если утверждение вообще верно) со всеми выкладками и обоснованиями, включая точные оценки для «короткое», «небольшие» и «несколько сотен» займёт приличный размер.
А вот при больших степенях могут оказаться близкие комплексные корни и здесь можно серьёзно завязнуть в оценках.
Куда удобнее просто получить явную формулу для f(n), тогда поведение частного сразу станет очевидным.
Во первых, существование предела нужно доказывать. Если кто-то думает, что можно обойтись, пусть поинтересуется парадоксом Перрона.
Во вторых, даже постановка «найдите отношение соседних членов» может оказать некорректной. Поясню.
Возьмём соотношение f(n+1) = 2f(n) — 2f(n-1), f(1) = 1, f(2) = 1.
Не поленитесь посчитать пару десятков следующих членов. Сюрприз — будут нули, причём их бесконечно много.
Можете взять другие начальные условия. Например, f(1) = 1, f(2) = 3. Сюрприз номер два — отношение будет принимать значения 3, 4/3, 1/2, -2 и дальше по кругу. Предела опять нет.
А у последовательности f(n+1) = 2f(n) — 3f(n-1) отношение будет прыгать без никакого намёка на предел.
Логичный вопрос — а что же тогда делать? Ответ — то, что вы можете обосновать. Допустим (допустим, а не постулирем!), у отношения f(n+1)/f(n) существует существует предел x. Тогда у f(n+2)/f(n) = (f(n+2)/f(n+1))/(f(n+1)/f(n)) тоже есть предел и он равен x^2. Аналогично для f(n+3)/f(n) стремится к x^3.
Для примера возьмём последнее уравнение. Поделив обе части на f(i), получим, что предел должен быть корнем уравнения x^4 — x^3 — x^2 — x — 1 = 0. Или предела нет, ещё ничего не доказано. Это и есть граница того, что можно доказать совсем на пальцах.
Между прочим, коэффициенты будут теми же самыми, что и в рекуррентном соотношении, и это неспроста. Собственно, найдя решения уравнения можно получить явную формулу для общего члена последовательности. Знакомые с линейной алгеброй могут попробовать разобраться самостоятельно.
Мораль 1. Баги бывают не только в наших программах, но и в рассуждениях.
Мораль 2. Если решаете математическую задачу, отвлекитесь от программистского подхода «сейчас машина всё нам посчитает».