Оценить асимптотику для суммы

[forspam86]

У меня в расчётах вылезла такая сумма:

\large${\sum\limits_{k=1}^{\lfloor{n/2}\rfloor}\frac{(-1)^k{k}}{{k!(n-k)!}}\left(\frac{n}{2}-k\right)^n}$

(она меньше 0 и убывает).

Я пытаюсь найти для неё асимптотику при $n\to\infty$. Эмпирически получается, что порядок асимптотического роста этой суммы больше $n$, но меньше $n^2$.
Помогите, пожалуйста доказать, что она есть $o(n^2)$ (лучше, конечно, найти точную асимптотику, а ещё лучше — явную формулу для суммы).

[Zealint]

forspam86 в сообщении #316713 писал(а):

\large${\sum\limits_{k=1}^{\lfloor{n/2}\rfloor}\frac{(-1)^k{k}}{{k!(n-k)!}}\left(\frac{n}{2}-k\right)^n}$
лучше, конечно, найти точную асимптотику, а ещё лучше — явную формулу для суммы.

Maple-13 говорит, что ответ (специально не пишу в math, чтобы можно было скопировать и проверить):

-(floor(1/2*n)+1)*(-n+1+2*floor(1/2*n))/(n-1)/(-n+2*floor(1/2*n)+2)*(-1)^(floor(1/2*n)+1)/(floor(1/2*n)+1)!/(n-floor(1/2*n)-1)!*(1/2*n-floor(1/2*n)-1)-(-n+1)/(n-1)/(-n+2)/(n-1)!*(1/2*n-1)

Вам надо теперь доказать, что это правильно. Единственное, что при n=1 и 2 надо пределы считать, иначе деление на ноль получается. Асимптотику получить можно, если вспомните про формулу Стирлинга для асимптотики факториалов. А можно теперь и из этой формулы получить.

[forspam86]

Моя формула при $n=3$ равна $-1/16$, а ваша $-1/4$. Может быть, при записи суммы в Maple возникла опечатка?

[Руст]

Откуда возникла такая сумма?
Если последнее выражение заменить на $(\frac{n-1}{2}-k)^{n-2}$, то получается
$\frac{1}{\pi}\int_0^{\infty}(\frac{\sin x}{x})^{n-1}dx.$
А интегралы легче оценить.

[Zealint]

forspam86 в сообщении #317060 писал(а):

Может быть, при записи суммы в Maple возникла опечатка?

Да, действительно возникла. Пропустил k в числителе. Вашу формулу Maple считать не хочет. Если численно смотреть, то скорость получается $O(n^{1.27})$ (очень грубо).

А Вы сами асимптотику пытались считать? В чём именно проблема?

[Руст]

На самом деле оценка должна быть $O(n(\ln n)^m)$. Это можно вывести и напрямую, но хотелось бы, чтобы автор дал ответ, откуда такая сумма появилась. Возможно проще оценить исходя из первоначальной постановки.

[forspam86]

Руст в сообщении #317105 писал(а):

Если последнее выражение заменить на $(\frac{n-1}{2}-k)^{n-2}$, то получается
$\frac{1}{\pi}\int_0^{\infty}(\frac{\sin x}{x})^{n-1}dx.$

А как именно получается? Ведь формула \large${\sum\limits_{k=1}^{\lfloor{n/2}\rfloor}\frac{(-1)^k{k}}{k!(n-k)!}\left(\frac{n-1}{2}-k\right)^{n-2}}$ при $n=4$ равна $1/12$, а интеграл при $n=4$ равен $3/8$.

Руст в сообщении #317124 писал(а):

На самом деле оценка должна быть $O(n(ln n)^m)$. Это можно вывести и напрямую, но хотелось бы, чтобы автор дал ответ, откуда такая сумма появилась. Возможно проще оценить исходя из первоначальной постановки.

Да, мне тоже кажется, что оценка такая.
Сумма возникла при вычислении «площади» $(n-1)$-мерного сечения $n$-мерного гиперкуба.

Zealint в сообщении #317118 писал(а):

А Вы сами асимптотику пытались считать? В чём именно проблема?

Проблема в том, что у членов суммы чередуется знак. Если оставить только все положительные или только все отрицательные слагаемые, то сумма будет расти экспоненциально (в первом случае — в плюс, во втором — в минус). Непонятно, как доказать, что сумма двух экспоненциальных величин растёт медленнее, чем квадратичная функция.

[Руст]

forspam86 в сообщении #317131 писал(а):

Руст в сообщении #317105 писал(а):

Если последнее выражение заменить на $(\frac{n-1}{2}-k)^{n-2}$, то получается
$\frac{1}{\pi}\int_0^{\infty}(\frac{\sin x}{x})^{n-1}dx.$

