Скорость роста суммы

[Sonic86]

Вот возьмем, например, бином Ньютона $(a+1)^n = \sum\limits_{k=0}^n \binom{n}{k}a^k$. В сумме слагаемое не имеет скорость роста. Максимальный рост среди всех слагаемых равен $\frac{2^n \sqrt{2}}{\sqrt{\pi n}}$, каждое слагаемое растет как $\binom{n}{k}$. А сама сумма имеет скорость роста $(a+1)^n$.
Вопрос такой: как для подобных сумм найти скорость роста в общем случае? Какая скорость роста, например, у таких сумм:
1. $\sum\limits_{k=0}^n e^{k^a}+e^{(n-k)^a}$
2. $\sum\limits_{k=0}^n \binom{n}{k}^a$ (хотя бы при $a=2$)

[nn910]

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

Какая скорость роста, например, у таких сумм:
1. $\sum\limits_{k=0}^n e^{k^a}+e^{(n-k)^a}$

$\sum\limits_{k=0}^n e^{k^a}+e^{(n-k)^a}=n \int_0^1 {(e^{(nx)^a}} +e^{(n-nx)^a})dx} $(эквивалентность а не равенство) , который можно ассимптотически свести к неполной гамма-функции

[ИСН]

Вторая сумма при $a=2$ сворачивается к чему-то типа $\binom{2n}{n}$

[RIP]

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

2. $\sum\limits_{k=0}^n \binom{n}{k}^a$ (хотя бы при $a=2$)

$\sim\frac{2^{an}}{\sqrt a}\left(\frac2{\pi n}\right)^{(a-1)/2}$ ($a>0$).
Для простых сумм типа этой можно применять дискретный аналог метода Лапласа. А именно:
Более-менее понятно, что основной вклад в сумму дают слагаемые вблизи $n/2$, конкретнее, слагаемые с $k=n/2+O(n^{0.6})$ (например). При таких $k$ с помощью дедушки Стирлинга получаем асимптотику
$\binom nk=2^n\sqrt{\frac2{\pi n}}e^{-2(k-n/2)^2/n}(1+O(n^{-0.2}))$ (очень грубая оценка).
Следовательно, искомая сумма равна (пользуемся монотонностью биномиальных коэффициентов)
$2^{an}\left(\frac2{\pi n}\right)^{a/2}\left(\bigl(1+O(n^{-0.2})\bigr)\sum_{|k-n/2|<n^{0.6}}e^{-2a(k-n/2)^2/n}+O\bigl(ne^{-2an^{0.2}}\bigr)\right)\sim$
$\sim2^{an}\left(\frac2{\pi n}\right)^{a/2}\sum_{|k-n/2|<n^{0.6}}e^{-2a(k-n/2)^2/n}.$
Последнюю сумму можно распространить на $k\in\mathbb Z$ (хвост можно оценить, например, так: при $n^{0.6}\le|k-n/2|<n$ оцениваем тривиально, а оставшийся хвост уже мажорируется убывающей геометрической прогрессией).
Дальше можно действовать по-разному.
Первый способ (самый простой) --- тупо заменяем сумму на интеграл, который равен $\sqrt{\pi n/(2a)}$; погрешность оцениваем из соображений монотонности как $O(1)$ (если применить формулу суммирования Эйлера--Маклорена, то остаток можно оценить гораздо лучше).
Второй способ (более тонкий и дающий исчерпывающую информацию по поведению суммы ряда; в данной задаче это слишком, но для общего развития полезно иметь в виду) --- формула суммирования Пуассона (или посмотреть в каком-нибудь справочнике готовую формулу для соответствующей тета-функции). Так или иначе получаем
$\sum_{k=-\infty}^\infty e^{-2a(k-n/2)^2/n}=\sqrt{\frac{\pi n}{2a}}\sum_{k=-\infty}^\infty(-1)^{nk}e^{-\pi^2k^2n/(2a)}\sim\sqrt{\frac{\pi n}{2a}}.$

Действуя чуть более аккуратно, можно получить асимптотику ($a>0$)
$\sum_{k=0}^n\binom nk^a=\frac{2^{an}}{\sqrt a}\left(\frac2{\pi n}\right)^{(a-1)/2}\left(1-\frac{(a-1)^2}{4an}+O(n^{-2})\right);$
ну, и т.д. Вот как-то так.

[ewert]

nn910 в сообщении #247236 писал(а):

$\sum\limits_{k=0}^n e^{k^a}+e^{(n-k)^a}=n \int_0^1 {(e^{(nx)^a}} +e^{(n-nx)^a})dx} $(эквивалентность а не равенство) , который можно ассимптотически свести к неполной гамма-функции

Во-первых, вторые слагаемые явно лишние -- они дублируют первые. Во-вторых, асимптотическим это равенство будет лишь при $\alpha<1$, иначе -- лишь оценка (фактически при $\alpha>1$ главным членом асимптотики будет просто наибольшее слагаемое).

[Sonic86]

Спасибо! Мне понятно.
Вторую сумму нашел в Грехэм, Кнут, Паташник, упр. 9.18.

З.Ы. Никто случаем производную гамма-функции не помнит? А то у меня какая-то фигня получается: $\Gamma ' (x) = x \Gamma (x-1)$.

[RIP]

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

Никто случаем производную гамма-функции не помнит?

А что конкретно Вас интересует?

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

А то у меня какая-то фигня получается: $\Gamma ' (x) = x \Gamma (x-1)$.

Действительно, фигня. Это Вы небось равенство \Gamma(x)=(x-1)\Gamma(x-1) неправильно продифференцировали?

[Sonic86]

RIP писал(а):

Действительно, фигня. Это Вы небось равенство $\Gamma(x)=(x-1)\Gamma(x-1)$ неправильно продифференцировали?

А! Все, понял! Я думал, что верно $\Gamma(x)=x \Gamma(x-1)$. Спасибо!

[Sonic86]

Еще такая же сумма:

$$\sum\limits_{k=1}^n \frac{n!}{(n-k)!} \left( \frac{2k}{n^2+3n+2}^k \right)^k$$

Я ее просто оценил как $\leq \frac{4}{n}$ (надеюсь, что верно). Хотелось бы (просто ради интереса), увидеть, как спецы вычисляют асимптотику (особенно интересно, как разбираются с факториалами - опять их тут нельзя заменить асмптотикой!)

[ИСН]

Зачем два раза маленькое k сверху? Кто на ком стоял?

[Sonic86]

ой!

$$\sum\limits_{k=1}^n \frac{n!}{(n-k)!} \left( \frac{2k}{n^2+3n+2} \right)^k$$

[lim0n]

(Оффтоп)

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

Я работаю как лошадь. На работе я программирую. Следовательно, я программирую как лошадь!

Лошадь программировать не может. Следовательно, на работе Вы бездельничаете!

[ИСН]

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

[Sonic86]

да, похоже, что банальность, увы

[Padawan]

ИСН в сообщении #365993 писал(а):

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

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