Азиатско-Тихоокеанская математическая олимпиада, 1996 год

$m$ и $n$ — два натуральных числа и $n \leq m$. Докажите, что $$ {2^n} \leq \frac{{\left( {m + n} \right)!}}{{\left( {m - n} \right)!}} \leq {\left( {{m^2} + m} \right)^n}. $$

Комментарий/решение

$$ \frac{(m+n)!}{(m-n)!}=\prod_{k=1}^{2n}(m-n+k)=\prod_{k=1}^{n}(m-n+k)\prod_{k=n+1}^{2n}(m-n+k)=$$

$$ =\prod_{k=1}^{n} m\left(1-\frac{n-k}{m}\right) \prod_{k=n+1}^{2n} (m+1)\left(1-\frac{n-k+1}{m+1}\right)=$$

$$ =\prod_{k=1}^{n} m\prod_{k=1}^{n} \left(1-\frac{n-k}{m}\right) \prod_{k=n+1}^{2n} (m+1)\prod_{k=n+1}^{2n}\left(1-\frac{n-k+1}{m+1}\right)$$

$$\prod_{k=1}^{n} m=m^n \qquad \prod_{k=n+1}^{2n} (m+1)=(m+1)^n$$

$$ \frac{(m+n)!}{(m-n)!}=m^n(m+1)^n\prod_{k=1}^{n} \left(1-\frac{n-k}{m}\right) \prod_{k=n+1}^{2n}\left(1-\frac{n-k+1}{m+1}\right)\leq$$

$$\leq (m^2+m)^n=m^n(m+1)^n \Rightarrow$$

$$\prod_{k=1}^{n} \left(1-\frac{n-k}{m}\right) \prod_{k=n+1}^{2n}\left(1-\frac{n-k+1}{m+1}\right)\leq 1$$

$$ m \geq n \geq n-k \Rightarrow 1 \geq \frac{n-k}{m} \Rightarrow \left(1-\frac{n-k}{m}\right) \leq 1 \Rightarrow \prod_{k=1}^{n} \left(1-\frac{n-k}{m}\right) \leq 1$$

$$ m \geq n-k \Rightarrow m+1 \leq n-k+1 \Rightarrow 1 \leq \frac{n-k+1}{m+1} \Rightarrow\prod_{k=n+1}^{2n}\left(1-\frac{n-k+1}{m+1}\right)\leq 1$$

$$ $$

$$ \frac{(m+n)!}{(m-n)!}=\prod_{k=1}^{2n}(m-n+k)=\prod_{k=1}^{n}(m-n+2k-1)\prod_{k=1}^{n}(m-n+2k)=$$

$$ =\prod_{k=1}^{n}(m-n+2k-1)\prod_{k=1}^{n} 2 \left( \frac{m-n}{2} +k\right)=$$

$$=\prod_{k=1}^{n} 2\prod_{k=1}^{n}(m-n+2k-1)\prod_{k=1}^{n} \left( \frac{m-n}{2} +k\right)=$$

$$ = 2^n\prod_{k=1}^{n}(m-n+2k-1)\prod_{k=1}^{n} \left( \frac{m-n}{2} +k\right)\geq 2^n \Rightarrow $$

$$ \Rightarrow \prod_{k=1}^{n}(m-n+2k-1)\prod_{k=1}^{n} \left( \frac{m-n}{2} +k\right)\geq 1$$

$$ m \geq n \Rightarrow m-n\geq 0 \Rightarrow \prod_{k=1}^{n}(m-n+2k-1)\prod_{k=1}^{n} \left( \frac{m-n}{2} +k\right)\geq $$

$$ \geq \prod_{k=1}^{n}(2k-1)\prod_{k=1}^{n} k = n!\cdot1\cdot 3\cdot...\cdot (2n-1)>1$$

Нравится задача, чисто счёт. Давайте начнём с доказательства левого неравенства. Преобразуем наше уравнение (деление факториалов) в:

$$(!)(m-n+1)(m-n+2)\dots m(m+1)\dots(m+n) \geq n!*2^n$$

Так как $m \geq n$ то левое уравнение больше равно $(2n!)$ (просто подставим вместо $m$ $n$-ки). По Индукции легко доказываем что $(2n!) \geq n!*2^n$.

Докажем правое неравенство. Заметим что наше произведение вида:

$$\prod (m-n+k)(m+n+1-k) k\in [1:n]$$

До этого легко догадаться если умножать первое и последнее, второе и предпоследнее и т.д. частички. Если доказать что все эти парные произведения меньше или равны $(m^2 +m)$ то задача решена. Ну давайте сравним их:

$$(m-n+k)(m+n+1-k)|(m^2+m) \Rightarrow 2nk+k |n^2+k^2+n\Rightarrow n\geq k, n^2+k^2\geq 2nk (AM \geq GM)$$. Значит $\prod (m-n+k)(m+n+1-k) \leq (m^2+m)^n.$

Кстати, в задаче опечатка. Вместо $2^n$ должно быть $n!*2^n.$

$\dfrac{(m+n)!}{(m-n)!} \geq n! \times 2^n$

$\dfrac{(m+n)!}{(m-n)!n!} \geq 2^n$

$\dfrac{(m+n)(m+n-1) \dots (m-n+1)}{n!} \geq 2^n$

$\dfrac{(m+n)(m+n-1) \dots (m-n+1)}{n!} \geq \dfrac{2n!}{n!}$

$2n(2n-1) \dots (n+1) \geq 2^n$

$n+1, n+2 \dots 2n-1 \geq n$

$2n(2n-1) \dots (n+1) \geq 2n \times n^{n-1} \rightarrow 2n^n \geq 2^n$

Ч.Т.Д

$$$$

$$(m^2+m)^n \geq (m+n)(m+n-1) \dots (m-n+1)$$

$$m(m+1) \geq (m-1)(m+2), (m-2)(m+3), \dots ,(m+n)(m-n+1) \rightarrow$$

$$ (m^2+m)^n \geq (m+n)(m+n-1) \dots (m-n+1)$$

Ч.Т.Д