guanmo1

1^# 跳转到 » 倒序看帖

打印

字体大小: tT

发表于 2014-2-21 10:05 | 只看该作者

[组合] 组合不等式

如图

____kuing edit in $\mathrm\LaTeX$____
求证：\[ C_{m+n}^n\leqslant \frac{(m+n)^{m+n}}{(n+1)^n\cdot m^m}. \]

分享到: QQ空间 腾讯微博 腾讯朋友

战巡

2^#

发表于 2014-2-21 13:57 | 只看该作者

本帖最后由战巡于 2014-2-21 14:00 编辑

目测少条件$m≠0$吧...
要不然右边就乱套了，而且即便按极限算也是错的
这里就强行加上这个条件了

从极限来看这玩意其实最后两边差很远，根本不是一个数量级的
但对阶乘来说，各种放缩的误差都大得离谱，所以其实没什么好办法

于是我们出赖招——数学归纳
首先看$m,n$都取最小值，即$m=1,n=0$的情况
显然有：
\[C_1^1=\frac{1^1}{1^0·1^1}=1\]
满足不等式
假设有:
\[C_{m+n}^n\le \frac{(m+n)^{m+n}}{(n+1)^n·m^m}\]
成立
则$m=m+1$时，左边为：
\[C_{m+1+n}^n=\frac{m+n+1}{m+1}C_{m+n}^n\le \frac{m+n+1}{m+1}·\frac{(m+n)^{m+n}}{(n+1)^n·m^m}\]
右边：
\[\frac{(m+n+1)^{m+n+1}}{(n+1)^n·(m+1)^{m+1}}=\frac{(m+n)^{m+n}}{(n+1)^n·m^m}·\frac{(m+n+1)^{m+n+1}m^m}{(m+n)^{m+n}(m+1)^{m+1}}\]
则只要比较$\frac{m+n+1}{m+1}$与$\frac{(m+n+1)^{m+n+1}m^m}{(m+n)^{m+n}(m+1)^{m+1}}$大小即可
右边除以左边可得：
\[\frac{(m+n+1)^{m+n}m^m}{(m+n)^{m+n}(m+1)^m}\]
\[=\frac{(1+\frac{1}{m+n})^{m+n}}{(1+\frac{1}{m})^{m}}\]
又显然函数$f(x)=(1+\frac{1}{x})^x$是递增的，外加$n\ge 0$，可知这货大于等1，仅当$n=0$时取等
于是有
\[C_{m+1+n}^n\le \frac{(m+n+1)^{m+n+1}}{(n+1)^n·(m+1)^{m+1}}\]

同理可证当$n=n+1$时，有
\[C_{m+n+1}^{n+1}< \frac{(m+n+1)^{m+n+1}}{(n+2)^{n+1}·m^m}\]
不过这里略有不同，鉴于$m≠0$，等号是没戏的，这里是严格的小于号

如此归纳下去可知所有$n\ge 0, m\ge 1$都成立

TOP

realnumber

3^#

发表于 2014-2-21 15:14 | 只看该作者

记$f(x)=\frac{x^x}{x!},x\in Z^+$,$f(1)=1$
问题等价于$\frac{m^m}{m!}\frac{n^n}{n!}\le \frac{(m+n-1)^{m+n-1}}{(m+n-1)!}$,
即$\frac{f(m)}{f(m-1)}\frac{f(m-1)}{f(m-2)}\cdots\frac{f(2)}{f(1)}\le \frac{f(m+n-1)}{f(m+n-2)}\cdots\frac{f(n+1)}{f(n)}$
而$\frac{f(k+1)}{f(k)}=(1+\frac{1}{k})^k，k\ge1 $是k的增函数.
因此上式成立，即1楼不等式成立.

TOP

realnumber

4^#

发表于 2014-2-21 19:30 | 只看该作者

本帖最后由 realnumber 于 2014-2-21 19:50 编辑

