Асимптотика суммы

[Samir]

Задача такая:
требуется найти асимптотику суммы $\sum_{k=1}^{n} C_n^k 2^\frac n k$, при $n \rightarrow \infty$

Пробую разбивать сумму на части. Например, видно, что $\sum_{k=n-1}^{n} C_n^k 2^\frac n k \sim 2$

Также видно, что $\sum_{k=1}^{2} C_n^k 2^\frac n k \sim e^{-1} 2^n \left( \frac n {n-1} \right)^\frac {2n+1} 2$, если использовать формулу Стирлинга для оценки факториала и доказав, что второй член суммы бесконечно мал по отношению к первому.

Не знаю, что делать со средней частью суммы..

[AlexValk]

Какой Стирлинг для расчета младших биноминальных коэффициентов $C^1_n=n$ и $C^2_n=\frac{n(n-1)}{2}$?!
Сумма двух последних членов у вас также оценена неправильно - на самом деле она $\sim n+1$.

Главный член асимптотики вашей суммы - это её первый член $ 2^n n$.
Менее тривиальная задача - найти следующий член асимптотики (относящийся к сумме членов со второго и дальше) - он равен $4\cdot 2^n$.
Естественно, и то и другое надо как-то доказывать.

[Samir]

Да, с младшими членами совсем смешно вышло) Спасибо.

Думаю, у вас опечатка: сумма последних двух членов эквивалентна $2n+2$

С этим понятно, но не понимаю, как оценить не отдельные члены, а хотя бы какую-то часть суммы с верхним или нижним пределом, зависящим от n. Получаются какие-то громоздкие выражения и непонятно, как это привести к разумному ответу.

Пробую оценивать 1-ю часть, где степень двойки больше двух, вторая часть - степень двойки от 1.5 до 2, третья - степень двойки от 1 до 1.5.

Как думаете, идея правильная?

[Sonic86]

Samir в сообщении #1065233 писал(а):

Думаю, у вас опечатка: сумма последних двух членов эквивалентна $2n+2$

Это верно, но эти 2 члена асимптотически неэквивалентны, так что это именно 2 разных слагаемых асимптотического разложения.

Samir в сообщении #1065233 писал(а):

С этим понятно, не понимаю, как оценить не отдельные члены, а хотя бы какую-то часть суммы с верхним или нижним пределом, зависящим от n.

это уже другая задача: найти асимптотику $\sum_{k=f(n)}^{n} C_n^k 2^\frac n k$ или $\sum_{k=1}^{g(n)} C_n^k 2^\frac n k$. Напишите конкретно сумму, асимптотику которой Вы оцениваете.
Для этой задачи достаточно поделить сумму на 1-й член и найти предел.

[Samir]

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

Напишите конкретно сумму, асимптотику которой Вы оцениваете.

К примеру, хочу найти асимптитоку такой суммы, после вынесения первого члена за скобки:

$$\sum_{k=2}^{\lfloor n/2 \rfloor} \frac {C_n^k} {n2^{\frac {n(k-1)} {k}}}$$

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

Также можно написать тривиальные верхнюю и нижнюю оценки этой суммы:

$$\sum_{k=2}^{\lfloor n/2 \rfloor} \frac {C_n^k} {n2^{\frac {n(k-1)} {k}}} \leqslant \frac {C_n^{\lfloor n/2 \rfloor} (\lfloor n/2 \rfloor - 1)} {2^{\frac n 2 + 1}}$$

$$\sum_{k=2}^{\lfloor n/2 \rfloor} \frac {C_n^k} {n2^{\frac {n(k-1)} {k}}} \geqslant \frac {C_n^2 (\lfloor n/2 \rfloor - 1)} {n2^{n-2}}$$

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

Может быть, нужно пытаться подбирать такую функцию, при делении на которую этой суммы в пределе будет получится 1?

[Sonic86]

Я бы так рассуждал: $k$ меняется от $1$ до $\frac{n}{2}$. $C_n^k$ при этом увеличивает свой рост до экспоненциального. $2^{n\left(1-\frac{n}{2}\right)}$ плавно меняет свой рост от экспоненциального до экспоненциального. Про $n$ вообще можно забыть. Значит какие слагаемые дают основной вклад? Далее надо проверить, не являются ли вклад описанных слагаемых подавляющим.

Samir в сообщении #1066226 писал(а):

Также можно написать тривиальные верхнюю и нижнюю оценки этой суммы:

$$\sum_{k=2}^{\lfloor n/2 \rfloor} \frac {C_n^k} {n2^{\frac {n(k-1)} {k}}} \leqslant \frac {C_n^{\lfloor n/2 \rfloor} (\lfloor n/2 \rfloor - 1)} {2^{\frac n 2 + 1}}$$

Эту оценку можно улучшить, если отбросить несколько первых членов суммы.

[Samir]

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

Значит какие слагаемые дают основной вклад? Далее надо проверить, не являются ли вклад описанных слагаемых подавляющим.

Обозначим эту сумму через $S$. Можно доказать, что, например, что $ S_{n/4} = o(S_{n/2})$, используя, например, формулу Стирлинга для оценки факториалов.

Далее, можно разбить эту сумму на сколько угодно много частей $m$ и видно, что $S_{nl/m}=o(S_{n/2}), l < m/2$

Отсюда следует, что эта сумма эквивалентна последнему слагаемому, то есть $\frac {C_n^{n/2}} {n2^{n-2}}$

В свою очередь, используя всю ту же формулу Стирлинга, имеем:

$$\frac {C_n^{n/2}} {n2^{n-2}} \sim \frac {4\sqrt{2}} {\sqrt{\pi}n^{3/2}}$$

Но в то же время смущает, что, например,

$$S_{n/2} \sim S_{n/2-a}, a - const$$

