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

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

Если отбросить начальный условия (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)

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

интересно

Для практических целей можно воспользоваться мат. пакетом. В 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]

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

Это можно считать за О(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]}}

немного (чуточку) изменив задачу — на выходе получим вечные 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
==

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

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

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