А как именно получается?
В олимпиадном разделе maxal давал задачу. У вас предварительно надо исключить $k=n/2$, а после уменьшения n до n-1 суммирование по k и вообще останется до $[(n-2)/2]$, а это даст ту самую сумму, которая получилось при вычислении такого интеграла.
Поэтому для оценки лучше привести эту сумму по аналогии к интегральному виду и оценить. Если у вас не получится, помогу.

[forspam86]

Руст в сообщении #317204 писал(а):

В олимпиадном разделе maxal давал задачу. У вас предварительно надо исключить $k=n/2$, а после уменьшения n до n-1 суммирование по k и вообще останется до $[(n-2)/2]$, а это даст ту самую сумму, которая получилось при вычислении такого интеграла.
Поэтому для оценки лучше привести эту сумму по аналогии к интегральному виду и оценить. Если у вас не получится, помогу.

Помогите, пожалуйста, буду признателен. У меня не получается привести моё выражение к вашему, потому что моё выражение меньше 0 и стремится к $-\infty$, а ваше больше 0 и стремится к 0.
Кроме того, по ссылке интегральный синус преобразовывается в формулу, у которой под знаком суммы не совсем такое выражение, как у меня (там нет домножения на $k$, а у меня есть). Можно пытаться добавлять в сумму какие-то слагаемые, но проблема в том, что каждое такое индивидуальное слагаемое является экспоненциальным от $n$.

[Руст]

Цитата:

Помогите, пожалуйста, буду признателен. У меня не получается привести моё выражение к вашему, потому что моё выражение меньше 0 и стремится к $-\infty$, а ваше больше 0 и стремится к 0.
Кроме того, по ссылке интегральный синус преобразовывается в формулу, у которой под знаком суммы не совсем такое выражение, как у меня (там нет домножения на $k$, а у меня есть). Можно пытаться добавлять в сумму какие-то слагаемые, но проблема в том, что каждое такое индивидуальное слагаемое является экспоненциальным от $n$.

Во первых заметим, что при $k=[\frac n2]$ в скобках нщль и

$$\frac{k}{k!(n-k)!}(\frac n2 -k)^n=\frac{1}{(n-1)!2^n}\binom{n-1}{k-1}(n-1-1-2(k-1))^n.$$

Соответственно, лучше ввести переменные $m=n-1,j=k-1$ и переписать сумму в виде:

$$\frac{-1}{2^{m+1}m!}\sum_{j=0}^{[m/2]-1}(-1)^j\binom{m}{j}(m-1-2j)^{m+1}.$$

Соответственно это можно представить как вычет в нуле от функции

$$f(x)=\frac{-e^{-ix}}{2^{m+1}m!}\sum_{0\le j<=m/2-1}(-1)^j\binom{m}{j}\frac{(e^{ix})^{m-j}*(e^{-ix})^j}{x^{m+2}}.$$

Находим при четном m

$$Re f(x)=\frac{f(x)+f(x^*)}{2}=\frac{-cos x\sin^m x}{4m!x^{m+2}}$$

При нечетном m

$$Im f(x)=\frac{f(x)-f(x^*)}{2i}=\frac{-\sin^{m+1}x}{4m!x^{m+2}}$$

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

[forspam86]

Так, первый шаг понял. Проблемы возникают при переходе к вычетам.

Рассмотрим элемент суммы при фиксированных $m$ и $j$. Если я правильно понял, ваша запись означает, что \large$\mathop{\mathrm{res}}_{x=0}\frac{(e^{ix})^{m-j}*(e^{-ix})^j}{x^{m+2}}e^{-ix}=(m-1-2j)^{m+1}$. Я, правда, хотел уточнить, что понимается под знаком $*$ — обычное перемножение функций или почленное перемножение их рядов. Но в любом случае при $m=2$, $j=0$ модуль левой части равен $1/6$, а правая часть равна $1$. Там, видимо, как-то по-другому нужно функцию подбирать.

Далее, похоже есть недосмотр при подсчёте $\mathop{\mathrm{Re}}f(x)$ и $\mathop{\mathrm{Im}}f(x)$. Например, если подставить $m=2$ в \large$\frac{f(x)+f(x^*)}{2}$, то мы получим \large$-\frac{\cos{x}}{16x^4}$, домножения на синус не будет.

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

[Руст]

[quote] Если я правильно понял, ваша запись означает, что \large$\mathop{\mathrm{res}}_{x=0}\frac{(e^{ix})^{m-j}*(e^{-ix})^j}{x^{m+2}}e^{-ix}=(m-1-2j)^{m+1}$. Я, правда, хотел уточнить, что понимается под знаком $*$ — обычное перемножение функций или почленное перемножение их рядов. [\quote]

