рекуррентное уравнение

[a1020]

Рекуррентное уровнение
помогите решить рекуррентное уровнение

\[\left\{ \begin{gathered} F(n) = {2^{n - 3}} + 2F(n - 2) + 2F(n - 3) \hfill \\ F(3) = 1 \hfill \\ F(4) = 2 \hfill \\ F(5) = 6 \hfill \\ \end{gathered} \right.\]

нужно вывести формулу, которая зависит только от n

// 2.05.09 темы «рекуррентное уравнение» и «булевы функции» соединены. / GAA

[ewert]

В принципе, надо искать поначалу решение однородного уравнения (без двойки в степени) в виде $F(n)=q^n$. Только там характеристическое уравнение для $q$ получается кубическим с плохими корнями. Скорее всего, с коэффициентами что-то напутано.

[a1020]

ewert писал(а):

В принципе, надо искать поначалу решение однородного уравнения (без двойки в степени) в виде $F(n)=q^n$. Только там характеристическое уравнение для $q$ получается кубическим с плохими корнями. Скорее всего, с что-то напутано.

с коэффициентами все написал точно, по этому принцыпу решать не получаеться, надо идти по другому пути

[Хорхе]

$2^{n-1}+$
$ \frac{1}{6} \left(-1-\frac{\left(2 \left(437-39 \sqrt{57}\right)\right)^{1/3}}{19^{2/3}}-\frac{14 2^{2/3}}{\left(19 \left(437-39 \sqrt{57}\right)\right)^{1/3}}\right) \times $ $ \left(\frac{1}{3} \left(27-3 \sqrt{57}\right)^{1/3}+\frac{\left(9+\sqrt{57}\right)^{1/3}}{3^{2/3}}\right)^{n} +$
$\left(-\frac{1}{6}+\frac{\left(1+i \sqrt{3}\right) \left(437-39 \sqrt{57}\right)^{1/3}}{6 38^{2/3}}+\frac{7 \left(1-i \sqrt{3}\right)}{3 \left(38 \left(437-39 \sqrt{57}\right)\right)^{1/3}}\right) \times $ $\left(-\frac{1}{6} \left(1+i \sqrt{3}\right) \left(27-3 \sqrt{57}\right)^{1/3}-\frac{\left(1-i \sqrt{3}\right) \left(9+\sqrt{57}\right)^{1/3}}{2 3^{2/3}}\right)^{n}$ $+$ $\left(-\frac{1}{6}+\frac{\left(1-i \sqrt{3}\right) \left(437-39 \sqrt{57}\right)^{1/3}}{6 38^{2/3}}+\frac{7 \left(1+i \sqrt{3}\right)}{3 \left(38 \left(437-39 \sqrt{57}\right)\right)^{1/3}}\right) \times $ $\left(-\frac{1}{6} \left(1-i \sqrt{3}\right) \left(27-3 \sqrt{57}\right)^{1/3}-\frac{\left(1+i \sqrt{3}\right) \left(9+\sqrt{57}\right)^{1/3}}{2 3^{2/3}}\right)^{n}$

Прекрасная формула, проще ничего не получится.

// Длинная формула разбита на части. / GAA

[a1020]

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

[ewert]

Да это просто формула Кардано, только кому она нужна.

(Степенные последовательности с комплексными корнями, естественно, сворачиваются в синусы и косинусы от соотв. арифметической прогрессии.)

[a1020]

Нужно найти количество наборов, удовлетворяющих равенству

\[{X_1}{X_2}{X_3} \oplus {X_2}{X_3}{X_4} \oplus ... \oplus {X_{n - 2}}{X_{n - 1}}{X_n} = 1\]

нужно вывести формулу, которая зависит только от n. Помогите с решением кто сможет

[Профессор Снэйп]

А что здесь что обозначает?

Наборы, если я правильно понял, состоят из нулей и единиц. Произведение обычное. А вот что такое $\oplus$?

[Xaositect]

Профессор Снэйп в сообщении #207953 писал(а):

Наборы, если я правильно понял, состоят из нулей и единиц. Произведение обычное. А вот что такое $\oplus$?

Сложение по модулю 2

[Профессор Снэйп]

А... То есть нужно посчитать количество слов длины $n$, составленных из нулей и единиц, в которые подслово $111$ входит нечётное число раз. Надо подумать, как это лучше сделать.

Добавлено спустя 3 минуты 47 секунд:

Можно выписать систему реккурентных соотношений и решать это дело методами линейной алгебры. Но может есть и что-то получше.

[a1020]

Профессор Снэйп писал(а):

А... То есть нужно посчитать количество слов длины $n$, составленных из нулей и единиц, в которые подслово $111$ входит нечётное число раз. Надо подумать, как это лучше сделать.

Добавлено спустя 3 минуты 47 секунд:

Можно выписать систему реккурентных соотношений и решать это дело методами линейной алгебры. Но может есть и что-то получше.

реккурентное уровнение получется вот такое

\[\left\{ \begin{gathered} F(n) = {2^{n - 3}} + 2F(n - 2) + 2F(n - 3) \hfill \\ F(3) = 1 \hfill \\ F(4) = 2 \hfill \\ F(5) = 6 \hfill \\ \end{gathered} \right.\]

но ее решение получается слишком длинным и не удобным для подсчета, если сможете найти что то более простое, буду признателен

[Профессор Снэйп]

Из каких соображений первое соотношение выписано? Как-то оно подозрительно выглядит!

P. S. Забавно, там, кстати, марковский процесс получается с шестью состояниями, и все вероятности переходов равны либо $0$, либо $1/2$. Можно при $n \to \infty$ легко асимптотику найти. А вот при малых $n$ всё сложнее

[AD]

a1020 в сообщении #207969 писал(а):

\[\left\{ \begin{gathered} F(n) = {2^{n - 3}} + 2F(n - 2) + 2F(n - 3) \hfill \\ F(3) = 1 \hfill \\ F(4) = 2 \hfill \\ F(5) = 6 \hfill \\ \end{gathered} \right.\]

Если так, то по идее эта задача стандартна - линейное разностное уравнение третьего порядка.

[RIP]

a1020 в сообщении #207969 писал(а):

реккурентное уровнение получется вот такое

\[\left\{ \begin{gathered} F(n) = {2^{n - 3}} + 2F(n - 2) + 2F(n - 3) \hfill \\ F(3) = 1 \hfill \\ F(4) = 2 \hfill \\ F(5) = 6 \hfill \\ \end{gathered} \right.\]

но ее решение получается слишком длинным и не удобным для подсчета, если сможете найти что то более простое, буду признателен

Для подсчёта, имхо, удобнее всего пользоваться рекуррентным уравнением (конечно, если оно верное), чем вот этим.

[Профессор Снэйп]

Я не понимаю, откуда взялось соотношение

$$F(n) = {2^{n - 3}} + 2F(n - 2) + 2F(n - 3)$$

и слабо в него верю. Щас быстренько напаскалю полнопереборную програмку, посчитаю первых значений 20, тогда понятно будет, правильно это или нет.

А вообще там довольно красивая вещь получается. Язык, состоящий из слов алфавита $\{ 0,1 \}$, в которые подслово $111$ входит нечётное число раз, конечно же, регулярный. ДКА для него имеет 6 состояний. Если всем переходам в нём приписать вероятность $1/2$, то получается марковский процесс, ну и нам нужно, фактически, посчитать вероятность того, что мы после $n$ переходов придём в одно из конечных состояний. Эргодическая теорема, кажется, работает. Но даже если без неё, там получается чисто линейная система, с постоянной матрицей перехода; никаких слагаемых типа $2^{n-3}$, в принципе, возникать не должно.

Ладно, буду прогу писать для начала

Добавлено спустя 1 час 4 минуты 17 секунд:

Вынужден попросить прощения у a1020 за своё недоверие. Формула оказалась верна. По крайней мере, первые 20 значений, вычисленные напрямую, совпадают со значениями, вычисленными по этой формуле.

Вот эти значения.

$$F(3) = 1$$

$$F(4) = 2$$

$$F(5) = 6$$

$$F(6) = 14$$

$$F(7) = 32$$

$$F(8) = 72$$

$$F(9) = 156$$

$$F(10) = 336$$

$$F(11) = 712$$

$$F(12) = 1496$$

$$F(13) = 3120$$

$$F(14) = 6464$$

$$F(15) = 13328$$

$$F(16) = 27360$$

$$F(17) = 55968$$

$$F(18) = 114144$$

$$F(19) = 232192$$

$$F(20) = 471296$$

Добавлено спустя 47 минут 36 секунд:

Мой подход к решению этой задачи лежит несколько с другого боку.

Допустим, что мы подкидываем монету и в соответствии с результатами подкидывания генерируем последовательность из нулей и единиц. Каждый член последовательности не зависит от остальных и равен одному из значений $0$, $1$ с вероятностью $1/2$. Пусть $x_1, x_2, \ldots$ --- полученная последовательность из нулей и единиц. Пусть также $f(n)$ равно вероятности того, что сумма

$$ x_1x_2x_3 + x_2x_3x_4 + \ldots + x_{n-2}x_{n-1}x_n $$

является нечётной. Очевидно, что $F(n) = f(n) \cdot 2^n$.

У нас есть 6 состояний: $a_1, a_2, a_3, b_1, b_2, b_3$. Из состояния $a_1$ можно перейти либо в $a_1$, либо в $a_2$. Из $a_2$ --- либо в $a_1$, либо в $a_3$. Из $a_3$ --- либо в $a_1$, либо в $b_3$. Из $b_3$ --- либо в $a_3$, либо в $b_1$. Из $b_2$ --- либо в $b_3$, либо в $b_1$. Из $b_1$ --- либо в $b_1$, либо в $b_2$. Каждый переход осуществляется с вероятностью $1/2$. Стартуем из состояния $a_1$. Искомое значение $f(n)$ равно вероятности того, что после $n$ переходов мы окажемся в одном из $b$-состояний.

Ну а тут уже теория марковских процессов. Я её, к сожалению, помню совсем-совсем плохо. Соответствующая стохастическая матрица выглядит так:

$$ \left( \begin{array}{cccccc} 1/2 & 1/2 & 1/2 & 0 & 0 & 0 \\ 1/2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1/2 & 0 & 0 & 0 & 1/2 \\ 0 & 0 & 0 & 1/2 & 1/2 & 1/2 \\ 0 & 0 & 0 & 1/2 & 0 & 0 \\ 0 & 0 & 1/2 & 0 & 1/2 & 0 \end{array} \right) $$

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

$$ (1/4,1/8,1/8,1/4,1/8,1/8) $$

с собственным значением $1$, который соответствует вероятностям нахождения системы в состояниях $a_1,a_2,a_3,b_1,b_2,b_3$ соответственно после большого числа переходов. Отсюда $f(n) \approx 1/4 + 1/8 + 1/8 = 1/2$ при $n \to \infty$. Другими словами, при больших $n$ примерно $2^{n-1}$ наборов будут удовлетворять нужному условию. Погрешность оценивать не берусь, не хватает квалификации.

Ну а при произвольных $n$ надо просто возводить эту матрицу в $n$-ую степень, для чего искать жорданову форму и т. д. Для стохастических матриц это вроде бы как-то просто делается. Опять, увы, ничерта не помню с третьего курса

Добавлено спустя 11 минут 11 секунд:

P. S. После всего проделанного смотрим сюда и узнаём ещё кое-что

В частности, там приведена какая-то странная формула

$$ \frac{x^2}{[(1-2x)(1-2x^2-2x^3)]} $$

Я не понял, что она означает. Но последовательность, судя по вычисленным значениям, вроде та. Хотя определяется как-то по другому

Добавлено спустя 7 минут 49 секунд:

P. P. S. Формула --- это, наверное, генерическая функция