Асимптотический анализ

[ELVY]

Покажите, что для любых действительных констант $a$ и $b$, где $b > 0$, выполняется соотношение:

$$(n + a)^b = \theta(n^b)$$

Я понимаю, что должен найти две константы, такие что:

$$0 \leqslant c_{1}n^b \leqslant (n + a)^b \leqslant c_{2}n^b$$

Я не знаю, что еще можно сделать. Я попытался воспользоваться биномом Ньютона, однако ничего не получилось.

$$\theta(g(n)) = \{ f(n) : \exists c_1 > 0, c_2 > 0, n_0 > 0 : 0 \leqslant c_1g(n) \leqslant f(n) \leqslant c_2g(n), \forall n \geqslant n_0 \} $$

[thething]

Вынесите $n$ за скобку.

[ELVY]

thething
Ну, я что-то похожее делал, однако не понимаю как дальше продвинуться. $n^b(1 + a/n)^b$

[thething]

А о втором сомножителе Вы ничего сказать не можете?

[ELVY]

thething
Похоже на определение экспоненты, но в степени вместо $n$ стоит $b$.

[thething]

ELVY в сообщении #1408205 писал(а):

Похоже на определение экспоненты, но в степени вместо $n$ стоит $b$.

Ага, значит с экспонентой ничего общего.. Тема-то как называется? Глобально.

[ELVY]

thething
Рост функций. Это название всей главы.

[alcoholist]

ELVY
Так как ведет себя функция

ELVY в сообщении #1408203 писал(а):

$(1 + a/n)^b$

при изменении $n$?

[ELVY]

alcoholist
С ростом $n$ значение функции стремится к 1. Тогда можно взять по идее $c_1 = 1$, но нужно же еще найти $n_0$?

[thething]

ELVY
Ну и распишите определение предела теперь. Из него найдёте нужные константы. Только не "по идее", а просто по определению. "По идее" может быть и неправильно.

[ELVY]

thething
Получилась вот такая система уравнений:

$$\begin{cases} n < \frac{a}{\sqrt{1 - \varepsilon} - 1} \\ n > \frac{a}{\sqrt{1 + \varepsilon} - 1} \\ n > 0 \end{cases}$$

Однако как отсюда выбрать $n_0$ не совсем понятно.

[thething]

У Вас написано что-то странное. Не нужно писать, что получилось, нужно выписать определение предела, а потом подумать, как из него выделить две нужные константы, ограничивающие сверху и снизу Вашу функцию. И это $n_0$ от Вас не требуется выражать явно, важно лишь, что оно есть.

[ELVY]

thething Определние такое получается?
$\forall \varepsilon > 0, \exists \delta = \delta(n) : \forall{n} , 0 < n - n_0 < \delta \Rightarrow |f(n) - A| < \varepsilon$

[thething]

Откуда Вы взяли такое определение, из головы? Откройте конспект, учебник, гугл, в конце-концов (ищите "предел последовательности", вот что я имел ввиду, когда про тему спрашивал).

[Otta]

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