Это, по крайней мере, если g (n) сходится к положительной бесконечности для n к положительной бесконечности (если g (n) нет, легко найти контрпримеры).
Эскиз доказательства:
Предварительные условия: g (n) сходится к положительной бесконечности, для n - к положительной бесконечности.
f (n) в o (g (n)) означает:
for every eps > 0 exists a n0 so that for all n > n0 abs(f(n)) < abs(g(n)*eps).
Форма выглядит следующим образом:
2^abs(f(n)) < 2^abs(g(n)*eps) = (2^eps)^g(n) (for n > n0).
для eps <1: </p>
(2^eps)^n is in o(2^n) (as 2^eps < 2)
из этого следует, что для каждого eps2> 0 существует n1, так что для всех n> n1
(2^eps)^n < eps2*(2^n).
Выбор eps2 = eps vields:
(2^eps)^n < eps*(2^n) for all n > n1 (n1 is dependent on eps)
Потому что g (n) -> поз. инф. для п -> поз. инф. существует n2, так что
g(n) > n1 for all n > n2
Исходя из
(2^eps)^g(n) < eps*2^g(n) for all n > n2.
Таким образом, для каждого 0 = max (n0, n2), так что
2^abs(f(n)) < 2^abs(g(n)*eps) = (2^eps)^g(n) < eps*2^g(n) for all n > n3.
Для каждого eps3> 1 также:
2^abs(f(n)) < eps*2^g(n) < eps3*2^g(n)
Таким образом, для каждого eps> 0 существует n3, так что
2^abs(f(n)) < eps*2^g(n) for all n > n3
Поскольку 2 ^ f (n) <2 ^ abs (f (n)) для всех n и 2 ^ x> 0 для всех вещественных x, следует
abs(2^f(n)) < abs(eps*2^g(n)) for all n > n3
* 1040 что и требовалось доказать *
Если что-то неясно или неправильно, пожалуйста, прокомментируйте.
РЕДАКТИРОВАТЬ: Некоторые мысли о других g (n):
Подпоследовательность g (n) ограничена, то есть существует некоторый x, так что не существует n0 с abs (g (n))> = x для всех n> n0:
o (g (n)) состоит только из функций, которые постоянны 0 после некоторого n или сходятся к 0. Тогда 2 ^ g (n) также имеет ограниченную подпоследовательность, но 2 ^ f (n) постоянна 1 после какой-то момент.
Нет n0, поэтому g (n)> 0 для всех n> n0:
2 ^ g (n) <1, если g (n) <0, поэтому g (n) имеет ограниченную подпоследовательность, означающую, что o (2 ^ g (n)) состоит только из функций, которые постоянны 0 после некоторого n или сходится к 0. </p>