Рекуррентная последовательность

[lux_lucem]

Здравствуйте!
Помогите, пожалуйста, со следующей формулой:$f(n)=f(n-1)+f(n-3)+1$. Нужно найти f(37), но как, я не понимаю. Для того, чтобы составить характеристическое уравнение, мешается единица в рекуррентном соотношении. Может, как-то и без уравнения можно?
Пожалуйста, подтолкните к верному направлению. Большое спасибо!

[arseniiv]

А подставьте сюда решение однородного уравнения $f(n) = f(n-1) + f(n-3)$, которое вы умеете находить, но прибавьте сначала к нему константу.

[whitefox]

lux_lucem в сообщении #1175684 писал(а):

Для того, чтобы составить характеристическое уравнение, мешается единица в рекуррентном соотношении.

Перепишите рекуррентное уравнение для $n-1$ и вычтите его из уравнения для $n.$

[Brukvalub]

lux_lucem в сообщении #1175684 писал(а):

Помогите, пожалуйста, со следующей формулой:$f(n)=f(n-1)+f(n-3)+1$. Нужно найти f(37), но как, я не понимаю.

Найти $f(37)$ нельзя. Не хватает данных.

[lux_lucem]

Brukvalub
Да, конечно, забыла упомянуть $f(1)=1; f(2)=1; f(3)=2$. whitefox, arseniiv
Тогда получается уравнение $r^3-r^2-1=0$, решила, нашла, что $f(37)=1387575$. Написала программу, ответ получила другой - $1427439$. В общем, за программу ручаюсь, второй ответ скорее всего верный, но как решить алгебраически? Верное ли у меня характеристическое уравнение для последовательности?

[whitefox]

lux_lucem в сообщении #1175725 писал(а):

Тогда получается уравнение $r^3-r^2-1=0$

Хм, а не пробовали последовать моему совету? Уравнение другое.

[lux_lucem]

whitefox
Да я ему и последовала. Изначальную систему из двух последовательностей опущу, общее выражение для обеих последовательностей: $f(n-4)-f(n-3)+f(n-2)-2f(n-1)+f(n)=0$, отсюда такое уравнение получила:$r^4-2r^3+r^2-r+1=0$, что тождественно $(r-1)(r^3-r^2-1)$. Место ошибки никак найти не могу

[whitefox]

lux_lucem в сообщении #1175741 писал(а):

$(r-1)(r^3-r^2-1)$

Теперь уравнение верно.

[lux_lucem]

whitefox
А разве корень не тот же остался, как и у изначального моего уравнения? Мы же корень возводим в 37 степень. У меня все рано не выходит $1427439$, все также.

[whitefox]

А Вы у того уравнения только один вещественный корень нашли? Там ещё пара мнимых имеется. А в этом ещё четвёртый корень добавился.

[lux_lucem]

whitefox
Да, кажется, поняла наконец-то к чему Вы. Сейчас составлю систему из четырёх уравнений, чтобы определить коэффициенты при $r$ в искомой последовательности. Но разве если у нас уже есть два мнимых корня, не получатся ли и коэффициенты тоже мнимыми? Мне нужна последовательность из действительных чисел. Да и с корнями вообще у меня проблематично пока >< Система сложная выходит.

[Yu_K]

Хорошо бы проверить исходное уравнение - очень громоздкие выражения получаются - если аналитически вычислять. Может просто в Excel достаточно посчитать значение?

[lux_lucem]

Yu_K
Да, согласна, сложно посчитать. Изначально решала такую задачу:

Цитата:

$f(n)$ количество перестановок $r_1, r_2, r_3,...,r_n$ чисел $1, 2, 3,...,n$ при условии, что $r_1=1$ и $|r_i-r_{i+1}|\leqslant2$. Найти $f(37)$

. Раньше здесь уже мелькала подобная задача http://dxdy.ru/topic6216-30.html, оттуда и нашла рекуррентное соотношение. Ну, на первых числах последовательности вроде выполняется :) Честно признаться, проверить истинность этого рекуррентного соотношения пока не догадываюсь как.

[whitefox]

lux_lucem в сообщении #1175862 писал(а):

Сейчас составлю систему из четырёх уравнений

Для начала напишите формулу для общего решения рекуррентного уравнения. Затем попробуйте его упростить, может получится обойтись только тремя неопределёнными коэффициентами.

lux_lucem в сообщении #1175862 писал(а):

Но разве если у нас уже есть два мнимых корня, не получатся ли и коэффициенты тоже мнимыми?

Эти мнимые корни сопряжённые. Собственно, на это я и намекал в предыдущем абзаце.

lux_lucem в сообщении #1175862 писал(а):

Система сложная выходит

Это-то система трёх уравнений с тремя неизвестными сложная?

[iifat]

whitefox в сообщении #1175918 писал(а):

система трёх уравнений с тремя неизвестными

А почему трёх? Корня-то четыре.