Да это вычет в 0 от функции $\frac{e^{i(m-1-2j)x}}{i^{m+1}x^{m+2}}.$ Умножение для представления в виде разложения степени синуса.
Соответственно

$$f(x)=\frac{-e^{ix}}{(2i)^{m+1}m!}\sum_{0\le j<[m/2]}(-1)^j\binom{m}{j}\frac{(e^{ix})^{m-j}(e^{-ix})^{j}}{x^{m+2}}.$$

Далее аккуратно надо привести к виду с суммированием по всему диапозону j. Это можно делать с самого начала или исходя из последней суммы. У меня не хватает терпения сделать это аккуратно.

[forspam86]

О, теперь понял больше. На самом деле, \large$\mathop{\mathrm{res}}\limits_{x=0}\frac{e^{i(m-1-2j)x}(m+1)!}{i^{m+1}x^{m+2}}=(m-1-2j)^{m+1}$.
Таким образом, сумма равна \large$-\frac{m+1}{(2i)^{m+1}}\mathop{\mathrm{res}}\limits_{x=0}\sum\limits_{j=0}^{\lfloor{m/2}\rfloor-1}(-1)^j{m\choose j}\frac{e^{i(m-1-2j)x}}{x^{m+2}}$.
Осталось найти вычет \large$\frac{e^{i(m-1-2j)x}}{x^{m+2}}$. Тут у меня проблемы, похоже, с какими-то базовыми знаниями. Если выписать равенства

$$\mathop{\mathrm{res}}_{z=0}\frac{e^{i(m-1-2j)z}}{z^{m+2}}=\frac{1}{2\pi{i}}\int\limits_{|z|=1}\frac{e^{i(m-1-2j)z}}{z^{m+2}}dz=|z=e^{i\varphi},dz=ie^{i\varphi}d\varphi|=\frac{1}{2\pi}\int\limits_0^{2\pi}e^{i((m-1-2j)e^{i\varphi}-\varphi(m+1))}d\varphi,$$

то последний интеграл будет равен 0 (так как в формуле для первообразной символ $\varphi$ встречается только в контексте $e^{i\varphi}$, следовательно, её значения при $\varphi=0$ и $\varphi=2\pi$ совпадают). Но этот вычет ведь точно не равен 0! Тут, кажется, загвоздка какая-то…

[Руст]

Цитата:

Осталось найти вычет \large$\frac{e^{i(m-1-2j)x}}{x^{m+2}}$. Тут у меня проблемы, похоже, с какими-то базовыми знаниями. Если выписать равенства

$$\mathop{\mathrm{res}}_{z=0}\frac{e^{i(m-1-2j)z}}{z^{m+2}}=\frac{1}{2\pi{i}}\int\limits_{|z|=1}\frac{e^{i(m-1-2j)z}}{z^{m+2}}dz=|z=e^{i\varphi},dz=ie^{i\varphi}d\varphi|=\frac{1}{2\pi}\int\limits_0^{2\pi}e^{i((m-1-2j)e^{i\varphi}-\varphi(m+1))}d\varphi,$$

то последний интеграл будет равен 0 (так как в формуле для первообразной символ $\varphi$ встречается только в контексте $e^{i\varphi}$, следовательно, её значения при $\varphi=0$ и $\varphi=2\pi$ совпадают). Но этот вычет ведь точно не равен 0! Тут, кажется, загвоздка какая-то…

У вас большие проблемы. Вычет легче вычисляется как коэффициент перед $\frac 1z$ в разложении Маклорена. Можно конечно и как вы $\frac{1}{2\pi i}\int_0^{2\pi}\frac{ie^{i\phi}d\phi ((dz))}{e^{i\phi}}=1.$

[forspam86]

Руст в сообщении #317865 писал(а):

У вас большие проблемы. Вычет легче вычисляется как коэффициент перед $\frac 1z$ в разложении Маклорена. Можно конечно и как вы $\frac{1}{2\pi i}\int_0^{2\pi}\frac{ie^{i\phi}d\phi ((dz))}{e^{i\phi}}=1.$

Не, у меня речь о другом. Если считать вычет как как коэффициент перед $\frac{1}{z}$ в разложении Маклорена, то мы получим $\frac{i^{m+1}}{(m+1)!}(m-1-2j)^{m+1}$, то есть придём к тому, с чего начали. То есть под «найти вычет» я понимаю «выразить вычет через интеграл», вы же вроде так посоветовали? Вот я выразил, но, похоже, у мнея где-то баг, так как через интеграл получается другой ответ (нулевой, а должно быть иначе). И в вашем случае $\frac{1}{2\pi i}\int_0^{2\pi}\frac{ie^{i\phi}d\phi ((dz))}{e^{i\phi}}=1$ — тоже другой ответ, и мне даже не ясно, как у вас получился именно такой интеграл.