Вывод формулы n-ного члена для рекуррентной последовательности на примере задачи из квеста Амнезия

[ibessonov]

Здравствуйте!
Задача по виду очень похожа на вывод общей формулы для чисел Фибоначчи и для неё нам в универе давали намного более простой вывод.

Если отбросить начальный условия (F₀=0, F₁=10), то в качестве формулы решения можно попробовать рассмотреть F_n = λⁿ для некоторой константы λ. Уравнение на неё строится следующим образом:

λⁿ=3λ^n-1-2λ^n-2

Оно далее упрощается и быстро решается (по той же теореме Виета):

λ²-3λ+2=0
λ₁=2, λ₂=1

Мы нашли две подходящие последовательности. Не сложно заметить, что любая их линейная комбинация будет удовлетворять изначальному рекуррентному соотношению, а значит решение представимо в следующем виде:

F_n = aλ₁ⁿ + bλ₂ⁿ

Если подставить начальные условие, то получается система линейных уравнений:

F₀ = 0 = a + b
F₁ = 10 = aλ₁ + bλ₂

Если её решить, то получается тот же ответ, что и у вас:

a = 10, b = -10
F_n = 10*2ⁿ-10*1ⁿ = 10(2ⁿ-1)

[roginvs]

Да, можно и так. Интересно, верно ли что любая удовлетворяющая рекуррентному условию последовательность будет являться линейной комбинацией λ₁ и λ₂. Может быть даже это как-то очень легко получается

[ibessonov]

Да, любая рекуррентная последовательность заданного вида будет выражаться такой линейной комбинацией. Единственное исключение — это когда λ₁ и λ₂ совпадают.
Доказывается это тем, что определитель в матрице соответствующей системы уравнений будет ненулевым, а значит система всегда разрешима и полученное решение удовлетворяет изначальным условиям.
Более того, данный подход легко масштабируется на большее число слагаемых в рекуррентной формуле, просто уравнение получится не квадратным а большей степени.

[AC130]

Ну тогда уж следует упомянуть и случай комплексных корней характеристического уравнения, когда чисто действительные решения получаются с синусами и косинусами.

[windgrace]

А зачем вам вообще определитель? Переписываем рекуррентную последовательность как умножение вектора на некую постоянную матрицу, задача сводится к «найди общий вид формулы n-ной степени этой матрицы», дальше жорданова нормальная форма матрицы, собственные и обобщенные собственные вектора, все дела, плюс начальные условия, определитель нигде не нужен.

[ibessonov]

Ну так всё просто.
Представьте последовательность F_n=2*F_n-1-F_n-2, F₀ = 0, F₁ = 1.

Возможно вы удивитесь, попробовав её перечислить: 0, 1, 2, 3, 4, 5, 6…
Это как раз случай, когда λ₁=λ₂=1 и матрица системы уравнений является вырожденной. Формулу F_n=n в виде суммы показательных функций не выразить.
Это к слову о том, зачем нужен определитель. В моём методе без него не выйдет.

Что же касается возведения матрицы в степень, то да, там для любой последовательности формула выводится, с этим никто не спорит. Просто путь до неё посложнее будет.

[windgrace]

Мы, кажется, о каких-то разных матрицах говорим. Пусть все вектора далее — это столбцы. Рекуррентное соотношение в вашем примере запишется как (F_{n+1}, F_{n}) = A (F_{n}, F_{n-1}), а матрица A имеет вид (2 -1 \\ 1 0). С определителем у этой матрицы всё хорошо, det A = 1, как раз произведение собственных чисел.

А вы о какой матрице?

[ibessonov]

Я говорю о методе, который описан в 1-м комментарии. В нём появляется система линейных уравнений — матрица этой системы и имеется ввиду.

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

[windgrace]

А, понял, спасибо.

Метод из этого комментария хорош как готовый рецепт «делай так, есть шанс, что решение найдётся». А вот для понимания, почему мы ищем решение именно в такой форме — не очень.

[Taus]

В википедии неплохая статья про решение рекуррентных соотношений. В ссылках на учебники есть и доказательства.

[Sungmaster]

Если пойти эмпирическим путем, то можно вывести рекуррентную формулу первого порядка
F[n] = 2*F[n-1] + 10

[zelenin]

70 * 3 = 240
70 * 3 — 30 * 2 = 210

интересно

[roginvs]

Исправил, спасибо

[Dr_Dash]