继续证明这个$\frac{m^m}{m!}\frac{n^n}{n!}\le \frac{(m+n-1)^{m+n-1}}{(m+n-1)!},m,n\in Z^+$---(1)
容易检验m=1,2,3（或n=1,2,3）时，上述不等式成立.
如此只需要证明$m\ge4$且$n\ge4$即可.
不等式(1)变形为
$C_{m+n}^n\le\frac{(m+n)^{m+n}}{m^mn^n}\frac{(m+n-1)^{m+n-1}}{(m+n)^{m+n-1}}$-----(2)
又$2\le (1+\frac{1}{k})^k<3,k\ge1$,所以$\frac{1}{3}<\frac{(m+n-1)^{m+n-1}}{(m+n)^{m+n-1}}\le\frac{1}{2}$
所以要证明(2)成立，只需要证明$3C_{m+n}^n\le\frac{(m+n)^{m+n}}
{m^mn^n}$
又由二项式定理$(m+n)^{m+n}\ge C_{m+n}^{n-2}m^{m+2}n^{n-2}+C_{m+n}^{n-1}m^{m+1}n^{n-1}+C_{m+n}^nm^mn^n+C_{m+n}^{n+1}m^{m-1}n^{n+1}+C_{m+n}^{n+2}m^{m-2}n^{n+2}$
$C_{m+n}^{n-2}m^{m+2}n^{n-2}=\frac{n-1}{n}\frac{m^2}{(m+1)(m+2)}C_{m+n}^nm^mn^n\ge \frac{1}{4}C_{m+n}^nm^mn^n,C_{m+n}^{n-1}m^{m+1}n^{n-1}\ge\frac{3}{4}C_{m+n}^nm^mn^n,$
同样有$C_{m+n}^{n+1}m^{m-1}n^{n+1}\ge\frac{3}{4}C_{m+n}^nm^mn^n,C_{m+n}^{n+2}m^{m-2}n^{n+2}\ge \frac{1}{4}C_{m+n}^nm^mn^n$
所以有$(m+n)^{m+n}\ge 3C_{m+n}^nm^mn^n$
即证明了(2)成立，即1楼不等式成立.

加个说明：由二项式定理$(1+\frac{1}{k})^k=1+1+C_k^2\frac{1}{k^2}+C_k^3\frac{1}{k^3}+\cdots \le 1+1+\frac{1}{1\times2}+\frac{1}{2\times3}+\frac{1}{3\times4}+\cdots <3$

TOP

kuing

5^#

发表于 2014-2-21 19:35 | 只看该作者

回复 3# realnumber

其实我没看懂怎么等价过去的……

TOP

realnumber

6^#

发表于 2014-2-21 19:42 | 只看该作者

1楼问题就是$\frac{(n+1)^n}{n!}\frac{m^m}{m!}\le\frac{(m+n)^{m+n}}{(m+n)!}$
而$\frac{(n+1)^n}{n!}=\frac{(n+1)^{n+1}}{(n+1)!}$
如此问题就是$\frac{(n+1)^{n+1}}{(n+1)!}\frac{m^m}{m!}\le\frac{(m+n)^{m+n}}{(m+n)!}$
再n用n-1替换

TOP

kuing

7^#

发表于 2014-2-21 20:26 | 只看该作者

回复 6# realnumber

soga...nice!

TOP

战巡

8^#

发表于 2014-2-22 00:32 | 只看该作者

本帖最后由战巡于 2014-2-22 00:36 编辑

回复 1# guanmo1

可以顺便研究一下极限情况
当$m,n$都很大时，由斯特灵公式可知
\[C_{m+n}^n=\frac{(m+n)!}{m!n!}\approx \frac{\sqrt{2\pi (m+n)}(m+n)^{m+n}}{e^{m+n}}·\frac{e^m}{\sqrt{2\pi m}m^m}·\frac{e^n}{\sqrt{2\pi n}n^n}\]
\[=\frac{(m+n)^{m+n}}{m^mn^n}·\sqrt{\frac{m+n}{2\pi mn}}\]
这里面$\frac{1}{e}·\frac{(m+n)^{m+n}}{m^mn^n}$与右边是等价无穷大的，但$\sqrt{\frac{m+n}{2\pi mn}}$却会趋于0
也就是左右两边根本不在同一个水平上，$m,n$很大时会差很远

TOP

返回列表回复发帖

[组合] 组合不等式

[收藏此主题] [关注此主题的新回复]

[通过 QQ、MSN 分享给朋友]