Таким образом, не совсем понимаю, верны ли мои рассуждения.

Для второй суммы (индексы от $n/2$ до $n$) получаю то же самое.

[Sonic86]

Samir в сообщении #1066358 писал(а):

Далее, можно разбить эту сумму на сколько угодно много частей $m$ и видно, что $S_{nl/m}=o(S_{n/2}), l < m/2$

Отсюда следует, что эта сумма эквивалентна последнему слагаемому, то есть $\frac {C_n^{n/2}} {n2^{n-2}}$

Строго говоря, не следует. Что конкретно следует, мне чего-то в голову не лезет (я разбирал пример, когда отбрасывалось конкретное число слагаемых), контрпример вроде такой: из $S_n=\sum\limits_{k=1}^{n/2}C_n^k$ следует тоже, что $S_{nl/m}=o(S_{n/2}), l < m/2$, но не следует, что $S_n\sim C_n^{n/2}$
Но такая догадка вполне может появится.
Лучше доказать в лоб. Найдите предел $\lim\limits_{n\to +\infty}\frac{S_n}{\frac {C_n^{n/2}} {n2^{n-2}}}$ более простым способом.

[Samir]

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

Лучше доказать в лоб. Найдите предел $\lim\limits_{n\to +\infty}\frac{S_n}{\frac {C_n^{n/2}} {n2^{n-2}}}$ более простым способом.

Получаю такое:

$$\sum_{k=2}^{n/2} \frac {(n/2)!(n/2)! 2^{n/k}} {4k!(n-k)!}$$

Опять видно, что все решает последний член, который стремится к $1$, начало стремится к 0, но значит ли это, что и вся сумма стремится к 1, и если да, то почему? Может, здесь бином Ньютона как-то может пригодиться?

[Sonic86]

(Оффтоп)

Samir в сообщении #1066358 писал(а):

Но в то же время смущает, что, например,

$$S_{n/2} \sim S_{n/2-a}, a = const$$

Это верно для любой функции, растущей не быстрее многочлена

$(\forall \epsilon>0) S_{(1/2-\epsilon) n}=o(S_{n/2})$
$S_{n/2} \sim \sum\limits_{k=(1/2-\epsilon) n}^{n/2}\frac{2^{k/n}C_n^k}{2^n}$
$2^{1/2-\epsilon} \leqslant 2^{k/n}\leqslant \sqrt{2}$
$\frac{2^{1/2-\epsilon}}{2^n}B_n \leqslant S_{n/2} \leqslant \frac{\sqrt{2}}{2^n}B_n$, где
$B_n\sim\sum\limits_{k=(1/2-\epsilon) n}^{n/2}C_n^k$
Последняя сумма, ЕМНИП, оценивается относительно легко (через локальную формулу Муавра-Лапласа, вроде), но я сейчас торможу, не могу выписать явную формулу.
Если я нигде не наврал (я без бумаги, могу легко ошибиться), то все получается ($\epsilon$ легко элиминируется). Однако, у меня сильное ощущение, что наврал

[AlexValk]

Проделаем сначала численный эксперимент. Поделите оцениваемый остаток суммы $\frac{1}{2^n}\sum\limits_{k=2}^n C_n^k 2^\frac{n}{k}$ на $2^n$ и гляньте на график функции, хотя бы при $n=50$. Ничего не напоминает? Это гауссиан. И сразу видно, что главный вклад в сумму $\sum\limits_{k=2}^n C_n^k 2^\frac{n}{k}$ вносит окрестность $k=\frac{n}{2}$, что и указывал Sonic86. В итоге общая идея - свести эту сумму к гауссиану (ну а тогда, можно надеяться, что вместо суммирования в итоге можно будет перейти к интегрированию). Практическая реализация этого плана:

Полагаем $k=\frac{n}{2}+\frac12\sqrt{n}y$. (Здесь используется тот факт, что характерная ширина нашего гауссиана имеет порядок $\sqrt{n}$. Этот $\sqrt{n}$ не обязательно угадывать - можно работать и по схеме Sonic86: $k=\frac{n}{2}+\frac12n x $, просто с $\sqrt{n}$ результат лучше выглядит). После манипуляций со Стирлингом и т.п., получим в главном порядке по $n\;$:

$$\frac{1}{2^n}C_n^k 2^\frac{n}{k}\sim \frac{8}{\sqrt{2\pi n}}e^{-y^2/2}.$$

Интересующая нас сумма по $k$ с шагом 1 в окрестности $k=n/2$ переписывается как интегральная сумма от функции $4\cdot\frac{1}{\sqrt{2\pi}}e^{-y^2/2}$ с шагом $\Delta y=\frac{2}{\sqrt{n}}$. При $n\to \infty$ пределы интегрирования по $y$ можно заменить на $\pm \infty$ и мы получаем

$$\frac{1}{2^n}\sum\limits_{k=2}^n C_n^k 2^\frac{n}{k}\sim 4\int\limits_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi}}e^{-y^2/2} dy =4.$$

Таким, образом, как и было обещано, два первых члена асимптотики вашей суммы имеют вид

$$\sum\limits_{k=1}^{n} C_n^{k} 2^\frac{n}{k}=2^{n} n+\sum_{k=2}^{n} C_n^{k} 2^\frac{n}{k}\sim 2^n n +4\cdot 2^{n}=2^{n}(n+4).$$

Любопытно, что главный член определяется первым членом ряда, а второй член - суммой многих членов центрального участка. Это правильный ответ, но для его совершенно строгого обоснования здесь не хватает некоторой оценки суммы начального участка ряда от $k=2$ (и конечного участка тоже - но там все проще, т.к. члены ряда меньше из-за множителя $2^{n/k}$ ). Следующая поправка имеет порядок $2^nO(1/n)$.