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

[Yu_K]

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

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, оттуда и нашла рекуррентное соотношение. Ну, на первых числах последовательности вроде выполняется :) Честно признаться, проверить истинность этого рекуррентного соотношения пока не догадываюсь как.

lux_lucem

Там вроде написано обоснование соотношения.

В явном виде выписать полное решение - придется корни https://www.wolframalpha.com/input/?i=solve+x%5E3-x%5E2-1%3D0 - возводить в степень и складывать. Но может можно как то исхитриться. Z-преобразование и производящие функции тоже ничего хорошего не дадут.

Excel - самый быстрый вариант - совпадает с Вашим расчетом.

(Оффтоп)

1   1
2   1
3   2
4   4
5   6
6   9
7   14
8   21
9   31
10   46
11   68
12   100
13   147
14   216
15   317
16   465
17   682
18   1000
19   1466
20   2149
21   3150
22   4617
23   6767
24   9918
25   14536
26   21304
27   31223
28   45760
29   67065
30   98289
31   144050
32   211116
33   309406
34   453457
35   664574
36   973981
37   1427439

[lux_lucem]

whitefox
Система по сути не сложная, да корни у характеристического уравнения больно "сложные". Да, два из них сопряжённые комплексные числа, но какой у них ужасный модуль, и третий действительный корень тоже зарождает во мнения сомнения правильности самой рекуррентной последовательности... Я дико извиняюсь, но Вы сами не проверяли, какой получается тот самый 37 член последовательности, которую мы вручную сейчас находим? Боюсь, что с такими "монстрами", ничего не получится

[whitefox]

iifat в сообщении #1175930 писал(а):

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

Это так. Но так же верно, что для каждого корня $\alpha$ уравнения $z^3-z^2-1=0$ будет

$$\alpha^3=1+\alpha^2$$

-- 11 дек 2016, 16:10 --

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

Вы сами не проверяли, какой получается тот самый 37

Нет, недосуг как-то было.

[whitefox]

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

Вы сами не проверяли, какой получается тот самый 37

Вывел формулу и посчитал. Ответ 1427439.

[lux_lucem]

whitefox
Я, наверное, вообще наглею, но Вы не могли бы написать итоговую формулу, которую получили? Или там тоже все по-прежнему массивно выходит, как и в корнях? Пробовала сама – ничего не упрощается. Yu_K Спасибо большое за помощь! Интересно, как решить на бумаге, без компьютера.

[whitefox]

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

Вы не могли бы написать итоговую формулу, которую получили?

При всём моём желании, но правилами данного раздела это запрещено:

Цитата:

Для тех, кто оказывает помощь в решении задач.
Администрация форума обращается ко всем участникам с убедительной просьбой поддерживать просветительскую функцию раздела, т.е. учить решать задачи. Запрещается публикация полных готовых решений, особенно если речь идет о совсем простых задачах. Разумными способами оказания помощи являются, в частности, следующие:

1. Объяснить первый шаг решения задачи, предложив восстановить дальнейший ход рассуждений самостоятельно.
2. Дать ссылки на теоретические факты, которые должны быть использованы в решении задачи.
3. Описать общий ход решения, опустив технические детали, которые автор вопроса может восстановить самостоятельно.

А в чём, собственно, у Вас трудность? Характеристическое уравнение Вы уже нашли, его корни, надеюсь, уже вычислители. Один корень равен 1, второй вещественный корень обозначим как $\alpha,$ пару мнимых корней обозначим как $\beta$ и $\bar{\beta}.$ Тогда общим решением рекуррентного уравнения будет:

$$C_1+C_2\alpha^n+C_3\beta^n+C_4\bar{\beta}^n$$

Для нахождения формулы общего члена последовательности $\{f_n\}$ составим систему уравнений:

$$ \begin{cases} C_1+C_2+C_3+C_4=0\\ C_1+C_2\alpha+C_3\beta+C_4\bar{\beta}=1\\ C_1+C_2\alpha^2+C_3\beta^2+C_4\bar{\beta}^2=1\\ C_1+C_2\alpha^3+C_3\beta^3+C_4\bar{\beta}^3=2 \end{cases} $$

С учётом отмеченного ранее

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

Но так же верно, что для каждого корня $\alpha$ уравнения $z^3-z^2-1=0$ будет

$$\alpha^3=1+\alpha^2$$

Четвёртое уравнение превращается в

$$C_2\alpha^2+C_3\beta^2+C_4\bar{\beta}^2=2$$

