Ανισότητα για διωνυμικό συντελεστή

AlexandrosG · #1

Για φυσικούς $n\geq k$ να αποδειχθεί η ανισότητα

$\displaystyle{\binom{n}{k}\leq \frac{n^n}{k^k(n-k)^{n-k}}}$

Μάλλον υπάρχουν καλύτερα άνω φράγματα αλλά για το συγκεκριμένο έχω μια πολύ ωραία απόδειξη.

Λάμπρος Κατσάπας · #2

AlexandrosG έγραψε: Τρί Μαρ 27, 2018 2:39 am Για φυσικούς $n\geq k$ να αποδειχθεί η ανισότητα

$\displaystyle{\binom{n}{k}\leq \frac{n^n}{k^k(n-k)^{n-k}}}$

Μάλλον υπάρχουν καλύτερα άνω φράγματα αλλά για το συγκεκριμένο έχω μια πολύ ωραία απόδειξη.

Αρκεί να δείξουμε ότι για $1\leq k\leq n-1$ ισχύει $\binom{n}{k}k^k(n-k)^{n-k}\leq n^n.$

Είναι

$n^n=(k+(n-k))^n =\sum_{j=0}^{n}\binom{n}{j}k^j(n-k)^{n-j}$

$=\sum_{j=0,j\neq k}^{n}\binom{n}{j}k^j(n-k)^{n-j}+\binom{n}{k}k^k(n-k)^{n-k} \geq\binom{n}{k} k^k(n-k)^{n-k} .$

#3

Ωραία. Χρησιμοποιήστε τώρα το αποτέλεσμα για να δείξετε ότι $\displaystyle \binom{n}{k} \leqslant \left( \frac{en}{k}\right)^k.$

Είναι ασθενέστερη από την αρχική ανισότητα που ζητήθηκε αλλά αρκετά εύχρηστη.

Tolaso J Kos · #4

Demetres έγραψε: Τρί Μαρ 27, 2018 1:27 pm <...> να δείξετε ότι $\displaystyle \binom{n}{k} \leqslant \left( \frac{en}{k}\right)^k.$ <...>

Η κλασσική που υπάρχει εκεί έξω είναι η ακόλουθη:

$\displaystyle{\begin{aligned} \binom{n}{k} \left( \frac{k}{en} \right)^k &= \frac{n(n-1) \ldots (n-k+1)}{n^k} \frac{k^k}{k! e^k}\\ & \leq \frac{k^k}{k! e^k} \\ &<1 \end{aligned}}$
αφού $e^k =\sum \limits_{n=1}^{\infty} \frac{k^n}{n!}$ . Το αποτέλεσμα έπεται.

Tolaso J Kos · #5

AlexandrosG έγραψε: Τρί Μαρ 27, 2018 2:39 am Για φυσικούς $n\geq k$ να αποδειχθεί η ανισότητα

$\displaystyle{\binom{n}{k}\leq \frac{n^n}{k^k(n-k)^{n-k}}}$

Μάλλον υπάρχουν καλύτερα άνω φράγματα αλλά για το συγκεκριμένο έχω μια πολύ ωραία απόδειξη.

Μία άλλη απόδειξη που έχω δει για αυτό είναι η ακόλουθη:

$\displaystyle{\begin{aligned} \binom {n}{k} &=\frac{n!}{k!(n-k)!}\\ &\leq \frac{ e\ n^{n+1/2} e^{-n}}{\sqrt{2\pi}\ k^{k+1/2} e^{-k}\sqrt{2\pi}\ (n-k)^{n-k+1/2} e^{-(n-k)}}\\ &=\frac{ e}{2\pi}\sqrt{\frac{n}{k(n-k)}}\frac{n^n}{k^k(n-k)^{n-k}} \\ &\leq \frac{n^n}{k^k(n-k)^{n-k}} \end{aligned}}$
αφού από Stirling είναι $\sqrt{2\pi}\ n^{n+1/2} e^{-n} \le n! \leq e\ n^{n+1/2} e^{-n}$ .

Λάμπρος Κατσάπας · #6

Demetres έγραψε: Τρί Μαρ 27, 2018 1:27 pm Ωραία. Χρησιμοποιήστε τώρα το αποτέλεσμα για να δείξετε ότι $\displaystyle \binom{n}{k} \leqslant \left( \frac{en}{k}\right)^k.$

Είναι ασθενέστερη από την αρχική ανισότητα που ζητήθηκε αλλά αρκετά εύχρηστη.

Είναι

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

Επειδή $\left ( {1+\frac{k}{n-k}} \right )^{n-k} \leq e^k$ (γνησίως αύξουσα ως προς

με όριο το e^k

)

θα είναι τελικά

$\frac{n^k}{k^k} \left ( {1+\frac{k}{n-k}} \right )^{n-k}\leq \frac{n^k}{k^k} e^k$

AlexandrosG · #7

Γράφω την απόδειξη μου.

Ισχύει ότι $\displaystyle{\binom{n}{k}=\frac{1}{2\pi i} \oint_{\gamma}\frac{(1+z)^n}{z^{k+1}} \mathrm{d}z}$ όπου $\gamma$ είναι οποιαδήποτε απλή, κλειστή καμπύλη στο μιγαδικό επίπεδο που περικλείει το z=0

. Η απόδειξη της σχέσης αυτής είναι άμεση από το διωνυμικό θεώρημα και το θεώρημα του Cauchy. Αν τώρα στο πρόβλημα χρησιμοποιήσουμε ως $\gamma$ τον κύκλο με κέντρο το μηδέν και ακτίνα $\delta>0$ και το απλό

