рекуррентная формула, найти общий член

[Борис Лейкин]

$x(n+1)=\dfrac{x(n)+2}{x(n)+1}$

Дана рекуррентная формула, найти формулу для общего члена?
(Не срочно! Мне просто интересно, решит её кто-нибудь или нет?
Скажите пожалуйста, где вы научились решать такие задачи (по каким учебникам)?)

[cepesh]

а начальное условие?

[Борис Лейкин]

cepesh писал(а):

а начальное условие?

Ну допустим $x(1)=x_1$

[Борис Лейкин]

При $n \to \infty$, $x(n) \to \sqrt{2}$, при любом начальном условии.
Ведь так, да?

[cepesh]

$x(n)$ обозначим через $c_n,\, \{c_n\} = \left\{0, 2, \frac43, \frac{10}{7}, \frac{24}{17}, \frac{58}{41},\frac{140}{99}, \frac{338}{239}, \frac{816}{577}, \frac{1970}{1393}, \dots\right\}$
$c_n = \frac{a_n}{b_{n-1}}$, где
$a_n = 2a_{n-1} + a_{n-2}, \, a_0 = 0,\, a_1 = 2$
$b_n = 2b_{n-1} + b_{n-2}, \, b_0 = 1,\, b_1 = 3$
$a_n = \frac{(1+\sqrt{2})^n}{\sqrt{2}} - \frac{(1-\sqrt{2})^n}{\sqrt{2}}$
$b_n = \left(\frac12 + \frac{1}{\sqrt{2}}\right)(1+\sqrt{2})^n + \left(\frac12 - \frac{1}{\sqrt{2}}\right)(1-\sqrt{2})^n$
http://www.research.att.com/~njas/sequences/Seis.html
$c_n = \frac{ \frac{(1+\sqrt{2})^n}{\sqrt{2}} - \frac{(1-\sqrt{2})^n}{\sqrt{2}}}{\left(\frac12 + \frac{1}{\sqrt{2}}\right)(1+\sqrt{2})^{n-1} + \left(\frac12 - \frac{1}{\sqrt{2}}\right)(1-\sqrt{2})^{n-1}} = 2\frac{(1+\sqrt{2})^n - (1-\sqrt{2})^n}{(2 + \sqrt{2})(1+\sqrt{2})^{n-1} + (\sqrt{2} - 2)(1-\sqrt{2})^{n-1}}=$
$=\sqrt{2}\frac{(1+\sqrt{2})^n - (1-\sqrt{2})^n}{(1+\sqrt{2})^n + (1-\sqrt{2})^n} = \sqrt2\left(1-\frac{2}{\left(\frac{1+\sqrt2}{1-\sqrt2}\right)^n + 1}\right)$
$\lim\limits_{n \to \infty} c_n = \sqrt2$
Правда, ничего дельного по теме я так и не рассказал...
Upd: где-то я накосячил...
Upd: подчистил косяки...

[Борис Лейкин]

Ух! Блин!

Нашёл я вот тут в библиотеке книжку, решил зачитать. http://lib.mexmat.ru/books/5802

[cepesh]

Теперь общий случай: $c_0 = y$, тогда $\{c_n\} = \left\{\frac{y}{1}, \frac{y+2}{y+1}, \frac{3y+4}{2y+3}, \dots\right\}$
$c_n = \frac{a_n}{b_n}$, где
$a_n = 2a_{n-1} + a_{n-2}, \, a_0 = y,\, a_1 = y+2$
$b_n = 2b_{n-1} + b_{n-2}, \, b_0 = 1,\, b_1 = y+1$
Выводим формулу общего члена для $a_n$ : $A_1 = \frac{2+\sqrt2 y}{2\sqrt2},\,A_2 = \frac{\sqrt2 y - 2}{2\sqrt2}$
$a_n = A_1 (1+\sqrt2)^n + A_2 (1-\sqrt2)^n$
Выводим формулу общего члена для $b_n$ : $B_1 = \frac{y+\sqrt2}{2\sqrt2},\,B_2 = \frac{\sqrt2 - y}{2\sqrt2}$
$b_n = B_1 (1+\sqrt2)^n + B_2 (1-\sqrt2)^n$
$c_n = \frac{a_n}{b_n}$
$c_n = \frac{(2+\sqrt2 y)\alpha^n + (\sqrt2 y - 2)\beta^n}{(y+\sqrt2)\alpha^n + (\sqrt2 - y)\beta^n}$, где $\alpha = 1+ \sqrt2,\, \beta=1-\sqrt2$
$\lim\limits_{n \to \infty} c_n = \sqrt2 \lim\limits_{n \to \infty} \frac{(\sqrt2+ y)\alpha^n - (\sqrt2 -y)\beta^n}{(y+\sqrt2)\alpha^n + (\sqrt2 - y)\beta^n} = \sqrt2$
Ну вроде все...

