Вопрос: Как найти асимптотику последовательности?

[bundos]

Как найти асимптотику последовательности $a_{n+1}=a_n+\frac1{\sqrt[k]{a_n}}$,$k$-целое число больше 1, c задананным $a_0>0$?

[sup]

Рассмотрите последовательность
$b_n=a_n-\frac{n}{\sqrt[k]{a_n}}$.
Будет ли она монотонной? Как насчет ее ограниченности?

[Sonic86]

Вообще, если дано соотношение $a_{n+1}=F(a_n,...,a_{n-r}), r = \text{const}$, то можно делать так: сначала предугадать, как будет вести себя $a_n$ (тут есть разные способы) - найти предполагаемое $f:f(n,p_1,...,p_s) \sim a_n$ ($p_j$ - параметры), и потом выполнить замену $a_n=f(n)+a'_n$, где $a'_n$ имеет асимптотику меньше, чем $f$, и подставить в рекуррентную формулу $a_{n+1}=F(a_n,...,a_{n-r})$ и из нее уже найти все параметры $p_j$ функции $f$ (с помощью рассмотрения асимптотики полученной формулы, например). В данном случае этот метод тоже работает.

[ewert]

Найти асимптотику -- очень просто. Надо заменить разностное уравнение на дифференциальное:

$\dfrac{da_n}{dn}=a_n^{-1/k};\quad a_n^{-1/k}da_n=dn;\quad \int a_n^{1/k}da_n=\int dn;\quad \dfrac{k}{k+1}\,a_n^{(k+1)/k}=n+C,$