а третье в

$$C_1=-1$$

То есть нам нужно решить систему трёх линейных уравнений с тремя неизвестными:

$$ \begin{cases} C_2+C_3+C_4=1\\ C_2\alpha+C_3\beta+C_4\bar{\beta}=2\\ C_2\alpha^2+C_3\beta^2+C_4\bar{\beta}^2=2\\ \end{cases} $$

Решив эту систему, Вы найдёте, что $C_2$ вещественное, а $C_3$ и $C_4$ комплексные причём $C_4=\overline{C}_3.$

Обозначим $a=C_2,$ $b=2\operatorname{Re} C_3,$ $c=2\operatorname{Im} C_3,$ $r=|\beta|,$ $\varphi=\arg\beta.$ Тогда искомая формула будет:

$$f_n=-1+a\alpha^n+br^n\cos n\varphi-cr^n\sin n\varphi$$

Так как $r<1,$ то $|br^n\cos n\varphi-cr^n\sin n\varphi|<(|b|+|c|)r^n$ стремится к нулю при $n$ стремящемся к бесконечности. И так как члены последовательности $\{f_n\}$ целые числа, то при достаточно большом $n$ (таком, что $(|b|+|c|)r^n<\frac12$) для вычисления $f_n$ достаточно вычислить $(-1+a\alpha^n)$ и округлить его до ближайшего целого. То есть получим следующее выражение:

$$ f_n:=\begin{cases} f_0=0\\ \dots\\ f_k=?\\ f_n=\left\lfloor a\alpha^n-\frac12\right\rfloor,&\text{если $n>k$.} \end{cases} $$

[lux_lucem]

whitefox
Спасибо вам огромное! Да собственно вся проблема в том, чтобы решить последнюю систему и в айти коэффициенты. Да, система несложная, да вот $\alpha,\beta$ больно "сложные"... и такие же кривые и большие коэффициенты выходят. Хотя, может, это у меня руки кривые... В общем, сложность в счёте. Привожу на фото "размер" корней, чтобы нагляднее было.

[whitefox]

А зачем Вам выражать корни через радикалы? Решите систему используя приближённые значения. А когда потребуются более точные значения, находите их каким-нибудь итерационным быстросходящимся методом.

[DeBill]

Про вывод рек. формулы: эта задача обсуждалась в http://dxdy.ru/topic113413.html: посмотрите рассуждения в моем сообщении там.

[Yu_K]

(Оффтоп)

Замечание чисто учебного плана.
Производящая функция получается здесь такая https://www.wolframalpha.com/input/?i=(s-2x%5E3-x%5E2-x)%2Fx%5E3%3D(s-x%5E2-x)%2Fx%5E2%2Bs%2Bx%2F(1-x)+solve+s и коэффициенты ее разложения в ряд будут членами искомой последовательности - например$f_{25}=14536$
https://www.wolframalpha.com/input/?i=1%2F25!*d%5E25((x+(1+-+x+%2B+x%5E2))%2F(1+-+2+x+%2B+x%5E2+-+x%5E3+%2B+x%5E4))%2Fdx%5E25+,+x%3D0

Wolfram ленится дальше 25-го члена считать.

[Vince Diesel]

(Оффтоп)

Yu_K в сообщении #1176832 писал(а):

Wolfram ленится дальше 25-го члена считать.

Можно попросить сразу ряд.

[Yu_K]

(Оффтоп)

Красивое получилось решение у whitefox.

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

$$\begin{bmatrix} 1&0 &1 \\ 1&0 &0 \\ 0& 1 & 0 \end{bmatrix}^{34}\cdot\begin{pmatrix} 2\\ 1\\ 1 \end{pmatrix}+\sum_{k=0}^{33}\begin{bmatrix} 1&0 &1 \\ 1&0 &0 \\ 0& 1 & 0 \end{bmatrix}^{k}\cdot \begin{pmatrix} 1\\ 0\\ 0 \end{pmatrix}$$

https://www.wolframalpha.com/input/?i=%7B%7B1,0,1%7D,%7B1,0,0%7D,%7B0,1,0%7D%7D%5E34*%7B2,1,1%7D
https://www.wolframalpha.com/input/?i=SUM%7B%7B1,0,1%7D,%7B1,0,0%7D,%7B0,1,0%7D%7D%5EK*%7B1,0,0%7D+FOR+K%3D0+TO+33

и итог для номера 37 https://www.wolframalpha.com/input/?i=578948%2B848491