И выше ещё — 240

[Arukueido]

Для любителей космических рейнджеров — в этот квест можно поиграть здесь отдельно от игры https://vasiliy0.gitlab.io/#Amnesia

[GlukKazan]

Достойно, но картинок не хватает.
В некоторых квестах они помогают.

[roginvs]

Где именно нет? Картинки точно должны быть во всех .qmm квестах (из 2-х рейнджеров)

[GlukKazan]

Ага, виноват. Действительно есть картинки.
Этот эмулятор бесценен!

[roginvs]

Исправил, теперь картинки на квесты с первых КР тоже отображаются верно (подключил PQI из dat-файла из оригинальной игры)

[Karlson_rwa]

Это волшебно! Спасибо!

[Refridgerator]

Для практических целей можно воспользоваться мат. пакетом. В Wolfram Mathematica это выглядит так:

RSolve[{
a[n] == 3 a[n - 1] - 2 a[n - 2], 
a[1] == 10, 
a[0] == 0
}, a[n],  n]

{{a[n] -> 10 (-1 + 2^n)}}

Интересно, что если таким же образом посчитать ряд Фибонначи

RSolve[{a[n] == a[n - 1] + a[n - 2], a[1] == 1, a[2] == 1}, a[n], n]

То ответ таким и будет:

{{a[n] -> Fibonacci[n]}}

Ну а саму формулу, с корнями и косинусом, можно получить через

Fibonacci[n] // FunctionExpand

((1/2 (1 + Sqrt[5]))^n - (2/(1 + Sqrt[5]))^n Cos[n \[Pi]])/Sqrt[5]

[Refridgerator]

UPD: Похоже, тег Source для Mathematica не совсем корректно работает… На предпросмотре ничего не раскрашивал.

[DarkGenius]

Разве здесь для наглядности не лучше было бы написать в правой части F[0] + (F[1]-3F[0])*x?
Я не сразу понял, почему при x мы сразу подставили 0 вместо F[0], а при нулевой степени — оставили F[0]. Или я что-то упустил из виду?

[roginvs]

Да, всё верно, поправил, спасибо

[AbrikOS3]

Это можно считать за О(lon(n)) с помощью матриц и быстрого возведения в степень. A = {{3, -2}, {1, 0}}; A * {{F[n-1]}, {F[n-2]}} = {{F[n]}, {F[n-1]}}, где {{A[1][1], A[1][2]}, {A[2][1], A[2][2]}} — матрица 2*2, {{v[1]}, {v[2]}} — вектор-столбец 2*1. Итого, (A^n) * {{10}, {0}} = {{F[n]}, {F[n-1]}}

[roginvs]

Действительно, «Бинарное возведение в степень» дает O(log(n)) операций

[p9202583853]

немного (чуточку) изменив задачу — на выходе получим вечные 30 баранов хрякоплюхов.

Пеленгский фермер Бух'ерик разводит хрякоплюхов. Эти животные размножаются так быстро, что их поголовье ежедневно возрастает в 3 раза. Но, начиная со второго дня, на ферму повадилась нападать стая страшных зверей долбогрызов, каждый вечер пожирающих вдвое больше хрякоплюхов, чем их было. в предыдущий день. Сколько хрякоплюхов будет у фермера на 7-й вечер, если вначале их было 10?

==
День 1
Утро 10 * 1 = 10
После размножения 10* 3 = 30
После долбогрызов (вечер) 10* 3 — 0 * 2 = 30

День n
Утро 30 * 1 = 30
После размножения 30* 3 = 90
После долбогрызов (вечер) 30* 3 — 30* 2 = 30
==

Скорее всего, так и задумывалось?

[roginvs]

В квесте требуется вводить результат по полученной формуле, так что вряд ли так и задумывалось. Да и задачи тогда толком не получается

[p9202583853]

квест не видел ранее — сейчас для себя его открываю ) интересно )

[windgrace]

Ммм, сразу вспоминается байка про Дирака и «минус две рыбы».

[p9202583853]

еще один вариант — электронные таблицы!
Не нужно умных формул…
Достаточно ввести пару простых правил типа ячейка * 3 и ячейка — ячейка = и все — тянем применяя автозаполнение и получаем к примеру 32 день, да и все остальные в наглядной форме — хоть графики рисуй)
Конечно есть пределы, но 40 дней не проблема посчитать за пару секунд и пару минут форматирования.

ссылка на Гуглодоки