т.е. должно быть $a_n\sim\left(\dfrac{k+1}{k}\,n\right)^{\frac{k}{k+1}$.

Теперь это надо формально обосновать. Если взять точную последовательность $b_n=\left(\dfrac{k+1}{k}\,n\right)^{\frac{k}{k+1}$, то нетрудно видеть, что она удовлетворяет рекуррентному уравнению вида $b_{n+1}-b_n=f(b_n)$, где $f(b)\sim b^{-1/k}$ при $ b\to+\infty$. Ну теперь надо воспользоваться тем, что последовательности, задаваемые подобного типа уравнениями, монотонно зависят от монотонных замен функций $f$ и т.д.

[Sonic86]

ewert писал(а):

Найти асимптотику -- очень просто. Надо заменить разностное уравнение на дифференциальное:

ewert, класс! обязательно запомню!

[bundos]

ewert в сообщении #433941 писал(а):

Найти асимптотику -- очень просто. Надо заменить разностное уравнение на дифференциальное:

Я вот немного не понимаю, разве мы можем заменить дискретную производную на непрерывную?Вообще C. Bender в книжечке что-то писал про аналогию, но я не совсем в этом разобрался.... $\a_n^{(k+1)/k}=n+C,$. Т.е. это-формула $n-ного$ члена для этой последовательности? Непонятно будет ли это решение единственным?
Или вы просто делаете это для того, чтобы получившийся результат проверить? Вот ещё вопрос: $a_{n+1}-a_n \to 0, n\to\infty$. Будет ли $a_{n+1}-a_n \sim a'(n)$. Я пробовал это доказать, что-то неполучилось, проверил для некоторых функций такого вида, вроде справедливо.....

[Sonic86]

bundos писал(а):

Я вот немного не понимаю, разве мы можем заменить дискретную производную на непрерывную?

Я так понял, что мы разностному уравнению ставим в соответствие дифференциальное уравнение, его решаем, а потом возвращаемся к исходному уравнению, делая замену переменной:

ewert писал(а):

т.е. должно быть $a_n\sim\left(\dfrac{k+1}{k}\,n\right)^{\frac{k}{k+1}$.

Смысл в том (боюсь соврать), что для функций, растущих не очень быстро, асимптотика производной (интеграла), такая же, как и асимптотика разности (суммы). Отсюда, кстати, ограничение на метод. Если $a_n \sim 2^n$, то $\Delta a_n \sim 2^n$, хотя $a'(n) \sim 2^n \ln 2$. Ну и т.п.

-- Вт апр 12, 2011 21:54:54 --

Цитата:

Вот ещё вопрос: $a_{n+1}-a_n \to 0, n\to\infty$. Будет ли $a_{n+1}-a_n \sim a'(n)$.

Да, получается, что это верно, поскольку $a_n$ растет медленнее $Cn$ - многочлена 1-й степени. Но это же верно и для многочленов любой степени.

-- Вт апр 12, 2011 21:59:21 --

Оно верно и для функций, растущих как $e^{\ln ^a x}, a>1$ - быстрее многочленов. Граница, видимо, проходит, по показательным функциям...

[bundos]

Sonic86 в сообщении #434107 писал(а):

Я так понял, что мы разностному уравнению ставим в соответствие дифференциальное уравнение, его решаем, а потом возвращаемся к исходному уравнению, делая замену переменной:

А на каком основании? Почему мы переходим к дифференциальному уравнению? На какую теорему там, или правило мы опираемся? Или чисто чтобы всё-таки "подглядеть"?

Sonic86 в сообщении #434107 писал(а):

асимптотика производной (интеграла), такая же, как и асимптотика разности (суммы)

А почему? Я попытался в лоб доказать, исходя из этого: $\Delta f(n)=f'(x)\Delta x+ o(\Delta x)$, не получилось что-то

-- Вт апр 12, 2011 20:07:08 --

Цитата:

Да, получается, что это верно, поскольку $a_n$ растет медленнее $Cn$ - многочлена 1-й степени.

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

[Sonic86]

bundos писал(а):

А на каком основании? Почему мы переходим к дифференциальному уравнению? На какую теорему там, или правило мы опираемся? Или чисто чтобы всё-таки "подглядеть"?

Я строгого обоснования не знаю. Просто соотношение $\Delta a_n \sim a'(n)$ дает возможность именно подглядеть. А истинность $\Delta a_n \sim a'(n)$ получается из того, что $a_n$ растет не быстре многочлена, что очевидно из рекуррентного уравнения.

bundos писал(а):

А почему? Я попытался в лоб доказать, исходя из этого: $\Delta f(n)=f'(x)\Delta x+ o(\Delta x)$, не получилось что-то

Я там написал

Sonic86 писал(а):

что для функций, растущих не очень быстро

И контрпример привел. Условие небыстрого роста существенно. Там кстати, вроде, как в правиле Лопиталя: надо сначала пытаться доказывать строго для сумм и интегралов $\sum a_n \sim \int a(n)dn$, а потом переходить к производным.
Я просто не помню точно, я это не в книжке читал. Может еще ewert придет и скажет точно, я скорее всего еще какие-то условия забыл.... Можете просто как идею запомнить...

[ewert]

Я пришёл, но ничего не скажу. Не из вредности или ещё чего похуже, а просто из лени.

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

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

А почему не скажу (т.е. почему лень) -- потому что бойан. Тут на форуме это уже было (может, и не один раз). И даже обосновывалось аккуратно. И даже я чего-то подобное точно писал (как минимум раз, и тоже аккуратно); только в упор не помню где и по какому поводу.

[bundos]

ewert в сообщении #434234 писал(а):

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

Т.е. для монотонных медленно растущих функций всегда будет $a_{n+1}-a_n\sim a'(n), n\to\infty$? Но тогда зачем же проверять полученный результат? Разве для таких функций после решения ДУ не получим ли мы сразу асимптотику?

А вы ещё говорили, что опровергать иногда приходится... А разве для медленно растущих функций такое случается, что найденное из ДУ асимптотика не подходит?

[Sonic86]

ewert писал(а):

А почему не скажу (т.е. почему лень) -- потому что бойан. Тут на форуме это уже было (может, и не один раз). И даже обосновывалось аккуратно. И даже я чего-то подобное точно писал (как минимум раз, и тоже аккуратно); только в упор не помню где и по какому поводу.

Это вот Вам баян, а я допер до этого не так давно + не припомню книжки с соответствующими утверждениями, чтобы там вот такая концепция была явно. Вот и придется теперь ради знаний прочитать все 15843 сообщения, чтобы найти нужное