Ανισότητα με συνάρτηση

vzf · #1

Να αποδείξετε ότι $\displaystyle{\binom{n}{k}\leq 2^{n\cdot H(\frac{k}{n})}}$ όπου H(x)

είναι η συνάρτηση εντροπίας $\displaystyle{H(x)=-x\log_2 x-(1-x)\log_2(1-x)}$ .

#2

vzf έγραψε:Να αποδείξετε ότι $\displaystyle{\binom{n}{k}\leq 2^{n\cdot H(\frac{k}{n})}}$ όπου είναι η συνάρτηση εντροπίας $\displaystyle{H(x)=-x\log_2 x-(1-x)\log_2(1-x)}$ .

$\displaystyle{{2^{n \cdot H\left( x \right)}} = {2^{ - n \cdot \left( {x{{\log }_2}x + \left( {1 - x} \right){{\log }_2}\left( {1 - x} \right)} \right)}} = {x^{ - nx}}{\left( {1 - x} \right)^{ - n\left( {1 - x} \right)}} \Rightarrow {2^{n \cdot H\left( {k/n} \right)}} = {\left( {\frac{n}{k}} \right)^k}{\left( {\frac{n}{{n - k}}} \right)^{\left( {k - n} \right)}} = \frac{{{n^n}}}{{{k^k}{{\left( {n - k} \right)}^{n - k}}}}}$

Άρα $\displaystyle{\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right) \leqslant {2^{n \cdot H\left( {k/n} \right)}} \Leftrightarrow \frac{{n!}}{{k!\left( {n - k} \right)!}} \leqslant \frac{{{n^n}}}{{{k^k}{{\left( {n - k} \right)}^{n - k}}}}}$ και λόγω συμμετρίας, αρκεί να αποδειχθεί για $\displaystyle{k = 1,2,..,\left\lfloor {\frac{n}{2}} \right\rfloor }$ .

Μέθοδος Μαθηματικής Επαγωγής: Για $\displaystyle{k = 1:\quad \frac{{n!}}{{\left( {n - 1} \right)!}} \leqslant \frac{{{n^n}}}{{{{\left( {n - 1} \right)}^{n - 1}}}} \Leftrightarrow n \leqslant \frac{{{n^n}}}{{{{\left( {n - 1} \right)}^{n - 1}}}} \Leftrightarrow 1 \leqslant {\left( {\frac{n}{{n - 1}}} \right)^{n - 1}}}$ ισχύει .

Έστω $\displaystyle{\frac{{n!}}{{k!\left( {n - k} \right)!}} \leqslant \frac{{{n^n}}}{{{k^k}{{\left( {n - k} \right)}^{n - k}}}}}$ για κάποιο $\displaystyle{k = 1,2,..}$ . Τότε $\displaystyle{\frac{{n!}}{{\left( {k + 1} \right)!\left( {n - k - 1} \right)!}} = \frac{{n - k}}{{k + 1}} \cdot \frac{{n!}}{{k!\left( {n - k} \right)!}} \leqslant \frac{{n - k}}{{k + 1}} \cdot \frac{{{n^n}}}{{{k^k}{{\left( {n - k} \right)}^{n - k}}}}}$

Επομένως αρκεί $\displaystyle{\frac{{n - k}}{{k + 1}} \cdot \frac{{{n^n}}}{{{k^k}{{\left( {n - k} \right)}^{n - k}}}} \leqslant \frac{{{n^n}}}{{{{\left( {k + 1} \right)}^{k + 1}}{{\left( {n - k - 1} \right)}^{n - k - 1}}}}}$ . Όμως $\displaystyle{\frac{{n - k}}{{k + 1}} \cdot \frac{{{n^n}}}{{{k^k}{{\left( {n - k} \right)}^{n - k}}}} \leqslant \frac{{{n^n}}}{{{{\left( {k + 1} \right)}^{k + 1}}{{\left( {n - k - 1} \right)}^{n - k - 1}}}} \Leftrightarrow }$

$\displaystyle{ \Leftrightarrow \frac{{{{\left( {k + 1} \right)}^k}}}{{{k^k}}} \leqslant \frac{{{{\left( {n - k} \right)}^{n - k - 1}}}}{{{{\left( {n - k - 1} \right)}^{n - k - 1}}}} \Leftrightarrow {\left( {1 + \frac{1}{k}} \right)^k} \leqslant {\left( {1 + \frac{1}{{n - k - 1}}} \right)^{n - k - 1}}}$ που ισχύει διότι η συνάρτηση $\displaystyle{f\left( x \right) = {\left( {1 + \frac{1}{x}} \right)^x}}$ είναι γνήσια αύξουσα (κλασσικά) και $\displaystyle{k \leqslant n - k - 1}$ .

Ανισότητα με συνάρτηση

Ανισότητα με συνάρτηση

Re: Ανισότητα με συνάρτηση

Μέλη σε σύνδεση