Двойные факториалы

[Bulinator]

Посчитать сумму
$\frac{99}{100}+\frac{99\cdot 97}{100\cdot 98}+\frac{99\cdot 97\cdot 95}{100\cdot 98\cdot 96}+\ldots+\frac{99\cdot 97\cdot\ldots\cdot 1}{100\cdot 98\cdot 96\cdot\ldots\cdot 2}$

-- Пн янв 24, 2011 15:50:15 --

Ответ какой-то дебильный:
$\frac{5233262531964178122562851242895}{158456325028528675187087900672}$
Думаю суть в представлении суммы в каком-то хорошем виде.

[Sonic86]

(Оффтоп)

Bulinator писал(а):

Ответ какой-то дебильный:
$\frac{5233262531964178122562851242895}{158456325028528675187087900672}$

Ну Вы и прикололись! Так ведь даже $\sum\limits_{k=0}^n\frac{1}{k!}$ не найти!

-- Пн янв 24, 2011 18:15:03 --

Асимптотику найти можно:
$S=c_n \sum\limits_{k=0}^{n-1}b_k, c_n = \frac{(n-1)(n-3)...}{n(n-2)...}, b_0=1, b_{k+1}=\frac{2k+2}{2k+1}b_k$
$\ln b_{k+1} - \ln b_k = \ln \left( 1+ \frac{1}{2k+1} \right) \sim \frac{1}{2k}$
$\ln b_{k+1} \sim \frac{1}{2} \ln k \sim \ln b_k$
$b_k \sim \sqrt{k}$
$\sum\limits_k b_k \sim \frac{2}{3} k\sqrt{k} \to \frac{2}{3} n\sqrt{n}$
$\ln c_n = \sum\limits_{k=1}^n \ln \left( 1- \frac{1}{2k}\right) \sim - \sum\limits_{k=1}^n \frac{1}{2k} \sim - \frac{1}{2} \ln n$
$c_n \sim \frac{1}{\sqrt{n}}$
$S \sim \frac{2}{3}n$
Похоже?

-- Пн янв 24, 2011 18:20:05 --

Блин, эмпирически $\sim \frac{n}{3}$

-- Пн янв 24, 2011 18:26:38 --

В общем, можете найти асмиптотический ряд, у Вас знаменатель $\sim \frac{C}{k}$ и $\not \sim \frac{C}{k \ln k}$, поэтому ряд будет иметь вид $\frac{n}{3} \sum\limits_{j=0}^{+\infty} c_j n^{-j}$ за исключением, возможно, конечного числа членов (которые обычно в самом начале вылазят, наподобие $\ln n$ или $\frac{n}{\ln n}$) - найдите его с точностью до $C \Omega(k^{-1})$ и будет Вам счастье.

[Bulinator]

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

найдите его с точностью до $C \Omega(k^{-1})$ и будет Вам счастье.

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

-- Пн янв 24, 2011 19:57:57 --

(Оффтоп)

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

Ну Вы и прикололись! Так ведь даже $\sum\limits_{k=0}^n\frac{1}{k!}$ не найти!

Ну я думал что это жжж100 не спроста и получится что-то типа 10.

[Sonic86]

Ой! Bulinator! Я извиняюсь , я не знал, что это со школьной олимпиады, я думал это у Вам там из физики такое вылезло и решил его насильно взять.
Тогда подумать надо...

[Руст]

Обозначим через

$$x_n=\frac{2n-1}{2n}+\frac{(2n-1)(2n-3)}{2n(2n-2)}+....+\frac{(2n-1)!!}{(2n)!!}.$$

Легко получается, что $x_{n+1}=\frac{2n+1)}{2n+2}(x_n+1)$.
Введем новую переменную $y_n=x_n-\frac{2n-1}{3}$. Тогда рекурентное соотношение упрощается:

$$y_{n+1}=\frac{2n+1}{2n+2}y_n,y_1=\frac{1}{6}.$$

Следовательно

$$y_n=\frac{(2n-1)!!}{3(2n)!!}=O(n^{-1/2})<1,x_n=\frac{2n-1}{3}+\frac{(2n-1)!!}{3(2n)!!}.$$

В частности $x_{50}=33+\frac{99!!}{3*100!!}$.
Ничего проще не могу придумать.

[Bulinator]

Руст
Гениально!!!!

[Andrey173]

Как нашли $y_1$?

[Bulinator]

Andrey173 в сообщении #403967 писал(а):

Как нашли $y_1$?

$x_1=1/2$

[Andrey173]

Что-то я вчера в 12 ночи совсем никакой был Очевидные вещи спрашиваю