-φράγμα παίρνουμε $\displaystyle{\binom{n}{k} \leq \frac{2\pi \delta}{2 \pi}\max_{|z|=\delta} \left| \frac{(1+z)^n}{z^{k+1}} \right| \leq \frac{(1+\delta)^n}{\delta^{k}}}$ . Η τελευταία παράσταση έχει ελάχιστο για $\delta=\frac{k}{n-k}$ οπότε βρίσκουμε $\displaystyle{\binom{n}{k}\leq \frac{n^n}{k^k(n-k)^{n-k}}}$ .

Η ολοκληρωτική αυτή αναπαράσταση, αν και αχρείαστη στο συγκεκριμένο πρόβλημα λόγω της πολύ απλής απόδειξης του Λάμπρου, μπορεί να χρησιμοποιηθεί σε άλλα προβλήματα με διωνυμικούς συντελεστές. Για παράδειγμα σε ταυτότητες όπως η $\displaystyle \binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}$ ή σε υπολογισμούς αθροισμάτων όπως το $\displaystyle{\sum_{n=0}^{\infty} \binom{2n}{n}\frac{1}{5^n}}$ .

Tolaso J Kos · #8

AlexandrosG έγραψε: Τρί Μαρ 27, 2018 11:30 pm
Ισχύει ότι $\displaystyle{\binom{n}{k}=\frac{1}{2\pi i} \oint_{\gamma}\frac{(1+z)^n}{z^{k+1}} \mathrm{d}z}$ όπου $\gamma$ είναι οποιαδήποτε απλή, κλειστή καμπύλη στο μιγαδικό επίπεδο που περικλείει το .

Για παράδειγμα σε ταυτότητες όπως η $\displaystyle \binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}$ ή σε υπολογισμούς αθροισμάτων όπως το $\displaystyle{\sum_{n=0}^{\infty} \binom{2n}{n}\frac{1}{5^n}}$ .

Βεβαίως. Ένα χαρακτηριστικό παράδειγμα έχουμε δει και εδώ πριν

χρόνια. ( πω πω πώς περνάν τα χρόνια ) . Βέβαια για το $\binom{2n}{n}$ έχουμε γεννήτρια. Επίσης υπάρχει γεννήτρια για τη σειρά $\sum \limits_{n=0}^{\infty} \binom{3n}{n} x^n$ . Ισχύει:

$\displaystyle{\begin{aligned} \sum\limits_{n=0}^{\infty} \binom{3n}{n}x^n &=-\frac{1}{2\pi i}\int\limits_{-i\infty}^{i\infty} \pi\csc (\pi s) f(s)\,ds\\ &= -\frac{1}{2\pi i}\int\limits_{-i\infty}^{i\infty} \pi\csc (\pi s) \dfrac{(-x)^s\Gamma(3s+1)}{\Gamma(2s+1)\Gamma(s+1)}\,ds& \\ &= -\frac{1}{2\pi i}\int\limits_{-i\infty}^{i\infty} \pi\csc (\pi s) \dfrac{(-x)^s3^{3s+\frac{1}{2}}\Gamma \left(s+\frac{1}{3}\right)\Gamma \left(s+\frac{2}{3}\right)}{\sqrt{2\pi}2^{2s+\frac{1}{2}}\Gamma \left(s+\frac{1}{2}\right)\Gamma(s+1)}\,ds& \\ &= \frac{1}{2\pi i}\frac{\sqrt{3}}{\sqrt{4\pi}}\int\limits_{-i\infty}^{i\infty} \dfrac{\Gamma \left(s+\frac{1}{3}\right)\Gamma \left(s+\frac{2}{3}\right)}{\Gamma \left(s+\frac{1}{2}\right)}\Gamma(-s)\left(-\frac{27}{4}x\right)^s\,ds& \\ &= \sqrt{\frac{3}{4\pi}}\frac{\Gamma\left(\frac{1}{3}\right)\Gamma\left(\frac{2}{3}\right)}{\Gamma\left(\frac{1}{2}\right)}{_2F_1}\left(\frac{1}{3},\frac{2}{3};\frac{1}{2};\frac{27}{4}x\right)& \\ &= \left(1-\frac{27}{4}x\right)^{-1/2}{_2F_1}\left(-\frac{1}{6},\frac{1}{6};\frac{1}{2};\frac{27}{4}x\right)& \\ &= \left(1-\frac{27}{4}x\right)^{-1/2} \cos \left(\frac{1}{3}\arcsin \frac{3\sqrt{3x}}{2}\right)& \end{aligned}}$
όπου $\displaystyle{f(s) = \dfrac{(-x)^s\Gamma(3s+1)}{\Gamma(2s+1)\Gamma(s+1)}}$ την οποία ολοκληρώνουμε πάνω σε ορθογώνιο με κορυφές $\gamma_T = (0+iT),(0-iT),(R-iT),(R+iT)$ .

Σημείωση: Η σειρά συγκλίνει όταν $\left| x \right| < \frac{4}{27}$ .

Ανισότητα για διωνυμικό συντελεστή

Ανισότητα για διωνυμικό συντελεστή

Re: Ανισότητα για διωνυμικό συντελεστή

Re: Ανισότητα για διωνυμικό συντελεστή

Re: Ανισότητα για διωνυμικό συντελεστή

Re: Ανισότητα για διωνυμικό συντελεστή

Re: Ανισότητα για διωνυμικό συντελεστή

Re: Ανισότητα για διωνυμικό συντελεστή

Re: Ανισότητα για διωνυμικό συντελεστή

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