[Anar Yusifov]

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

С уважением, Анар.

[lofar]

Можно использовать известный изоморфизм группы дробно-линейных отображений и группы $PSL_2(\mathbb C)$.

Говоря проще, если дробно-линейному отображению

$$w = \frac{az+b}{cz+d}\qquad (1)$$

поставить в соответсвие матрицу

$$ \left(\begin{array}{cc} a & b\\ c& d \end{array}\right)\qquad(2), $$

то $n$-й итерации отображения (1) будет соответствовать $n$-я степень матрицы (2).

В Вашем случае

$$ \left(\begin{array}{cc} 1 & 2\\ 1 & 1 \end{array}\right) = \left(\begin{array}{cc} \sqrt{2} & \sqrt{2}\\ 1 & -1 \end{array}\right) \left(\begin{array}{cc} 1+\sqrt{2} & 0\\ 0 & 1 -\sqrt {2} \end{array}\right) \left(\begin{array}{cc} \sqrt{2} & \sqrt{2}\\ 1 & -1 \end{array}\right)^{-1}. $$

Следовательно, полагая для краткости $\alpha = 1+\sqrt{2}$, $\beta= 1-\sqrt{2}$ (© cepesh),

$$ \left(\begin{array}{cc} 1 & 2\\ 1 & 1 \end{array}\right)^n = \left(\begin{array}{cc} \sqrt{2} & \sqrt{2}\\ 1 & -1 \end{array}\right) \left(\begin{array}{cc} \alpha^n & 0\\ 0 & \beta^n \end{array}\right) \left(\begin{array}{cc} \sqrt{2} & \sqrt{2}\\ 1 & -1 \end{array}\right)^{-1}= \left(\begin{array}{cc} \sqrt{2}(\alpha^n+\beta^n) & 2(\alpha^n-\beta^n)\\ (\alpha^n-\beta^n) & \sqrt{2}(\alpha^n+\beta^n) \end{array}\right), $$

значит

$$ x(n) = \frac{\sqrt{2}(\alpha^n+\beta^n)x(0) + 2(\alpha^n-\beta^n)}{(\alpha^n-\beta^n)x(0) + \sqrt{2}(\alpha^n+\beta^n)}. $$

[Anar Yusifov]

to lofar
Молодчина! Опередил )

[Anar Yusifov]

to lofar

Разрешите полюбопытствовать, а откуда вы читали про этот изоморфизм, а то я уже третий раз читаю как решают эти задачи таким методом, а ссылок на литературу не дают. Если можно подскажите книжку.

С Уважением, Анар.

[lofar]

Читать тут нечего. Все просто. Пусть $G$ --- группа всех дробно-линейных преобразований $\mathbb C$. Отображение $\mu\colon SL_2(\mathbb C)\to G$, определяемое соотношением

$$ \mu\colon\left( \begin{array}{cc} a & b\\ c & d \end{array} \right)\mapsto\left[w=\frac{az+b}{cz+d}\right], $$

есть эпиморфизм групп: произведению матриц соответствует композиция отображений (подставьте одно дробно-линейное отображение в другое).

Ядро $\mu$ равно подгруппе $SL_2(\mathbb C)$ состоящей из двух элементов:$Ker(\mu) = \{E,-E\}$ ($E$ --- единичная матрица). Таким образом $G$ изоморфно $SL_2(\mathbb C)/\{E,-E\} = PSL_2(\mathbb C)$.

Кстати, проективные специальные линейные группы $PSL_n(K)=SL_n(K)/\{\alpha E|\alpha^n = 1\}$ ($K$ --- поле) занимают важное место. Дело в том, что для всякого поля $K$ группа $PSL_n(K)$ проста, за исключением $PSL_2(\mathbb Z_2)$ и $PSL_2(\mathbb Z_3)$ (теорема Жордана-Диксона).

[Anar Yusifov]

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

Буду очень вам благодарен за любую информацию. Спасибо.

С Уважением, Анар.

[Борис Лейкин]

lofar о чём-то писал(а):

...

Спасибо.
Никак не думал, когда спрашивал, что до такого дойдёт.